前言
上篇二分搜索树的文章中，认识了树这种高效的结构，对递归也有更深层次的认识，也体会到了二分搜索树前中后序递归遍历的思想，也就是深度优先遍历。二分搜索树的遍历，对每一个节点都有三次的访问机会。前序遍历访问节点都是在第一个访问机会的位置才去访问节点，中序遍历访问节点都是在第二个访问机会的位置才去访问节点，后序遍历访问节点都是在第三个访问机会的位置才去访问节点。
接下来开始认识一下树遍历非递归的思想，也就是层序遍历(广度优先遍历)。还有删除树节点以及更多二分搜索树的feature。
还是那句老话：光看文章能够掌握两成，动手敲代码、动脑思考、画图才可以掌握八成。源码仓库
不要完美主义。掌握好“度”。
太过于追求完美会把自己逼的太紧，会产生各种焦虑的心态，最后甚至会怀疑自己，温故而知新，不要停止不前，掌握好这个度，不存在你把那些你认为完全掌握了，然后就成了某一个领域的专家，相反一旦你产生很浓厚的厌恶感，那么就意味着你即将会放弃或者已经选择了放弃，虽然你之前想把它做到 100 分，但是由于你的放弃让它变为 0 分。
学习本着自己的目标去。不要在学的过程中偏离了自己的目标。要分清主次。
难的东西，你可以慢慢的回头看一看。那样才会更加的柳暗花明，更能提升自己的收获。
二分搜索树的遍历-非递归写法
前序遍历的递归写法
前序遍历是最自然的一种遍历方式，同时也是最常用的一种遍历方式，如果没有特殊情况的话，在大多数情况下都会使用前序遍历。先访问这个节点，然后访问这个节点的左子树，再访问这个节点的右子树，整个过程循环往复。前序遍历的前表示先访问的这个节点。
function preOrder(node) {
if (node == null) return;
// ... 要做的事情
// 访问该节点
// 先一直往左，然后不断返回上一层 再向左、终止，
// 最后整个操作循环往复，直到全部终止。
preOrder(node.left);
preOrder(node.right);
}前序遍历的非递归写法
使用另外一个数据结构栈来模拟递归调用时的系统栈。先访问根节点，将根节点压入栈，然后把栈顶元素拿出来，对这个节点进行操作。
这个节点操作完毕之后，再访问这个节点的两个子树，也就是把这个节点的左右两个孩子压入栈中，压入栈的顺序是先压入右孩子、再压入左孩子。
这是因为栈是后入先出的，所以要先压入后续要访问的那个节点，再让栈顶的元素出栈，对这个节点进行操作，这个节点操作完毕之后，再访问这个节点的两个子树。
但是这个节点是叶子节点，它的两个孩子都为空，那么什么都不用压入了，再去取栈顶的元素，对这个节点进行操作。
这个节点操作完毕之后，再访问这个节点的两个子树，但是这个节点也是叶子节点，那么什么都不用压入了，栈中也为空了，整个访问操作结束。
无论是非递归还是递归的写法，结果都是一致的，非递归的写法中，栈的应用是帮助你记录你下面要访问的哪些节点，这个过程非常像使用栈模拟了一下在系统栈中相应的一个调用，相当于在系统栈中记录下一步依次要访问哪些节点。
将递归算法转换为非递归算法，是栈这种数据结构非常重要的一种应用。
二分搜索树遍历的非递归实现比递归实现复杂很多，因为你使用了一个辅助的数据结构才能完成这个过程，使用了栈这种数据结构模拟了系统调用栈，在算法语意解读上远远比递归实现的算法语意解读要难很多。
二分搜索树的中序遍历和后序遍历的非递归实现更复杂，尤其是对于后序遍历来说难度更大，但是中序遍历和后序遍历的非递归实现，实际应用并不广泛。
但是你可以尝试实现中序、后序遍历的非递归实现，主要是锻炼你算法实现、思维逻辑实现思路。在解决这个问题的过程中可能会遇到一些困难，可以通过查看网上的资料来解决这个问题，这样的问题有可能会在面试题及考试中出现，也就是中序和后序遍历相应的非递归实现。
在经典的教科书中一般都会有这三种遍历的非递归实现，通过二分搜索树的前序遍历非递归的实现方式中可以看出，完全可以使用模拟系统的栈来完成递归转成非递归这样的操作。
在慕课上 有一门课《玩转算法面试》中完全模拟了系统栈的写法，也就是将前中后序的遍历都转成了非递归的算法，这与经典的教科书上的实现不一样，但是这种方式对你进一步理解栈这种数据结构还是二分搜索树的遍历甚至是系统调用的过程都是很有意义的。
对于前序遍历来说无论是递归写法还是非递归写法，对于这棵树来说都是在遍历的过程中一直到底，这样的一种遍历方式也叫深度优先遍历，最终的遍历结果都会先来到整颗树最深的地方，直到不能再深了才会开始返回到上一层，所以这种遍历就叫做深度优先遍历。与深度优先遍历相对应的就是广度优先遍历，广度优先遍历遍历出来的结果它的顺序其实是整个二分搜索树的一个层序遍历的顺序。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5, 3, 6, 8, 4, 2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
this.alterLine('MyBinarySearchTree PreOrder Area');
myBinarySearchTree.preOrder(this.show);
this.alterLine('MyBinarySearchTree NonRecursivePreOrder Area');
myBinarySearchTree.nonRecursivePreOrder(this.show);
this.alterLine('MyBinarySearchTree InOrder Area');
myBinarySearchTree.inOrder(this.show);
this.alterLine('MyBinarySearchTree PostOrder Area');
myBinarySearchTree.postOrder(this.show);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};二分搜索树的层序遍历
二分搜索树的 前序、中序、后序遍历，它们本质上都是深度优先遍历。
对于二分搜索树来说每一个节点都有一个相应的深度的值，根节点作为深度为 0 相应的节点，有一些教科书 会把根节点作为深度为 1 相应的节点，如果以计算机世界里索引的定义为准那就是使用 0，根节点就是第 0 层。
先遍历第 0 层、再遍历第 1 层、再遍历下一层，这样的一层一层的遍历就称为广度优先遍历，逐层向下遍历的节点在广度上进行拓展，这样的一个遍历顺序就叫做层序遍历、广度优先遍历，而不像之前那样 先顺着一个枝杈向着最深的地方走。
对于层序遍历的实现或者广度优先遍历的实现，通常不是使用递归的方式进行实现的，而是使用非递归的方式进行实现的，并且在其中需要使用另外的一个数据结构队列，从根节点开始排着队的进入这个队列，队列中存储的就是待遍历的元素，每一次遍历的它的元素之后再将它的左右孩子也排进队列中，整个过程依此类推。
先入队根节点，然后看队首是否有元素，有的话就对队首的元素进行操作，操作完毕后就将操作完毕的元素的左右孩子也入队，然后再对队列中的元素进行操作，队列中的元素又操作完毕了，再让操作完毕的这些元素的左右孩子入队，最后在对队列中的元素进行操作，这些元素都是叶子节点没有左右孩子了，，不用入队了，队列中没有元素，整个过程处理完毕，这个处理过程就是一层一层的进行处理的一个顺序，这就是二分搜索树的广度优先遍历，也叫层序遍历。
相对于深度优先遍历来说，广度优先遍历的优点是它能更快的找到你想要查询的那个元素，这样的区别主要用于搜索策略上，而不是用在遍历这个操作上，虽然遍历要将整个二叉树上所有的元素都访问一遍，这种情况下深度优先遍历和广度优先遍历是没有区别的。
但是如果想在一棵树中找到某一个问题的解，那对于深度优先遍历来说它会从根节点一股脑的跑到这棵树非常深的地方，但是很有可能这个问题的解并不在那么深的地方而是很浅的地方，这样一来深度优先遍历要花很长时间才能访问到这个很浅的地方。
例如前序遍历，如果这个问题的解在右子树上很浅的位置，你从一开始就从根节点遍历到左子树的最深处，那就没必要了，但是这个常用于算法设计中。如无权图的最短路径，树这种结构在算法设计里也有非常重要的应用，尤其是很多时候设计出一个算法，可能真正不需要把这个树发现出来，但是这个算法的整个过程就是在一棵虚拟的树中完成的。
在图中也是有深度优先遍历和广度优先遍历的，在树中和图中进行深度优先遍历其实它们的实质是一样的，不同的点，对于图来说需要记录一下对于某一个节点之前是否曾经遍历过，因为对于图来说每一个节点的前驱或者放在树这个模型中相应的术语就是每一节点它的父亲可能有多个，从而产生重复访问这样的问题，而这样的问题在树结构中是不存在的，所以在图结构中需要做一个相应的记录。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 层序遍历
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while (!queue.isEmpty()) {
node = queue.dequeue();
operator(node.element);
console.log(node.element);
// 队列 是先进先出的，所以从左往右入队
// 栈 是后进先出的， 所以从右往左入栈
if (node.left !== null) queue.enqueue(node.left);
if (node.right !== null) queue.enqueue(node.right);
}
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Area');
let myBinarySearchTree = new MyBinarySearchTree();
let nums = [5, 3, 6, 8, 4, 2];
for (var i = 0; i < nums.length; i++) {
myBinarySearchTree.add(nums[i]);
}
/////////////////
// 5 //
// / \ //
// 3 6 //
// / \ \ //
// 2 4 8 //
/////////////////
this.alterLine('MyBinarySearchTree PreOrder Area');
myBinarySearchTree.preOrder(this.show);
this.alterLine('MyBinarySearchTree NonRecursivePreOrder Area');
myBinarySearchTree.nonRecursivePreOrder(this.show);
this.alterLine('MyBinarySearchTree InOrder Area');
myBinarySearchTree.inOrder(this.show);
this.alterLine('MyBinarySearchTree PostOrder Area');
myBinarySearchTree.postOrder(this.show);
this.alterLine('MyBinarySearchTree LevelOrder Area');
myBinarySearchTree.levelOrder(this.show);
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};学习方法小结
很多时候学习知识，并不是简单的一块儿一块儿把它们学过了就可以了，很多时候要想能够达到灵活运用能够达到理解的深刻，都需要进行比对，刻意的去找到从不同方法之间它们的区别和联系，以及自己去总结不同的方法适用于什么样的场合。只有这样，这些知识才能够在你的脑海中才不是一个一个的碎片，而是有机的联系起来的，面对不同的问题才能非常的快的并且准确的说出来用怎样的方法去解决更加的好。
二分搜索树的删除节点-删除最大最小值
对于二分搜索树来说删除一个节点相对来说是比较复杂的，可以先对这个操作进行拆解，从最简单的开始。
删除二分搜索树的最小值和最大值，删除二分搜索树中任意元素会复用到删除二分搜索树最大值和最小值相应的逻辑。要想删除二分搜索树中最大值和最小值，那么就要先找到二分搜索树中的最大值和最小值。
找到二分搜索树中的最大值和最小值是非常容易的，每一个节点的左子树上所有的节点的值都小于当前这个节点，每一个节点的右子树上所有的节点的值都大于当前这个节点，那么从根节点开始一直向左，直到不能再左了，就能找到最小值，反之从根节点开始一直向右，直到不能再右了，就能找到最大值。这个操作就像操作链表一样，就像是在找一条链上的尾节点。
删除最大元素节点，要删除最大元素的这个节点可能有左孩子节点但是没有右孩子节点，所以可能会导致无法继续向右于是递归就终止了，那么这个时候删除这个节点可以采用当前节点的左孩子替代当前这个节点，覆盖操作也算是删除了当前这个节点了。如果你想返回被删除的这个最大元素节点，你可以先查询出这个最大的元素节点，然后存到一个变量中，最后再调用删除这个最大元素节点的方法，最终返回存的这个变量。
删除最小元素节点，要删除的最小元素的节点可能有右孩子节点但是没有左孩子节点，会导致无法继续向左而递归终止，你不能删除这个节点的同时连右孩子一起删除，所以这个时候删除这个节点可以采用当前节点的右孩子替代当前这个节点，覆盖操作也算是删除了当前这个节点了。其它的和删除最大元素一样，先查询出来，然后存起来，删除这个最大元素后，再返回之前存起来的最大元素的变量。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 找到二分搜索树中的最大值的元素 +
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// 找到二分搜索树中的最大值的元素的节点 递归算法 -
recursiveMaximum(node) {
// 解决最基本的问题 向右走再也走不动了，说明当前节点就是最大值节点。
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMax(node) {
if (node.right === null) {
// 先存 当前这个节点的左子树，
// 因为可能当前这个节点仅仅没有右子树，只有左子树，
// 那么左子树可以替代当前这个节点。
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// 找到二分搜索树中的最小值 +
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// 找到二分搜索树中的最小值的元素的节点 递归算法 -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMin(node) {
// 解决最简单的问题
if (node.left == null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 将复杂的问题拆分为性质相同的小问题，
// 然后求出这些小问题的解后构建出原问题的答案
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 层序遍历
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while (!queue.isEmpty()) {
node = queue.dequeue();
operator(node.element);
console.log(node.element);
// 队列 是先进先出的，所以从左往右入队
// 栈 是后进先出的， 所以从右往左入栈
if (node.left !== null) queue.enqueue(node.left);
if (node.right !== null) queue.enqueue(node.right);
}
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTree remove Min Node Area');
{
let tree = new MyBinarySearchTree();
let n = 100;
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
}
let array = new MyArray(n);
while (!tree.isEmpty()) {
array.add(tree.removeMin());
}
// 数组中的元素从小到大排序的
console.log(array.toString());
for (var i = 1; i < n; i++) {
//如果数组后面的元素小于数组前面的元素
if (array.get(i) < array.get(i - 1))
throw new Error(
'error. array element is not (small - big) sort.'
);
}
console.log('removeMin test completed.');
this.show('removeMin test completed.');
}
this.alterLine('MyBinarySearchTree remove Max Node Area');
{
let tree = new MyBinarySearchTree();
let n = 100;
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
}
let array = new MyArray(n);
while (!tree.isEmpty()) {
array.add(tree.removeMax());
}
// 数组中的元素从大到小排序的
console.log(array.toString());
for (var i = 1; i < n; i++) {
//如果数组后面的元素大于数组前面的元素
if (array.get(i) > array.get(i - 1))
throw new Error(
'error. array element is not (big - small) sort.'
);
}
console.log('removeMax test completed.');
this.show('removeMax test completed.');
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};二分搜索树的删除节点-删除任意元素
在二分搜索树种删除最大值最小值的逻辑，从根节点开始，向左或者向右遍历，遍历到最左或者最右时，记录这个节点的右子树或者左子树，然后返回。然后让这条分支上每个节点的左或者右子树进行层层覆盖，然后层层返回新的节点，直到最后返回给根节点、覆盖掉根节点，从而达到了删除最小或最大节点的目的。
删除最小值的节点就不停的向左遍历，最后记录右子树，因为被删除的节点要被这个节点的右子树替代掉，只有这样才能够达到删除最小值的节点的效果。删除最大值的节点就不停的向右遍历，最后记录左子树，因为被删除的节点要被这个节点的左子树替代掉，只有这样才能够达到删除最大值的节点的效果。
删除二分搜索树上任意节点会发生的情况，删除的这个节点只有左孩子，这个逻辑和上面的类似，就让这个节点的左孩子取代这个节点的位置。
删除的这个节点只有右孩子，这个逻辑也是一样，就让这个节点的右孩子取代这个节点的位置。删除的这个节点是叶子节点，这个逻辑也一样，因为 null 也是一个二分搜索树、也是一个节点、也是一个孩子，直接让 null 取代这个节点的位置即可。
真正难的地方是去删除左右都有孩子这样的节点，在 1962 年，Hibbard(计算机科学家)提出-Hibbard Deletion，找到离这个节点的值最近并且大的那个节点来取代这个节点，也就是找到 这个节点的右孩子的左孩子(右子树的左子树上最小的节点)。
例如待删除的节点为 d，那么就是 s = min(d->right)，找到比当前节点大最小且最近的节点，这个 s 就是 d 的后继，执行 s->right = delMin(d->right)这样的操作，之后让 s->left = d->left，删除的 d 后，s 是新的子树的根，返回这个 s 节点就可以了。
除了找待删除节点 d 的后继 s 之外，还可以找待删除节点的前驱 p，也就是找到 这个节点的左孩子的右孩子(左子树的右子树上最大的节点)。无论使用前驱还是后继来取代待删除的这个节点都能够继续保持二分搜索树的性质。
对于二分搜索树来说，相对于数组、栈、队列、链表这些数据结构要复杂一些，二分搜索树本身也是学习其它的树，如 平衡二叉树的基础。
代码示例
(class: MyBinarySearchTree, class: Main)
MyBinarySearchTree
// 自定义二分搜索树节点
class MyBinarySearchTreeNode {
constructor(element, left = null, right = null) {
// 实际存储的元素
this.element = element;
// 当前节点的左子树
this.left = left;
// 当前节点的右子树
this.right = right;
}
}
// 自定义二分搜索树
class MyBinarySearchTree {
constructor() {
this.root = null;
this.size = 0;
}
// 添加元素到二分搜索树中 +
add(element) {
if (element === null) throw new Error("element is null. can't store.");
this.root = this.recursiveAdd(this.root, element);
}
// 添加元素到二分搜索树中 递归算法 -
recursiveAdd(node, newElement) {
// 解决最基本的问题 也就是递归函数调用的终止条件
if (node === null) {
this.size++;
return new MyBinarySearchTreeNode(newElement);
}
// 1. 当前节点的元素比新元素大
// 那么新元素就会被添加到当前节点的左子树去
// 2. 当前节点的元素比新元素小
// 那么新元素就会被添加到当前节点的右子树去
// 3. 当前节点的元素比新元素相等
// 什么都不做了，因为目前不添加重复的元素
if (this.compare(node.element, newElement) > 0)
node.left = this.recursiveAdd(node.left, newElement);
else if (this.compare(node.element, newElement) < 0)
node.right = this.recursiveAdd(node.right, newElement);
else {
}
// 将复杂问题分解成多个性质相同的小问题，
// 然后求出小问题的答案，
// 最终构建出原问题的答案
return node;
}
// 判断二分搜索树中是否包含某个元素 +
contains(element) {
if (this.root === null) throw new Error("root is null. can't query.");
return this.recursiveContains(this.root, element);
}
// 判断二分搜索树种是否包含某个元素 递归算法 -
recursiveContains(node, element) {
if (node === null) return false;
// 当前节点元素比 要搜索的元素 大
if (this.compare(node.element, element) > 0)
return this.recursiveContains(node.left, element);
else if (this.compare(node.element, element) < 0)
// 当前元素比 要搜索的元素 小
return this.recursiveContains(node.right, element);
// 两个元素相等
else return true;
}
// 找到二分搜索树中的最大值的元素 +
maximum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMaximum(this.root).element;
}
// 找到二分搜索树中的最大值的元素的节点 递归算法 -
recursiveMaximum(node) {
// 解决最基本的问题 向右走再也走不动了，说明当前节点就是最大值节点。
if (node.right === null) return node;
return this.recursiveMaximum(node.right);
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点的元素 +
removeMax() {
let maxElement = this.maximum();
this.root = this.recursiveRemoveMax(this.root);
return maxElement;
}
// 删除二分搜索树中最大值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMax(node) {
if (node.right === null) {
// 先存 当前这个节点的左子树，
// 因为可能当前这个节点仅仅没有右子树，只有左子树，
// 那么左子树可以替代当前这个节点。
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
node.right = this.recursiveRemoveMax(node.right);
return node;
}
// 找到二分搜索树中的最小值 +
minimum() {
if (this.size === 0) throw new Error('binary search tree is empty.');
return this.recursiveMinimum(this.root).element;
}
// 找到二分搜索树中的最小值的元素的节点 递归算法 -
recursiveMinimum(node) {
if (node.left === null) return node;
return this.recursiveMinimum(node.left);
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点的元素 +
removeMin() {
let leftNode = this.minimum();
this.root = this.recursiveRemoveMin(this.root);
return leftNode;
}
// 删除二分搜索树中最小值的元素的节点，并返回这个节点 递归算法 -
recursiveRemoveMin(node) {
// 解决最简单的问题
if (node.left == null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 将复杂的问题拆分为性质相同的小问题，
// 然后求出这些小问题的解后构建出原问题的答案
node.left = this.recursiveRemoveMin(node.left);
return node;
}
// 删除二分搜索树上的任意节点
remove(element) {
this.root = this.recursiveRemove(this.root, element);
}
// 删除二分搜索树上的任意节点 递归算法
// 返回删除对应元素节点后新的二分搜索树的根
recursiveRemove(node, element) {
if (node === null) return null;
// 当前节点的元素值比待删除的元素小 那么就向当前节点的右子树中去找
if (this.compare(node.element, element) < 0) {
node.right = this.recursiveRemove(node.right, element);
return node;
} else if (this.compare(node.element, element) > 0) {
// 向当前节点的左子树中去找
node.left = this.recursiveRemove(node.left, element);
return node;
} else {
// 如果找到了相同值的节点了，开始进行相应的处理
// 如果这个节点左子树为空，那么就让这个节点的右子树覆盖当前节点
if (node.left === null) {
let rightNode = node.right;
node.right = null;
this.size--;
return rightNode;
}
// 如果当前节点的右子树为空，那么就让这个节点的左子树覆盖当前节点
if (node.right === null) {
let leftNode = node.left;
node.left = null;
this.size--;
return leftNode;
}
// 如果当前节点的左右子树都不为空，那么就开始特殊操作
// 1. 先找到当前节点右子树上最小的那个节点，保存起来
// 2. 然后删除掉当前节点右子树上最小的那个节点，
// 3. 让保存起来的那个节点覆盖掉当前节点
// 1. 也就是保存起来的那个节点的right = 删除掉当前节点右子树上最小的节点后返回的那个节点
// 2. 再让保存起来的那个节点的left = 当前节点的left
// 4. 解除当前节点及其left和right，全都赋值为null，这样就相当于把当前节点从二分搜索树中剔除了
// 5. 返回保存的这个节点
let successtor = this.recursiveMinimum(node.right);
successtor.right = this.recursiveRemoveMin(node.right);
// 恢复removeMin 操作的this.size -- 带来的影响
this.size++;
successtor.left = node.left;
// 开始正式的删除当前节点的操作
node = node.left = node.right = null;
this.size--;
// 返回当前保存的节点
return successtor;
}
}
// 前序遍历 +
preOrder(operator) {
this.recursivePreOrder(this.root, operator);
}
// 前序遍历 递归算法 -
recursivePreOrder(node, operator) {
if (node === null) return;
// 调用一下操作方法
operator(node.element);
console.log(node, node.element);
// 继续递归遍历左右子树
this.recursivePreOrder(node.left, operator);
this.recursivePreOrder(node.right, operator);
}
// 前序遍历 非递归算法 +
nonRecursivePreOrder(operator) {
let stack = new MyLinkedListStack();
stack.push(this.root);
let node = null;
while (!stack.isEmpty()) {
// 出栈操作
node = stack.pop();
operator(node.element); // 访问当前的节点
console.log(node.element);
// 栈是先入后出的，把需要后访问的节点 先放进去，先访问的节点后放进去
// 前序遍历是访问当前节点，然后再遍历左子树，最后遍历右子树
if (node.right !== null) stack.push(node.right);
if (node.left !== null) stack.push(node.left);
}
}
// 中序遍历 +
inOrder(operator) {
this.recursiveInOrder(this.root, operator);
}
// 中序遍历 递归算法 -
recursiveInOrder(node, operator) {
if (node == null) return;
this.recursiveInOrder(node.left, operator);
operator(node.element);
console.log(node.element);
this.recursiveInOrder(node.right, operator);
}
// 后序遍历 +
postOrder(operator) {
this.recursivePostOrder(this.root, operator);
}
// 后序遍历 递归算法 -
recursivePostOrder(node, operator) {
if (node == null) return;
this.recursivePostOrder(node.left, operator);
this.recursivePostOrder(node.right, operator);
operator(node.element);
console.log(node.element);
}
// 层序遍历
levelOrder(operator) {
let queue = new MyLinkedListQueue();
queue.enqueue(this.root);
let node = null;
while (!queue.isEmpty()) {
node = queue.dequeue();
operator(node.element);
console.log(node.element);
// 队列 是先进先出的，所以从左往右入队
// 栈 是后进先出的， 所以从右往左入栈
if (node.left !== null) queue.enqueue(node.left);
if (node.right !== null) queue.enqueue(node.right);
}
}
// 获取二分搜索树中节点个数 +
getSize() {
return this.size;
}
// 返回二分搜索树是否为空的bool值 +
isEmpty() {
return this.size === 0;
}
// 新增一个比较的方法，专门用来比较新增的元素大小 -
// 第一个元素比第二个元素大 就返回 1
// 第一个元素比第二个元素小 就返回 -1
// 第一个元素比第二个元素相等 就返回 0
compare(elementA, elementB) {
if (elementA === null || elementB === null)
throw new Error("element is null. can't compare.");
// 先直接写死
if (elementA > elementB) return 1;
else if (elementA < elementB) return -1;
else return 0;
}
// 输出二分搜索树中的信息
// @Override toString 2018-11-03-jwl
toString() {
let treeInfo = '';
treeInfo += this.getBinarySearchTreeString(this.root, 0, treeInfo);
return treeInfo;
}
// 写一个辅助函数，用来生成二分搜索树信息的字符串
getBinarySearchTreeString(node, depth, treeInfo, pageContent = '') {
//以前序遍历的方式
if (node === null) {
treeInfo += this.getDepthString(depth) + 'null \r\n';
pageContent = this.getDepthString(depth) + 'null<br /><br />';
document.body.innerHTML += `${pageContent}`;
return treeInfo;
}
treeInfo += this.getDepthString(depth) + node.element + '\r\n';
pageContent =
this.getDepthString(depth) + node.element + '<br /><br />';
document.body.innerHTML += `${pageContent}`;
treeInfo = this.getBinarySearchTreeString(
node.left,
depth + 1,
treeInfo
);
treeInfo = this.getBinarySearchTreeString(
node.right,
depth + 1,
treeInfo
);
return treeInfo;
}
// 写一个辅助函数，用来生成递归深度字符串
getDepthString(depth) {
let depthString = '';
for (var i = 0; i < depth; i++) {
depthString += '-- ';
}
return depthString;
}
}Main
// main 函数
class Main {
constructor() {
this.alterLine('MyBinarySearchTree Remove Node Area');
{
let n = 100;
let tree = new MyBinarySearchTree();
let array = new MyArray(n);
let random = Math.random;
for (var i = 0; i < n; i++) {
tree.add(n * n * n * random());
array.add(tree.removeMin());
}
// 数组中的元素从小到大排序的
console.log(array.toString());
for (var i = 0; i < n; i++) {
tree.remove(array.get(i));
}
console.log(
'removeMin test ' +
(tree.isEmpty() ? 'completed.' : 'no completed.')
);
this.show(
'removeMin test ' +
(tree.isEmpty() ? 'completed.' : 'no completed.')
);
}
}
// 将内容显示在页面上
show(content) {
document.body.innerHTML += `${content}<br /><br />`;
}
// 展示分割线
alterLine(title) {
let line = `--------------------${title}----------------------`;
console.log(line);
document.body.innerHTML += `${line}<br /><br />`;
}
}
// 页面加载完毕
window.onload = function() {
// 执行主函数
new Main();
};总结
目前已经实现了对二分搜索树进行 添加元素 add、删除元素 remove、查询元素 contains、遍历元素 order的功能。
其实还有其它的一些二分搜索树的功能。
比如可以非常方便的拿到二分搜索树中最大值和最小值，这是因为二分搜索树本身有一个非常重要的特性，也就是二分搜索树具有顺序性，这个顺序性就是指 二分搜索树中所有的元素都是有序的，例如使用中序遍历遍历的元素就是将元素从小到大排列起来，也正是有顺序性才能够很方便的获得二分搜索树中最大值(maximum)最小值(minimum)，包括给定一个值可以拿到它的前驱(predecessor)和后继(successor)。
也因为这个顺序性也可以对它进行 floor 和 ceil 的操作，也就是找比某一个元素值大的元素或者值小的元素，前驱、后继中指定的元素一定要在这棵二分搜索树中，而 floor 和 ceil 中指定的这个元素可以不在这棵二分搜索树中。
相应的二分搜索树还可以实现 rank 和 select 方法，rank 也就是指定一个元素找到它的排名，select 是一个反向的操作，也就是找到排名为多少名的那个元素。对于二分搜索树来说都可以非常容易的实现这两个操作。
实现 rank 和 select 最好的方式是对于二分搜索树每一个节点同时还维护一个 size，这个 size 就是指以这个节点为根的二分搜索树有多少个元素，也就是每一个节点为根的二分搜索树中有多少的元素，那么这个 size 就为多少，也就是每一个节点包括自己以及下面的子节点的个数。
每一个 node 在维护了一个 size 之后，那么实现 rank 和 select 这两个操作就会容易很多，也就是给 node 这个成员变量添加一个 size，那么对于二分搜索树其它操作如添加和删除操作时，也要去维护一下这个节点的 size，只有这样实现这个 rank 和 select 就会非常简单。
这样做之后，对于整棵二分搜索树而言，就不再需要二分搜索树的 size 变量了，如果要看整棵二分搜索树有多少个节点，直接看root.size就好了，非常的方便。
维护 depth 的二分搜索树，对于二分搜索树的每一个节点还可以维护一个深度值，也就是这个节点的高度值，也就是这个节点处在第几层的位置，维护这个值在一些情况下是非常有帮助的。
支持重复元素的二分搜索树，只需要定义每一个根节点的左子树所有的节点都是小于等于这个根节点值的，而每一个根节点的右子树所有的节点都是大于这个根节点值的，这样的定义就很好的支持了重复元素的二叉树的实现。
还可以通过维护每一个节点的 count 变量来实现重复元素的二分搜索树，也就是记录一下这个节点所代表的元素在这个二分搜索树中存储的个数，当你添加进重复的节点后，直接让相应节点的count++即可，如果你删除这个重复的节点时，直接让相应节点的count--即可，如果 count 减减之后为 0，那么就从二分搜索树中真正删除掉。
其它
在二分搜索树中相应的变种其实大多是在 node 中维护一些数据，就可以方便你进行一些其它特殊情况的处理。相关的习题可以去 leetcode 中找到，树标签：https://leetcode-cn.com/tag/tree/。如第一题，二叉树的最大深度，这个题和链表是非常像的，它有一个答题的模板，你提交的时候要按照这个模板来进行提交。
二分搜索树的复杂度分析，二分搜索树有两个重要的应用集合和映射，其实用数组和链表也能够实现集合和映射，不过二分搜索树也有它的局限性。
