二叉树中的节点最多只能有两个子节点：左侧节点 and 右侧节点，这样定义有助于我们写出更高效的在树中插入，查找，删除节点的算法。

二叉搜索树（BST）是二叉树的一种，但是 只允许你在左侧节点存储比父节点小的值 ， 右侧节点存储比父节点大的值 ；如下图：
未命名.png

重点

我在写二叉树的时候有个疑惑，他是如果插入的呢？为什么有的在坐标有的在右边。
答：其实可以看上图图上面那一样，

  • 先插入11，
  • 第一次插入7，由于小于11放到左边
  • 第二次插入5，比11小，又比7小，然后放到7的左侧
  • 第三次插入15，比11大放到右侧
  • 依次类推

我 想如果你看到这里，结合上面 左侧小于父节点，右侧大于父节点 这句话。一定知道怎么放了；⛽️

树的遍历

遍历一棵树🌲直指范围书上的每个节点并对他们进行某种操作的过程。访问树的所有节点有三种方式：中序，先序。

中序遍历

中序遍历是一种已上行顺序访问BST所有节点的遍历方式，也就是从最小到最大的顺序访问所有节点。是一种对树进行排序操作
执行循序：先执行左侧（递归使用栈数据结构）。先把大的值依次压入栈底 {1}，node为null {2} 时候依此弹出，继续执行{3},把右侧节点传入，在看右侧节点左侧是否存在 存在压入栈底 不存在在弹栈 以此类推。。。。

  1.     //  中序遍历
  2.     inOrderTraverse(callback){
  3.         this.inOrderTraverseNode(this.root,callback);
  4.     }
  5.     inOrderTraverseNode(node, callback) {
  6.         //  停止递归的条件      等于null的时候 栈执行 最后进去的小值
  7.         if (node !== null) {
  8.             //  从大到小 依次压入栈底
  9.             this.inOrderTraverseNode(node.left, callback);
  10.             //    最小值没有节点的时候 从最小值开始依次弹出
  11.             callback(node.key); //  弹栈
  12.             //  弹完后把右侧节点传入
  13.             this.inOrderTraverseNode(node.right, callback)
  14.         }
  15.     }
  17.     const b = new BinarySearchTree();
  18.     b.inOrderTraverse((value) => console.log(value))    //3 5 6 7 8 9 9 10 ...

中序 寻找规则图示

未命名.png

先序遍历

先序遍历是以优先于后代节点的顺序访问每个节点的，先序遍历的一种应用是打印一个结构化的文档。
先序遍历会访问节点本身，然后在访问他的左侧子节点，最后反问右侧子节点。

  1.     //  先序遍历
  2.     perOrderTraverse(callback){
  3.         this.perOrderTraverseNode(this.root,callback);
  4.     }
  5.     perOrderTraverseNode(node,callback){
  6.         if(node !== null){
  7.             callback(node.key);
  8.             this.perOrderTraverseNode(node.left,callback);
  9.             this.perOrderTraverseNode(node.right,callback);
  10.         }
  11.     }
  13.     b.perOrderTraverse((value) => console.log(value))   //  11 7 5 3 6 9 8 10 15 13 ...

先序 寻找规则图示

未命名.png

后序排序

后续遍历是先访问节点的后代节点，再访问节点本身。后续遍历的一种应用是计算一个目录及其子目录中所有文件所占空间的大小；

  1.     //  后续排序
  2.     postOrderTraverse(callback){
  3.         this.postOrderTraverseNode(this.root,callback);
  4.     }
  5.     postOrderTraverseNode(node,callback){
  6.         if(node !== null){
  7.             this.postOrderTraverseNode(node.left,callback)
  8.             this.postOrderTraverseNode(node.right,callback)
  9.             callback(node.key)
  10.         }
  11.     }
  13.     b.postOrderTraverse((value) => console.log(value))   //  3 6 5 8 10 9 7 12 14 ...

后序 寻找规则图示

未命名.png

搜索树的中值

搜索最大值和最小值

使用肉眼可以直观找到树的最大值和最小值。最小值在最末端左侧，最大值在最末端右侧；
min-max.png
查找最小值，递归遍历left节点，因为左侧节点是最小的，遍历到最下面一个就是最小的值然后返回；遍历最大值同理，遍历right 右侧节点即可

  1.     //  查找最小值
  2.     min(){
  3.         return this.minNode(this.root);
  4.     }
  5.     minNode(node){
  6.         while(node !== null && node.left !== null){
  7.             node = node.left;
  8.         }
  9.         return node.key;
  10.     }
  12.     //  查找最大值
  13.     max(){
  14.         return this.maxNode(this.root)
  15.     }
  16.     maxNode(node){
  17.         while(node !== null && node.right !== null){
  18.             node = node.right;
  19.         }
  20.         return node.key
  21.     }

搜索一个特定的值

