基本概念

二叉搜索树 - 图1

二叉树

二叉树中的节点最多只能有两个子节点：
一个是左侧子节点，另一个是右侧子节点。
这个定义有助于我们写出更高效地在树中插入、查找和删除节点的算法
二叉树在计算机科学中的应用非常广泛。

二叉搜索树

二叉搜索树（BST）是二叉树的一种
但是只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大的值。
二叉搜索树 - 图2

二叉搜索树的代码实现

结构

  1. class Node {
  2.     constructor(key) {
  3.         this.key = key; // 存值
  4.         this.left = null;   // 左子结点
  5.         this.right = null;  // 右子结点
  6.     }
  9. }
  10. // 设计比较大小的方法，注意可读性
  11. let Compare = {
  12.     LES_THAN: -1,
  13.     BIG_THAN: 1,
  14.     EQUAL: 0,
  15. };
  17. class BinarySearch {
  18.     constructor() {
  19.         this.root = null;   // 二叉树结构的根结点
  20.     }
  21.     compareFn(a, b) {
  22.         if (a === b) {
  23.             return Compare.EQUAL;
  24.         }
  25.         return a < b ? Compare.LES_THAN : Compare.BIG_THAN;
  26.     }
  27. }
  • insert(key)：向树中插入一个新的键。
  • search(key)：在树中查找一个键。如果节点存在，则返回true；如果不存在，则返回false。
  • inOrderTraverse()：通过中序遍历方式遍历所有节点。
  • preOrderTraverse()：通过先序遍历方式遍历所有节点。
  • postOrderTraverse()：通过后序遍历方式遍历所有节点。
  • min()：返回树中最小的值/键。
  • max()：返回树中最大的值/键。
  • remove(key)：从树中移除某个键。

insert

  1. insert(key) {
  2.         if (this.root === null) {
  3.             this.root = new Node(key);
  4.         } else {
  5.             this.insertNode(this.root, key);
  6.         }
  7.     }
  9. insertNode(node, key) {
  10.     if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  11.         // 如果插入的值比当前结点小，往左子树走
  12.         if (node.left === null) {
  13.             // 左子树为空，就插入左子树
  14.             node.left = new Node(key);
  15.         } else {
  16.             // 左子树不为空就向下递归判断左右子树
  17.             this.insertNode(node.left, key);
  18.         }
  19.     }
  20.     // 右子树
  21.     else {
  22.         if (node.right === null) {
  23.             node.right = new Node(key);
  24.         } else {
  25.             this.insertNode(node.right, key);
  26.         }
  27.     }
  28. }

Traverse 遍历

中序遍历（左中右）

  • 要通过中序遍历的方法遍历一棵树，首先要检查以参数形式传入的节点是否为null（这就是停止递归继续执行的判断条件，即递归算法的基线条件）。
  • 然后，递归调用相同的函数来访问左侧子节点。
  • 接着对根节点进行一些操作（callback），然后再访问右侧子节点
  1. inOrderTraverse(cb) {
  2.     this.inOrderTraverseNode(this.root, cb);
  3. }
  4. inOrderTraverseNode(node, cb) {
  5.     if (node != null) {
  6.         this.inOrderTraverseNode(node.left, cb);
  7.         cb(node.key);
  8.         this.inOrderTraverseNode(node.right, cb);
  10.     }
  11. }

先序遍历（中左右）

二叉搜索树 - 图3

  1. preOrderTraverse(cb) {
  2.     this.preOrderTraverseNode(this.root, cb);
  3. }
  4. preOrderTraverseNode(node, cb) {
  5.     if (node != null) {
  6.         cb(node.key);
  7.         this.preOrderTraverseNode(node.left, cb);
  8.         this.preOrderTraverseNode(node.right, cb);
  9.     }
  10. }

后序遍历（左右中）

二叉搜索树 - 图4

  1. postOrderTraverse(cb) {
  2.     this.postOrderTraverseNode(this.root, cb);
  3. }
  4. postOrderTraverseNode(node, cb) {
  5.     if (node != null) {
  6.         this.postOrderTraverseNode(node.left, cb);
  7.         this.postOrderTraverseNode(node.right, cb);
  8.         cb(node.key);
  9.     }
  10. }

