JavaScript实现数据结构中的二叉搜索树
共 5055字，需浏览 11分钟
· 2021-01-17
二叉树中的节点最多只能有两个子节点：左侧节点 and 右侧节点，这样定义有助于我们写出更高效的在树中插入，查找，删除节点的算法。
二叉搜索树（BST）是二叉树的一种，但是 只允许你在左侧节点存储比`父节点`小的值 ， 右侧节点存储比`父节点`大的值 ；如下图：
重点
我在写二叉树的时候有个疑惑，他是如果插入的呢？为什么有的在坐标有的在右边。
答：其实可以看上图图上面那一样，
先插入11，
第一次插入7，由于小于11放到左边
第二次插入5，比11小，又比7小，然后放到7的左侧
第三次插入15，比11大放到右侧
依次类推
我 想如果你看到这里，结合上面 左侧小于父节点，右侧大于父节点 这句话。一定知道怎么放了；⛽️
树的遍历
遍历一棵树🌲直指范围书上的每个节点并对他们进行某种操作的过程。访问树的所有节点有三种方式：中序，先序。
中序遍历
中序遍历是一种已上行顺序访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。是一种对树进行排序操作
// 中序遍历inOrderTraverse(callback){this.inOrderTraverseNode(this.root,callback);}inOrderTraverseNode(node,callback){// 停止递归的条件if(node !== null){// 通过栈先把所有小的都放到栈里面// 先遍历左测 小节点this.inOrderTraverseNode(node.left,callback);callback(node.key);// 后遍历右测 大节点this.inOrderTraverseNode(node.right,callback)}}const b = new BinarySearchTree();b.inOrderTraverse((value) => console.log(value)) //3 5 6 7 8 9 9 10 ...
中序 寻找规则图示
先序遍历
先序遍历是以优先于后代节点的顺序访问每个节点的，先序遍历的一种应用是打印一个结构化的文档。
先序遍历会访问节点本身，然后在访问他的左侧子节点，最后反问右侧子节点。
// 先序遍历perOrderTraverse(callback){this.perOrderTraverseNode(this.root,callback);}perOrderTraverseNode(node,callback){if(node !== null){callback(node.key);this.perOrderTraverseNode(node.left,callback);this.perOrderTraverseNode(node.right,callback);}}b.perOrderTraverse((value) => console.log(value)) // 11 7 5 3 6 9 8 10 15 13 ...
先序 寻找规则图示
后序排序
后续遍历是先访问节点的后代节点，再访问节点本身。后续遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小；
// 后续排序postOrderTraverse(callback){this.postOrderTraverseNode(this.root,callback);}postOrderTraverseNode(node,callback){if(node !== null){this.postOrderTraverseNode(node.left,callback)this.postOrderTraverseNode(node.right,callback)callback(node.key)}}b.postOrderTraverse((value) => console.log(value)) // 3 6 5 8 10 9 7 12 14 ...
后序 寻找规则图示
搜索树的中值
搜索最大值和最小值
使用肉眼可以直观找到树的最大值和最小值。最小值在最末端左侧，最大值在最末端右侧；
查找最小值，递归遍历left节点，因为左侧节点是最小的，遍历到最下面一个就是最小的值然后返回；遍历最大值同理，遍历right 右侧节点即可
// 查找最小值min(){return this.minNode(this.root);}minNode(node){while(node !== null && node.left !== null){node = node.left;}return node.key;}// 查找最大值max(){return this.maxNode(this.root)}maxNode(node){while(node !== null && node.right !== null){node = node.right;}return node.key}
搜索一个特定的值
寻找一棵树或其任意子树中的一个特定的值。
// 搜索一个特定的值search(key) {return this.searchNode(this.root, key)}searchNode(node, key) {if (node === null) return false;let result = this.defaultCompare(key, node.key)if (result === -1) {return this.searchNode(node.left, key);} else if (result === 1) {return this.searchNode(node.right, key)} else {return true;}}console.log(b.search(1)); // falseconsole.log(b.search(8)); // true
移除指定节点
注意⚠️：这里的移除节点返回的是移除完节点后的树，而不是返回移除完的值（我在这里绕了半天，因为没有仔细看返回值～～）
// 移除 节点返回一个新的root树，而不是返回移除的节点值remove(key) {this.root = this.removeNode(this.root, key);}removeNode(node, key) {if (node === null) return false;// key 比 当前节点小if (this.defaultCompare(key, node.key) === -1) {node.left = this.removeNode(node.left, key)return node;} else if (this.defaultCompare(key, node.key) === 1) {// key 比当前节点大node.right = this.removeNode(node.right, key);return node;} else {// { 1 } 情况1: 移除没有左右叶的节点if (node.let === null && node.right === null) {node = null;return node;}// { 2 } 情况2：移除只存在 左叶或右叶的 节点if (node.left === null) {node = node.left; // null 赋值给当前节点表示移除return node;} else if (node.right === null) {node = node.right // null 赋值给当前节点表示移除return node;}// { 3 } 情况3：移除有两个子节点的节点const aux = this.minNode(node.right); // 找到右侧最小节点node.key = aux.key; // 最小节点更新 要移除的这个节点node.right = this.removeNode(node.right, aux.key); // 移除掉原来位置的值return node;}}
移除没有左右叶的节点
见代码 { 1 }，判断当前节点的左叶或右叶是否都是null，如果是的话，把当前节点赋值给null（移除当前节点）；
移除存有左侧或右侧节点的节点
见代码{ 2 }，先判断左侧或右侧节点是否为null，如果是的话，跳过这个节点，直接将父节点指针指向子节点。（不存在的这个节点肯定是null，null 赋值给当前节点表示删除）
移除的节点存在两子节点
见代码{ 3 }，要移除的这个节点下面有两个节点。注⚠️：只是移除存在两个节点的这个节点，不移除当前节点下面的两个子节点；
先找到右边节点下的
最小的节点，因为父｜祖父节点一定比右侧小，左侧大。所有要找到最小节点；找到右侧最小节点的值，去更新要移除的这个节点的值。也就是移除掉了要移除的值，把比左侧大 右侧小的值，推上了被替换掉的这个值的位置。
此时存在两个相同的节点（第一条这个值），第一个在原来节点，第二个在替换掉的那个值的位置。所以要把它原来位置的值删掉，保证树中不存在两个相同的值；
返回树
完整代码见 https://github.com/qdwds/data-structure/blob/master/src/binarySearchTree/binarySearchTree.js
https://www.yuque.com/qdwds/uee630/qe52ca