二叉搜索树

发表于 | 分类于

二叉查找树（Binary Search Tree），它或者是一棵空树，或者是具有下列性质的二叉树：

  • 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
  • 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
  • 它的左、右子树也分别为二叉排序树

二叉搜索树需要特别记住的一点就是，它的中序遍历的序列是递增排序的。

还需要留意二叉搜素树的前驱和后继节点怎么获取。

二叉搜索树对象

我创建了一个 BST 对象，来对二叉树进行插入、删除、查找等常用的操作：

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
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
const BST = {
  root: null, // 根节点
  count: 0, // 节点个数
  // 节点的构造函数
  TreeNode: function (key, value) {
    this.key = key
    this.value = value
    this.left = this.right = null
  },
  // 向二叉搜索数种插入节点，向以 root为根的二叉搜索树中,插入节点(key, value)
  // 回插入新节点后的二叉搜索树的根
  insert: function (root, key, value) {
    if (root === null) {
        return new this.TreeNode(key, value);
    }
    if (key ===  root.key) {
        root.value = value
    } else if (key < root.key) {
        root.left = this.insert(root.left, key, value)
    } else {
        root.right = this.insert(root.right, key, value)
    }
    return root
  },
  // 查看以 root 为根的二叉搜索树中是否包含键值为 key 的节点
  contain: function (root, key) {
    if (root === null) {
      return false
    }
    if (key === root.key) {
      return true
    } else if (key < root.key) {
      return this.contain(root.left, key)
    } else {
      return this.contain(root.right, key)
    }
  },
  // 在以 root 为根的二叉搜索树中查找 key 所对应的 value
  search: function (root, key) {
      if (root === null) {
          return null
      }
      if (key === root.key) {
          return root.value
      } else if (key < root.key) {
          return this.search(root.left, key)
      } else {
          return this.search(root.right, key)
      }
  },
  // root 为根的二叉搜索树进行前序遍历
  preOrder: function (root) {
  	if (root !== null) {
      console.log(root.key)
      this.preOrder(root.left)
      this.preOrder(root.right)
    }
  },
  // root 为根的二叉搜索树进行中序遍历
  inOrder: function (root) {
    if (root !== null) {
      this.inOrder(root.left)
      console.log(root.key)
      this.inOrder(root.right)
    }
  },
  // root 为根的二叉搜索树进行后序遍历
  postOrder: function (root) {
    if (root !== null) {
      this.postOrder(root.left)
      this.postOrder(root.right)
      console.log(root.key)
    }
  },
  // root 为根的二叉搜索树进行层序遍历
  levelOrder: function (root) {
  	let queue = [root]
    while (queue.length) {
      let node = queue.shift()
      console.log(node.key)
      node.left && queue.push(node.left)
      node.right && queue.push(node.right)
    }
  },
  // 销毁二叉树
  destroy: function (root) {
    if (root !== null) {
      this.destroy(root.left)
      this.destroy(root.right)
    }
    delete root
    this.count--
  },
  // 寻找最小健值key
  minimum: function (root) {
    if (root.left === null) {
    	return root.key
    }
    return this.minimum(root.left)
  },
  // 寻找最大健值key
  minimum: function (root) {
    if (root.right === null) {
        return root.key
    }
    return this.minimum(root.right)
  },
  // 删除掉以node为根的二分搜索树中的最小节点
  // 返回删除节点后新的二分搜索树的根
  removeMin: function (root) {
    if (root.left === null) {
      let rightNode = root.right
      delete root
      this.count--
      return rightNode
    }
    root.left = this.removeMin(root.left)
    return root
  },
  // 删除掉以 root 为根的二分搜索树中的最大节点
  // 返回删除节点后新的二分搜索树的根
  removeMax: function (root) {
    if (root.right === null) {
      let leftNode = root.left
      delete root
      this.count--
      return leftNode
    }
    root.right = this.removeMax(root.right)
    return root
  },
  // 删除掉以 root 为根的二分搜索树中键值为 key 的节点
  // 返回删除节点后新的二分搜索树的根
  remove: function (root, key) {
    if (root === null ) {
      return null
    }
    if( key < root.key) {
      root.left = this.remove(root.left, key);
      return root;
    } else if (key > root.key){
      root.right = this.remove(root.right, key);
      return root;
    } else {  // key === root.key
      if(root.left === null){
        let rightNode = root.right;
        delete root;
        this.count--;
        return rightNode;
      }
      if(root.right === null) {
        let leftNode = root.left;
        delete root;
        this.count--;
        return leftNode;
      }
      // root.left !== null && root.right !== null
      // 二叉搜索树中序遍历序列的下一个节点。即比当前节点大的最小节点，简称后继节点
      // 这里就是获取后继节点替代当前删除的节点，
      // 先取当前节点的右节点，然后一直取该节点的左节点，直到左节点为空，则最后指向的节点为后继节点。
      // 这里再解释以下前驱节点：二叉搜索树中序遍历序列的前一个节点。
      // 即比当前节点小的最大节点，简称前驱节点。
      // 先取当前节点的左节点，然后取该节点的右节点，直到右节点为空，则最后指向的节点为前驱节点。
      let successor = new this.TreeNode(this.minimum(root.right));
      this.count++;
      successor.right = this.removeMin(root.right);
      successor.left = root.left;

      delete root;
      this.count--;

      return successor;
    }
  }
}


// 创建一个元素为20个的二叉搜索树
for (let i = 0; i < 20; i++) {
  let randVal = parseInt(Math.random()*1000+1)
  // 为了后续测试方便,这里value值取和key值一样
  BST.root = BST.insert(BST.root, randVal, randVal)
}
console.log(BST.root)

注释都写在方法上，有兴趣的童鞋可以自己复制代码，调用测试以下~