【数据结构与算法】手撕二叉查找树

二叉查找树

定义

• 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，且各结点关键词互异，其中根序列按其关键词递增排列。

• 等价描述：二叉查找树中任一结点 P，其左子树中结点的关键词都小于 P 的关键词，右子树中结点的关键词都大于 P 的关键词，且结点 P 的左右子树也都是二叉查找树

节点结构

1️⃣ key：关键字的值
2️⃣ value：关键字的存储信息
3️⃣ left：左节点的引用
4️⃣ right：右节点的引用

复制代码
1
2
3
4
5
6
7
java
class BSTNode<K extends Comparable<K>,V>{
    public K key;
    public V value;

    public BSTNode<K,V> left;
    public BSTNode<K,V> right;
}

为了代码简洁，本文不考虑属性的封装，一律设为 public

查找算法

思想：利用二叉查找树的特性，左子树值小于根节点值，右子树值大于根节点值，从根节点开始搜索

• 如果目标值等于某节点值，返回该节点
• 如果目标值小于某节点值，搜索该节点的左子树
• 如果目标值大于某节点值，搜索该节点的右子树

1️⃣ 递归版本

复制代码
1
2
3
4
5
6
7
8
9
java
    public BSTNode<K, V> searchByRecursion(K key) {
        return searchByRecursion(root, key);
    }

    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
        if (t == null || t.key == key) return t;
        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
        else return searchByRecursion(t.right, key);
    }

2️⃣ 迭代版本

复制代码
1
2
3
4
5
6
7
8
9
java
    public BSTNode<K,V> searchByIteration(K key) {
        BSTNode<K,V> p = this.root;
        while(p != null) {
            if(key.compareTo(p.key) < 0) p = p.left;
            else if(key.compareTo(p.key) > 0) p = p.right;
            else return p;
        }
        return null;
    }

插入算法

• 在以 t 为根的二叉查找树中插入关键词为 key 的结点
• 在 t 中查找 key，在查找失败处插入

1️⃣ 递归版本

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
java
public void insertByRecursion(K key, V value) {
        this.root = insertByRecursion(root, key, value);
    }

    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
        if (t == null) {
            return new BSTNode<>(key, value);
        } 
        else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);
        else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);
        else {
            t.value = value;  // 如果二叉查找树中已经存在关键字，则替换该结点的值
        }
        return t;
    }

2️⃣ 迭代版本

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
java
    public void insertByIteration(K key, V value) {
        BSTNode<K, V> p = root;
        if (p == null) {
            root = new BSTNode<>(key, value);
            return;
        }
        BSTNode<K, V> pre = null;
        while (p != null) {
            pre = p;
            if (key.compareTo(p.key) < 0) p = p.left;
            else if (key.compareTo(p.key) > 0) p = p.right;
            else {
                p.value = value;    // 如果二叉查找树中已经存在关键字，则替换该结点的值
                return;
            }
        }
        if(key.compareTo(pre.key) < 0) {
            pre.left = new BSTNode<>(key, value);
        } else {
            pre.right = new BSTNode<>(key, value);
        }
    }

删除算法

• 在以 t 为根的二叉查找树中删除关键词值为 key 的结点

• 在 t 中找到关键词为 key 的结点，分三种情况删除 key

  • 若 key 是叶子节点，则直接删除
    

  • 若 key 只有一棵子树，则子承父业
    

  • 若 key 既有左子树也有右子树，则找到 key 的后继结点，替换 key 和后继（前驱）节点的值，然后删除后继节点（后继/前驱节点只有一棵子树，转化为第二种情况）。
    后继结点是当前结点的右子树的最左结点，如果右子树没有左子树，则后继节点就是右子树的根节点。
    前驱结点时当前节点的左子树的最右结点，如果左子树没有右子树，则前驱结点就是左子树的根节点。
    
    

1️⃣ 写法一

复制代码
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
java
    public void removeByRecursion(K key) {
        this.root = removeByRecursion(root, key);
    }
    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
        if(t == null) return root;
        else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树
        else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，递归处理左子树
        else {
            if(t.right == null) return t.left;  // 情况一、二一起处理
            if(t.left == null) return t.right;  // 情况一、二一起处理
            BSTNode<K, V> node = t.right;       // 情况三：右子树没有左子树
            if (node.left == null) {
                node.left = t.left;
            } else {                            // 情况三：右子树有左子树
                BSTNode<K, V> pre = null;
                while (node.left != null) {
                    pre = node;
                    node = node.left;
                }
                t.key = node.key;
                t.value = node.value;
                pre.left = node.right;
            }
        }
        return t;
    }

2️⃣ 写法二