最大最小值

  1.     min() {
  2.         let curr = this.minNode(this.root);
  3.     }
  5.     minNode(node) {
  6.         let curr = node;
  7.         while (curr && curr.left) {
  8.             curr = curr.left;
  9.         }
  10.         return curr;
  11.     }
  13.     max() {
  14.         let curr = this.maxNode(this.root);
  15.     }
  17.     maxNode(node) {
  18.         let curr = node;
  19.         if (curr && curr.right) {
  20.             curr = curr.right;
  21.         }
  22.         return curr;
  23.     }

搜索值是否存在

  1.     search(key) {
  2.         return this.searchNode(this.root, key);
  3.     }
  4.     searchNode(node, key) {
  5.         if (node === null) {
  6.             return false;
  7.         }
  8.         if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  9.             return this.searchNode(node.left, key);
  10.         }
  11.         // 右子树
  12.         else if (this.compareFn(key, node.key) === Compare.BIG_THAN) {
  13.             return this.searchNode(node.right, key);
  14.         }
  15.         else {
  16.             return true;
  17.         }
  18.     }

删除树结点

找到需要删除的结点后，要分三种情况

  1. 是叶结点
    二叉搜索树 - 图5
  2. 有一个子结点
    二叉搜索树 - 图6
  3. 有两个子结点：需要把下面最小的结点补充到这个被删除结点的位置
    二叉搜索树 - 图7
    思路：需要记录删除结点后的数
  1. remove(key) {
  2.     return this.removeNode(this.root, key);
  3. }
  5. removeNode(node, key) {
  6.     // 没有了
  7.     if (node === null) {
  8.         return null;
  9.     }
  10.     // 找左子树
  11.     if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  12.         node.left = this.removeNode(node.left, key);
  13.         return node;
  14.     }
  15.     // 找右子树
  16.     else if (this.compareFn(key, node.key) === Compare.BIG_THAN) {
  17.         node.right = this.removeNode(node.right, key);
  18.         return node;
  19.     }
  20.     else {
  21.         // 1. 删除的是个叶结点
  22.         if (!node.left && !node.right) {
  23.             node = null;
  24.             return node;
  25.         }
  26.         // 2. 没有左（右）子结点，但是有右（左）子结点（只有一个孩子结点）
  27.         else if (!node.left && node.right) {
  28.             node = node.right;
  29.             return node;
  30.         }
  31.         else if (node.left && !node.right) {
  32.             node = node.left;
  33.             return node;
  34.         }
  35.         // 3. 被删除的结点有两个孩子结点
  36.         else {
  37.             const minNode = this.minNode(node.right);   // 找到孩子结点中的最小的一个
  38.             // 用这个最小的结点替换掉删除结点
  39.             node.key = minNode.key;
  40.             // 删除找到的最小结点，并将这个结点的左子树重构（返回删除后的结点）
  41.             node.right = this.removeNode(node.right, minNode.key);
  42.             return node;
  43.         }
  45.     }
  46. }

