树是一种分层数据的抽象模型。由一个或多个父子关系的节点组成。

相关术语

image.png

  • 根节点 ：位于树的顶部的节点叫根节点
  • 内部节点 ：至少有一个子节点的节点称为内部节点，如上图的 7,5,9,15,13,20
  • 外部节点 ：一个节点都没有的节点称为外部节点，也叫 叶节点 ，如上图的 3,6,8,10,12,14,18,25
  • 子树 ：由节点和他的后代节点组成，如上图的 13,12,14 构成了一个子树
  • 节点深度 ：节点的深度取决于节点的祖先节点的数量，如上图的节点3，它的祖先节点有 5,7,11, 所以它的节点深度为3
  • 树的高度 ：树的高度是所有节点的深度的最大值，如上图树的高度最大的节点深度为3，其树的高度也就是3。也可以通过分层，根节点在第0层，子节点在第1层，依此类推，可得到树的高度。

二叉树

二叉树就是只有两个节点的树，一个左节点和一个右节点。

二叉搜索树

二叉搜索树(BST)，是二叉树的一种，他的特点是左侧节点比父节点小，右侧节点比父节点大。

  1. class Node {
  2.     constructor(key) {
  3.         this.key = key;
  4.         this.left = null;
  5.         this.right = null;
  6.     }
  7. }
  9. class BinarySearchTree {
  10.     constructor() {
  11.         this.root = null;
  12.     }
  14.     insert(key) {
  15.         if (this.root) {
  16.             this.insertNode(this.root, key);
  17.         } else {
  18.             this.root = new Node(key);
  19.         }
  20.     }
  22.     insertNode(node, key) {
  23.         if (key < node.key) {
  24.             if (node.left) {
  25.                 this.insertNode(node.left, key);
  26.             } else {
  27.                 node.left = new Node(key);
  28.             }
  29.         } else {
  30.             if (node.right) {
  31.                 this.insertNode(node.right, key);
  32.             } else {
  33.                 node.right = new Node(key);
  34.             }
  35.         }
  36.     }
  38.     /**
  39.      * 中序遍历
  40.      * 从小到大访问节点
  41.      * @param {*} callback 
  42.      */
  43.     inOrderTraverse(callback) {
  44.         this.inOrderTraverseNode(this.root, callback);
  45.     }
  47.     inOrderTraverseNode(node, callback) {
  48.         if (node) {
  49.             this.inOrderTraverseNode(node.left, callback);
  50.             callback(node.key);
  51.             this.inOrderTraverseNode(node.right, callback);
  52.         }
  53.     }
  55.     /**
  56.      * 先序遍历
  57.      * 从上往下，先左后右访问节点
  58.      * @param {*} callback 
  59.      */
  60.     preOrderTraverse(callback) {
  61.         this.preOrderTraverseNode(this.root, callback);
  62.     }
  64.     preOrderTraverseNode(node, callback) {
  65.         if (node) {
  66.             callback(node.key);
  67.             node.left && this.preOrderTraverseNode(node.left, callback);
  68.             node.right && this.preOrderTraverseNode(node.right, callback);
  69.         }
  70.     }
  72.     /**
  73.      * 后序遍历
  74.      * 从下往下，先左后右访问节点
  75.      * @param {*} callback 
  76.      */
  77.     postOrderTraverse(callback) {
  78.         this.postOrderTraverseNode(this.root, callback);
  79.     }
  81.     postOrderTraverseNode(node, callback) {
  82.         if (node) {
  83.             node.left && this.postOrderTraverseNode(node.left, callback);
  84.             node.right && this.postOrderTraverseNode(node.right, callback);
  85.             callback(node.key);
  86.         }
  87.     }
  89.     min() {
  90.         return this.minNode(this.root);
  91.     }
  93.     minNode(node) {
  94.         let current = node;
  95.         while (current && current.left) {
  96.             current = current.left;
  97.         }
  99.         return current;
  100.     }
  102.     max() {
  103.         let current = this.root;
  104.         while (current && current.right) {
  105.             current = current.right;
  106.         }
  108.         return current;
  109.     }
  111.     search(key) {
  112.         return this.searchNode(this.root, key);
  113.     }
  115.     searchNode(node, key) {
  116.         if (!node) return false;
  118.         if (key < node.key) {
  119.             return this.searchNode(node.left, key);
  120.         } else if (key > node.key) {
  121.             return this.searchNode(node.right, key);
  122.         } else {
  123.             return true;
  124.         }
  125.     }
  127.     remove(key) {
  128.         return this.removeNode(this.root, key);
  129.     }
  131.     removeNode(node, key) {
  132.         if (!node) return null;
  134.         if (key < node.key) {
  135.             node.left = this.removeNode(node.left, key);
  136.             return node;
  137.         } else if (key > node.key) {
  138.             node.right = this.removeNode(node.right, key);
  139.         } else {
  140.             if (!node.left && !node.right) {
  141.                 node = null;
  142.             } else if (node.left && !node.right) {
  143.                 node = node.left;
  144.             } else if (!node.left && node.right) {
  145.                 node = node.right;
  146.             } else {
  147.                 let minNode = this.minNode(node.right);
  148.                 node.key = minNode.key;
  149.                 node.right = this.removeNode(node.right, minNode.key);
  150.             }
  152.             return node;
  153.         }
  154.     }
  156.     toString() {
  157.         return JSON.stringify(this.root, null, 2);
  158.     }
  159. }
  161. const tree = new BinarySearchTree();
  162. tree.insert(11);
  163. tree.insert(7);
  164. tree.insert(15);
  165. tree.insert(5);
  166. tree.insert(3);
  167. tree.insert(9);
  168. tree.insert(8);
  169. tree.insert(10);
  170. tree.insert(13);
  171. tree.insert(12);
  172. tree.insert(14);
  173. tree.insert(20);
  174. tree.insert(18);
  175. tree.insert(25);
  176. tree.insert(6);
  177. tree.remove(5)
  178. console.log(tree.toString());

AVL 自平衡树

红黑树