寻找一棵树或其任意子树中的一个特定的值。

  1.     // 搜索一个特定的值
  2.     search(key) {
  3.         return this.searchNode(this.root, key)
  4.     }
  5.     searchNode(node, key) {
  6.         if (node === null) return false;
  8.         let result = this.defaultCompare(key, node.key)
  9.         if (result === -1) {
  10.             return this.searchNode(node.left, key);
  11.         } else if (result === 1) {
  12.             return this.searchNode(node.right, key)
  13.         } else {
  14.             return true;
  15.         }
  16.     }
  18.     console.log(b.search(1));    //    false
  19.     console.log(b.search(8));    //    true

移除指定节点

注意⚠️：这里的移除节点返回的是移除完节点后的树，而不是返回移除完的值（我在这里绕了半天，因为没有仔细看返回值～～）

  1.    //  移除 节点返回一个新的root树，而不是返回移除的节点值
  2.     remove(key) {
  3.         this.root = this.removeNode(this.root, key);
  4.     }
  5.     removeNode(node, key) {
  6.         if (node === null) return false;
  7.         //  key 比 当前节点小
  8.         if (this.defaultCompare(key, node.key) === -1) {
  9.             node.left = this.removeNode(node.left, key)
  10.             return node;
  11.         } else if (this.defaultCompare(key, node.key) === 1) {
  12.             //  key 比当前节点大
  13.             node.right = this.removeNode(node.right, key);
  14.             return node;
  15.         } else {
  16.             //  { 1 } 情况1: 移除没有左右叶的节点
  17.             if (node.let === null && node.right === null) {
  18.                 node = null;
  19.                 return node;
  20.             }
  21.             // { 2 } 情况2：移除只存在 左叶或右叶的 节点
  22.             if (node.left === null) {
  23.                 node = node.left;   //  null  赋值给当前节点表示移除
  24.                 return node;
  25.             } else if (node.right === null) {
  26.                 node = node.right   //  null  赋值给当前节点表示移除
  27.                 return node;
  28.             }
  30.             // { 3 }  情况3：移除有两个子节点的节点
  31.             const aux = this.minNode(node.right);   //  找到右侧最小节点
  32.             node.key = aux.key; //  最小节点更新 要移除的这个节点
  33.             node.right = this.removeNode(node.right, aux.key);  //  移除掉原来位置的值
  34.             return node;
  35.         }
  36.     }

移除没有左右叶的节点

见代码 { 1 }，判断当前节点的左叶或右叶是否都是null，如果是的话，把当前节点赋值给null（移除当前节点）；
null.png

移除存有左侧或右侧节点的节点

见代码{ 2 }，先判断左侧或右侧节点是否为null，如果是的话，跳过这个节点，直接将父节点指针指向子节点。（不存在的这个节点肯定是null，null 赋值给当前节点表示删除）right.png

移除的节点存在两子节点

见代码{ 3 }，要移除的这个节点下面有两个节点。注⚠️：只是移除存在两个节点的这个节点，不移除当前节点下面的两个子节点；

  • 先找到右边节点下的 最小的节点 ，因为父｜祖父节点一定比右侧小，左侧大。所有要找到最小节点；
  • 找到右侧最小节点的值，去更新要移除的这个节点的值。也就是移除掉了要移除的值，把比左侧大 右侧小的值，推上了被替换掉的这个值的位置。
  • 此时存在两个相同的节点（第一条这个值），第一个在原来节点，第二个在替换掉的那个值的位置。所以要把它原来位置的值删掉，保证树中不存在两个相同的值；
  • 返回树

1.png2.png3.png