完整代码

  1. class Node {
  2.     constructor(key) {
  3.         this.key = key; // 存值
  4.         this.left = null;   // 左子结点
  5.         this.right = null;  // 右子结点
  6.     }
  9. }
  10. // 设计比较大小的方法，注意可读性
  11. let Compare = {
  12.     LES_THAN: -1,
  13.     BIG_THAN: 1,
  14.     EQUAL: 0,
  15. };
  17. class BinarySearch {
  18.     constructor() {
  19.         this.root = null;   // 二叉树结构的根结点
  20.     }
  21.     compareFn(a, b) {
  22.         if (a === b) {
  23.             return Compare.EQUAL;
  24.         }
  25.         return a < b ? Compare.LES_THAN : Compare.BIG_THAN;
  26.     }
  28.     insert(key) {
  29.         if (this.root === null) {
  30.             this.root = new Node(key);
  31.         } else {
  32.             this.insertNode(this.root, key);
  33.         }
  34.     }
  36.     insertNode(node, key) {
  37.         if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  38.             // 如果插入的值比当前结点小，往左子树走
  39.             if (node.left === null) {
  40.                 // 左子树为空，就插入左子树
  41.                 node.left = new Node(key);
  42.             } else {
  43.                 // 左子树不为空就向下递归判断左右子树
  44.                 this.insertNode(node.left, key);
  45.             }
  46.         }
  47.         // 右子树
  48.         else {
  49.             if (node.right === null) {
  50.                 node.right = new Node(key);
  51.             } else {
  52.                 this.insertNode(node.right, key);
  53.             }
  54.         }
  55.     }
  57.     inOrderTraverse(cb) {
  58.         this.inOrderTraverseNode(this.root, cb);
  59.     }
  60.     inOrderTraverseNode(node, cb) {
  61.         if (node != null) {
  62.             this.inOrderTraverseNode(node.left, cb);
  63.             cb(node.key);
  64.             this.inOrderTraverseNode(node.right, cb);
  65.         }
  66.     }
  67.     // 前序
  68.     preOrderTraverse(cb) {
  69.         this.preOrderTraverseNode(this.root, cb);
  70.     }
  71.     preOrderTraverseNode(node, cb) {
  72.         if (node != null) {
  73.             cb(node.key);
  74.             this.preOrderTraverseNode(node.left, cb);
  75.             this.preOrderTraverseNode(node.right, cb);
  76.         }
  77.     }
  78.     // 后序遍历
  79.     postOrderTraverse(cb) {
  80.         this.postOrderTraverseNode(this.root, cb);
  81.     }
  82.     postOrderTraverseNode(node, cb) {
  83.         if (node != null) {
  84.             this.postOrderTraverseNode(node.left, cb);
  85.             this.postOrderTraverseNode(node.right, cb);
  86.             cb(node.key);
  87.         }
  88.     }
  90.     min() {
  91.         let curr = this.minNode(this.root);
  92.     }
  94.     minNode(node) {
  95.         let curr = node;
  96.         while (curr && curr.left) {
  97.             curr = curr.left;
  98.         }
  99.         return curr;
  100.     }
  102.     max() {
  103.         let curr = this.maxNode(this.root);
  104.     }
  106.     maxNode(node) {
  107.         let curr = node;
  108.         if (curr && curr.right) {
  109.             curr = curr.right;
  110.         }
  111.         return curr;
  112.     }
  114.     search(key) {
  115.         return this.searchNode(this.root, key);
  116.     }
  118.     searchNode(node, key) {
  119.         if (node === null) {
  120.             return false;
  121.         }
  122.         if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  123.             return this.searchNode(node.left, key);
  124.         }
  125.         // 右子树
  126.         else if (this.compareFn(key, node.key) === Compare.BIG_THAN) {
  127.             return this.searchNode(node.right, key);
  128.         }
  129.         else {
  130.             return true;
  131.         }
  132.     }
  133.     remove(key) {
  134.         return this.removeNode(this.root, key);
  135.     }
  137.     removeNode(node, key) {
  138.         // 没有了
  139.         if (node === null) {
  140.             return null;
  141.         }
  142.         // 左子树
  143.         if (this.compareFn(key, node.key) === Compare.LES_THAN) {
  144.             node.left = this.removeNode(node.left, key);
  145.             return node;
  146.         }
  147.         // 右子树
  148.         else if (this.compareFn(key, node.key) === Compare.BIG_THAN) {
  149.             node.right = this.removeNode(node.right, key);
  150.             return node;
  151.         }
  152.         else {
  153.             // 1. 删除的是个叶结点
  154.             if (!node.left && !node.right) {
  155.                 node = null;
  156.                 return node;
  157.             }
  158.             // 2. 没有左（右）子结点，但是有右（左）子结点（只有一个孩子结点）
  159.             else if (!node.left && node.right) {
  160.                 node = node.right;
  161.                 return node;
  162.             }
  163.             else if (node.left && !node.right) {
  164.                 node = node.left;
  165.                 return node;
  166.             }
  167.             // 3. 被删除的结点有两个孩子结点
  168.             else {
  169.                 const minNode = this.minNode(node.right);   // 找到孩子结点中的最小的一个
  170.                 // 用这个最小的结点替换掉删除结点
  171.                 node.key = minNode.key;
  172.                 // 删除找到的最小结点，并将这个结点的左子树重构（返回删除后的结点）
  173.                 node.right = this.removeNode(node.right, minNode.key);
  174.                 return node;
  175.             }
  176.         }
  177.     }
  178. }
  180. let tree = new BinarySearch();
  181. tree.insert(4);
  182. tree.insert(3);
  183. tree.insert(2);
  184. tree.insert(1);
  185. tree.insert(5);
  186. tree.insert(6);
  188. console.log(tree);
  189. // tree.inOrderTraverse(function (key) {
  190. //     console.log(key);
  191. // });
  192. // tree.preOrderTraverse(function (key) {
  193. //     console.log(key);
  194. // });
  195. tree.postOrderTraverse(function (key) {
  196.     console.log(key);
  197. });
  199. console.log(tree.search(10));
  200. console.log(tree.remove(5));