情况三也进行递归处理，写法更简单（考虑的前驱结点）

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
java
    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
        if (t == null) return root;
        else if (t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树
        else if (t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，递归处理左子树
        else {
            else if (t.right == null) return t.left;
            else {
                BSTNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = removeByRecursion(t.left, t.key);
            }
        }
        return t;
    }

完整代码

复制代码
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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
java
class BSTNode<K extends Comparable<K>, V> {
    public K key;
    public V value;

    public BSTNode<K, V> left;
    public BSTNode<K, V> right;

    public BSTNode(K key, V value) {
        this.key = key;
        this.value = value;
    }
}

class BSTree<K extends Comparable<K>, V> {
    public BSTNode<K, V> root;

    private void inorder(BSTNode<K, V> root) {
        if (root != null) {
            inorder(root.left);
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
            inorder(root.right);
        }
    }

    private void preorder(BSTNode<K, V> root) {
        if (root != null) {
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
            preorder(root.left);
            preorder(root.right);
        }
    }

    private void postorder(BSTNode<K, V> root) {
        if (root != null) {
            postorder(root.left);
            postorder(root.right);
            System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
        }
    }

    public void postorderTraverse() {
        System.out.print("后序遍历：");
        postorder(root);
        System.out.println();
    }

    public void preorderTraverse() {
        System.out.print("先序遍历：");
        preorder(root);
        System.out.println();
    }

    public void inorderTraverse() {
        System.out.print("中序遍历：");
        inorder(root);
        System.out.println();
    }

    public BSTNode<K, V> searchByRecursion(K key) {
        return searchByRecursion(root, key);
    }

    private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
        if (t == null || t.key == key) return t;
        else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
        else return searchByRecursion(t.right, key);
    }

    public BSTNode<K, V> searchByIteration(K key) {
        BSTNode<K, V> p = root;
        int cmp = key.compareTo(p.key);
        while (p != null) {
            if (cmp < 0) p = p.left;
            else if (cmp > 0) p = p.right;
            else return p;
        }
        return null;
    }

    public void insertByRecursion(K key, V value) {
        this.root = insertByRecursion(root, key, value);
    }

    private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
        if (t == null) {
            return new BSTNode<>(key, value);
        }
        int cmp = key.compareTo(t.key);
        if (cmp < 0) t.left = insertByRecursion(t.left, key, value);
        else if (cmp > 0) t.right = insertByRecursion(t.right, key, value);
        else {
            t.value = value;
        }
        return t;
    }

    public void insertByIteration(K key, V value) {
        BSTNode<K, V> p = root;
        if (p == null) {
            root = new BSTNode<>(key, value);
            return;
        }
        BSTNode<K, V> pre = null;
        while (p != null) {
            pre = p;
            int cmp = key.compareTo(p.key);
            if (cmp < 0) p = p.left;
            else if (cmp > 0) p = p.right;
            else {
                p.value = value;    // 如果二叉查找树中已经存在关键字，则替换该结点的值
                return;
            }
        }
        if (key.compareTo(pre.key) < 0) {
            pre.left = new BSTNode<>(key, value);
        } else {
            pre.right = new BSTNode<>(key, value);
        }
    }

    public void removeByRecursion(K key) {
        this.root = removeByRecursion(root, key);
    }

    private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
        if (t == null) return root;
        else if (t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，递归处理右子树
        else if (t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key);   // key小，递归处理左子树
        else {
//            if (t.right == null) return t.left;  // 情况一
//            if (t.left == null) return t.right;  // 情况二
//            BSTNode<K, V> node = t.right;       // 情况三：右子树没有左子树
//            if (node.left == null) {
//                node.left = t.left;
//            } else {                            // 情况三：右子树有左子树
//                BSTNode<K, V> pre = null;
//                while (node.left != null) {
//                    pre = node;
//                    node = node.left;
//                }
//                t.key = node.key;
//                t.value = node.value;
//                pre.left = node.right;
            if (t.left == null) return t.right;
            else if (t.right == null) return t.left;
            else {
                BSTNode<K, V> pre = t.left;
                while (pre.right != null) {
                    pre = pre.right;
                }
                t.key = pre.key;
                t.value = pre.value;
                t.left = removeByRecursion(t.left, t.key);
            }
        }
        return t;
    }
}

🐛 方法测试：

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
java
    public static void main(String[] args) {
        BSTree<Integer, Integer> tree = new BSTree<>();
//        tree.insertByRecursion(1, 1);
//        tree.insertByRecursion(5, 1);
//        tree.insertByRecursion(2, 1);
//        tree.insertByRecursion(4, 1);
//        tree.insertByRecursion(3, 1);
//        tree.insertByRecursion(1, 2);
        tree.insertByIteration(1, 1);
        tree.insertByIteration(5, 1);
        tree.insertByIteration(2, 1);
        tree.insertByIteration(4, 1);
        tree.insertByIteration(3, 1);
        //tree.insertByIteration(1, 5);
        tree.removeByRecursion(4);
        tree.preorderTraverse();
        tree.inorderTraverse();
        tree.postorderTraverse();
        BSTNode<Integer, Integer> node = tree.searchByIteration(1);
        System.out.println(node.key + " " + node.value);
    }

复制代码
1
2
3
4
java
先序遍历：(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1) 
中序遍历：(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1) 
后序遍历：(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5) 
1 5