Java数据结构与算法：二叉搜索树-Toy模板网

这篇具有很好参考价值的文章主要介绍了Java数据结构与算法：二叉搜索树。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

Java数据结构与算法：二叉搜索树

大家好，我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编，也是冬天不穿秋裤，天冷也要风度的程序猿！

什么是二叉搜索树？

在计算机科学中，二叉搜索树（Binary Search Tree，简称BST）是一种常见的树形数据结构，它具有良好的查找和插入性能。每个节点的左子树上所有节点的值小于根节点的值，右子树上所有节点的值大于根节点的值。

二叉搜索树的性质

对于二叉搜索树的每个节点，其左子树的所有节点值都小于该节点的值。
对于二叉搜索树的每个节点，其右子树的所有节点值都大于该节点的值。
对于二叉搜索树的每个节点，其左右子树也分别是二叉搜索树。

二叉搜索树的基本操作

插入节点

在二叉搜索树中插入一个节点，首先需要找到插入的位置。从根节点开始，比较要插入节点的值与当前节点的值，根据大小关系决定向左子树还是右子树移动，直到找到插入位置。

public class BinarySearchTree {
    // 省略其他代码

    public void insert(int value) {
        root = insertRec(root, value);
    }

    private TreeNode insertRec(TreeNode root, int value) {
        if (root == null) {
            root = new TreeNode(value);
            return root;
        }

        if (value < root.data) {
            root.left = insertRec(root.left, value);
        } else if (value > root.data) {
            root.right = insertRec(root.right, value);
        }

        return root;
    }
}

查找节点

在二叉搜索树中查找一个节点，同样从根节点开始比较值，根据大小关系决定向左子树还是右子树移动，直到找到目标节点或者到达叶子节点。

public class BinarySearchTree {
    // 省略其他代码

    public boolean search(int value) {
        return searchRec(root, value);
    }

    private boolean searchRec(TreeNode root, int value) {
        if (root == null) {
            return false;
        }

        if (value == root.data) {
            return true;
        } else if (value < root.data) {
            return searchRec(root.left, value);
        } else {
            return searchRec(root.right, value);
        }
    }
}