完整代码

  1. //  用于创建每个树的节点
  2. class Node {
  3.     constructor(key = null, left = null, right = null) {
  4.         this.key = key;
  5.         this.left = left;
  6.         this.right = right;
  7.     }
  8. }
  9. // export const Compare = {
  10. //     LESS_THAN: -1,
  11. //     BIGGER_THAN: 1,
  12. //     EQUALS: 0
  13. //   };
  15. class BinarySearchTree {
  16.     constructor() {
  17.         this.root = null;   //  Node根节点
  18.     }
  20.     //  向二叉搜索树插入一个键
  21.     insert(key) {
  22.         //  如果没有根节点，直接创建一个新的节点
  23.         if (this.root === null) {
  24.             this.root = new Node(key);
  25.         } else {
  26.             //  如果不是第一个节点 递归查找到指定位置然后创建节点
  27.             this.insertNode(this.root, key)
  28.         }
  29.     }
  30.     insertNode(node, key) {
  31.         //  左侧 比父节点小
  32.         if (this.defaultCompare(key, node.key) === -1) {
  33.             if (node.left === null) {
  34.                 node.left = new Node(key)
  35.             } else {
  36.                 this.insertNode(node.left, key)
  37.             }
  38.         } else {
  39.             // 右侧 比父节点大
  40.             if (node.right === null) {
  41.                 node.right = new Node(key)
  42.             } else {
  43.                 this.insertNode(node.right, key)
  44.             }
  45.         }
  46.     }
  48.     //  用来比较两个节点
  49.     defaultCompare(a, b) {
  50.         //  两个相等 = 0
  51.         if (a === b) {
  52.             //  如果一样放到下一个节点
  53.             return 0;
  54.         }
  55.         return a < b ?
  56.             -1 /* 左侧 比父节点小 */ :
  57.             1  /* 右侧 比父节点大 */ ;
  58.     }
  60.     //  中序遍历
  61.     inOrderTraverse(callback) {
  62.         this.inOrderTraverseNode(this.root, callback);
  63.     }
  64.     inOrderTraverseNode(node, callback) {
  65.         //  停止递归的条件
  66.         if (node !== null) {
  67.             //  通过栈先把所有小的都放到栈里面
  68.             //  先遍历左测 小节点 
  69.             this.inOrderTraverseNode(node.left, callback);
  70.             callback(node.key);
  71.             //  后遍历右测 大节点
  72.             this.inOrderTraverseNode(node.right, callback)
  73.         }
  74.     }
  76.     //  先序遍历
  77.     perOrderTraverse(callback) {
  78.         this.perOrderTraverseNode(this.root, callback);
  79.     }
  80.     perOrderTraverseNode(node, callback) {
  81.         if (node !== null) {
  82.             callback(node.key);
  83.             this.perOrderTraverseNode(node.left, callback);
  84.             this.perOrderTraverseNode(node.right, callback);
  85.         }
  86.     }
  88.     //  后续排序
  89.     postOrderTraverse(callback) {
  90.         this.postOrderTraverseNode(this.root, callback);
  91.     }
  92.     postOrderTraverseNode(node, callback) {
  93.         if (node !== null) {
  94.             this.postOrderTraverseNode(node.left, callback)
  95.             this.postOrderTraverseNode(node.right, callback)
  96.             callback(node.key)
  97.         }
  98.     }
  100.     //  查找最小值
  101.     min() {
  102.         return this.minNode(this.root);
  103.     }
  104.     minNode(node) {
  105.         while (node !== null && node.left !== null) {
  106.             node = node.left;
  107.         }
  108.         return node;
  109.     }
  111.     //  查找最大值
  112.     max() {
  113.         return this.maxNode(this.root)
  114.     }
  115.     maxNode(node) {
  116.         while (node !== null && node.right !== null) {
  117.             node = node.right;
  118.         }
  119.         return node.key
  120.     }
  122.     // 搜索一个特定的值
  123.     search(key) {
  124.         return this.searchNode(this.root, key)
  125.     }
  126.     searchNode(node, key) {
  127.         if (node === null) return false;
  129.         let result = this.defaultCompare(key, node.key)
  130.         if (result === -1) {
  131.             return this.searchNode(node.left, key);
  132.         } else if (result === 1) {
  133.             return this.searchNode(node.right, key)
  134.         } else {
  135.             return true;
  136.         }
  137.     }
  139.     //  移除 节点返回一个新的root树，而不是返回移除的节点值
  140.     remove(key) {
  141.         this.root = this.removeNode(this.root, key);
  142.     }
  143.     removeNode(node, key) {
  144.         if (node === null) return false;
  145.         //  key 比 当前节点小
  146.         if (this.defaultCompare(key, node.key) === -1) {
  147.             node.left = this.removeNode(node.left, key)
  148.             return node;
  149.         } else if (this.defaultCompare(key, node.key) === 1) {
  150.             //  key 比当前节点大
  151.             node.right = this.removeNode(node.right, key);
  152.             return node;
  153.         } else {
  154.             //  { 1 } 情况1: 移除没有左右叶的节点
  155.             if (node.let === null && node.right === null) {
  156.                 node = null;
  157.                 return node;
  158.             }
  159.             // { 2 } 情况2：移除只存在 左叶或右叶的 节点
  160.             if (node.left === null) {
  161.                 node = node.left;   //  null  赋值给当前节点表示移除
  162.                 return node;
  163.             } else if (node.right === null) {
  164.                 node = node.right   //  null  赋值给当前节点表示移除
  165.                 return node;
  166.             }
  168.             // { 3 }  情况3：移除有两个子节点的节点
  169.             const aux = this.minNode(node.right);   //  找到右侧最小节点
  170.             node.key = aux.key; //  最小节点更新 要移除的这个节点
  171.             node.right = this.removeNode(node.right, aux.key);  //  移除掉原来位置的值
  172.             return node;
  173.         }
  174.     }
  175. }

缺点

二叉搜索树（BST）存在一个问题，取决于你添加的节点数，书的一遍可能会非常深。也就是说，树的一条分之会有很多层，而其他的分之却只有几层，会在添加，移除，搜索某个节点的时候产生性能问题。

完整代码见 https://github.com/qdwds/data-structure/blob/master/src/binarySearchTree/binarySearchTree.js