数据结构：二叉查找树

---

二叉查找树

一，概述

二叉查找树，也称为二叉搜索树，是一种特殊的二叉树，它或者是一颗空树，或者具有以下性质：对于每个非空节点，其左子树中所有节点的值都小于该节点的值，而右子树中所有节点的值都大于该节点的值。这种特性使得在二叉查找树中查找一个特定的值变得相对简单和高效。

二叉查找树的查找操作如下：

1. 从根节点开始查找。
2. 如果当前节点为空，说明查找失败，返回NULL。
3. 如果当前节点的值等于要查找的值，说明查找成功，返回当前节点。
4. 如果要查找的值小于当前节点的值，则在左子树中继续查找。
5. 如果要查找的值大于当前节点的值，则在右子树中继续查找。

在二叉查找树中，每个节点的左子树和右子树的高度最多相差1，因此，二叉查找树的查找时间复杂度是O(log n)，其中n是树中节点的数量。在最坏的情况下，当树完全不平衡时，可能退化成O(n)的时间复杂度。为了保持二叉查找树的效率，通常会使用一些平衡的策略，如AVL树和红黑树。

总的来说，二叉查找树是一种常见的数据结构，它具有很好的查找性能，但是需要注意平衡的问题，以避免效率的降低。

简介：

• 二叉查找树是一种自我平衡的二叉树，它的中序遍历会得到一个升序的序列。
• 二叉查找树的每个节点都包含一个键和一个值，其中键用于保持树的排序，而值则可以是任何类型的数据。
• 二叉查找树的主要操作包括插入、查找和删除。

图示：

以下是一个简单的二叉查找树的图示：

      50
     / \
    30  70
   / \  / \
  10 40 60 80
1
2
3
4
5

在这个二叉查找树中，每个节点的键都大于其左子树中所有节点的键，且小于其右子树中所有节点的键。

示例：

以下是一个在Java中实现二叉查找树的简单示例：

public class BinarySearchTree {
    class Node {
        int key;
        Node left, right;

        public Node(int item) {
            key = item;
            left = right = null;
        }
    }

    Node root;

    BinarySearchTree(int key) {
        root = new Node(key);
    }

    BinarySearchTree() {
        root = null;
    }

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

    Node insertRec(Node root, int key) {
        if (root == null) {
            root = new Node(key);
            return root;
        }
        if (key < root.key) {
            root.left = insertRec(root.left, key);
        } else if (key > root.key) {
            root.right = insertRec(root.right, key);
        }
        return root;
    }

    void inorder()  {
        inorderRec(root);
    }

    void inorderRec(Node root) {
        if (root != null) {
            inorderRec(root.left);
            System.out.println(root.key);
            inorderRec(root.right);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

在这个示例中，定义了一个内部类Node来表示二叉查找树的节点。每个节点都有一个键key和两个子节点left和right。还定义了两个方法insert和inorder。insert方法用于向二叉查找树中插入一个新的节点，而inorder方法则用于按中序遍历顺序打印出树中的所有节点的键。

二，添加数据

在Java中，二叉查找树（Binary Search Tree）是一种常见的数据结构。在二叉查找树中，每个节点包含一个关键字和两个指向其子树的链接。树也必须满足二叉查找树性质：左子树上的所有关键字都小于其根节点的关键字，右子树上的所有关键字都大于其根节点的关键字。

下面是一个简单的Java类，表示一个二叉查找树节点：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
1
2
3
4
5
6
7
8
9

然后可以创建一个二叉查找树的类，并实现添加数据的方法：

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void add(int value) {
        root = addRecursive(root, value);
    }

    private TreeNode addRecursive(TreeNode current, int value) {
        if (current == null) {
            return new TreeNode(value);
        }

        if (value < current.val) {
            current.left = addRecursive(current.left, value);
        } else if (value > current.val) {
            current.right = addRecursive(current.right, value);
        } else {
            // value already exists in the tree, do nothing
            return current;
        }

        return current;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

在这个类中，使用了递归方法addRecursive来找到应该插入新节点的位置。如果树为空，就在根节点插入新值。如果新值小于当前节点的值，将其插入到左子树；如果新值大于当前节点的值，将其插入到右子树。如果新值已经存在于树中，什么也不做。

三，删除数据

在Java中，二叉查找树（Binary Search Tree）是一种常见的数据结构。在二叉查找树中，每个节点包含一个关键字和两个指向其子树的链接。树也必须满足二叉查找树性质：左子树上的所有关键字都小于其根节点的关键字，右子树上的所有关键字都大于其根节点的关键字。

下面是一个简单的Java类，表示一个二叉查找树节点：

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}
1
2
3
4
5
6
7
8
9

然后可以创建一个二叉查找树的类，并实现删除数据的方法：

public class BinarySearchTree {
    private TreeNode root;

    public BinarySearchTree() {
        root = null;
    }

    public void remove(int value) {
        root = removeRecursive(root, value);
    }

    private TreeNode removeRecursive(TreeNode current, int value) {
        if (current == null) {
            return null;
        }

        if (value == current.val) {
            // Node with the given value found, remove it from the tree.
            if (current.left == null && current.right == null) {
                return null;
            } else if (current.left == null) {
                return current.right;
            } else if (current.right == null) {
                return current.left;
            } else {
                // Find the minimum value in the right subtree and replace it with the current node's value.
                TreeNode minNode = findMin(current.right);
                current.val = minNode.val;
                current.right = removeRecursive(current.right, minNode.val);
                return current;
            }
        } else if (value < current.val) {
            current.left = removeRecursive(current.left, value);
            return current;
        } else {
            current.right = removeRecursive(current.right, value);
            return current;
        }
    }

    private TreeNode findMin(TreeNode node) {
        while (node.left != null) {
            node = node.left;
        }
        return node;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

在这个类中，使用了递归方法removeRecursive来找到应该删除节点的位置。如果要删除的节点没有子节点，直接返回null。如果要删除的节点只有一个子节点，将这个子节点返回作为新的节点。如果要删除的节点有两个子节点，找到右子树中的最小节点，用它替换要删除的节点，然后在右子树中递归删除这个最小节点。