树

（1）相关概念

兄弟节点：节点的父节点是同一个节点，所以它们之间互称为兄弟节点。

根节点：没有父节点的节点叫作根节点

叶子节点：没有子节点的节点叫作叶子节点或者叶节点。

节点的高度：节点到叶子节点的最长路径（边数）。

节点的深度：根节点到这个节点所经历的边的个数。

节点的层数：节点的深度 + 1.

树的高度：根节点的高度。

记这几个概念，还有一个小窍门，就是类比“高度”、“深度”、“层”这几个名词在生活中的含义。

在生活中，“高度”这个概念，其实就是从下往上度量，比如要度量第 10 层楼的高度、第 13 层楼的高度，起点都是地面。所以，树这种数据结构的高度也是一样，从最底层开始计数，并且计数的起点是 0。

“深度”这个概念在生活中是从上往下度量的，比如水中鱼的深度，是从水平面开始度量的。所以，树这种数据结构的深度也是类似的，从根结点开始度量，并且计数起点也是 0。

“层数”跟深度的计算类似，不过，计数起点是 1，也就是说根节点的位于第 1 层。

（2）二叉树（Binary Tree）

二叉树，顾名思义，每个节点最多有两个“叉”，也就是两个子节点，分别是左子节点和右子节点。不过，二叉树并不要求每个节点都有两个子节点，有的节点只有左子节点，有的节点只有右子节点。

编号 2 的二叉树中，叶子节点全都在最底层，除了叶子节点之外，每个节点都有左右两个子节点，这种二叉树就叫作满二叉树。

编号 3 的二叉树中，叶子节点都在最底下两层，最后一层的叶子节点都靠左排列，并且除了最后一层，其他层的节点个数都要达到最大，这种二叉树叫作完全二叉树。

存储一棵二叉树，我们有两种方法，一种是基于指针或者引用的二叉链式存储法，一种是基于数组的顺序存储法。

1. 链式存储法

每个节点有三个字段，其中一个存储数据，另外两个是指向左右子节点的指针。

只要拎住根节点，就可以通过左右子节点的指针，把整棵树都串起来。这种存储方式我们比较常用。大部分二叉树代码都是通过这种结构来实现的。

2. 顺序存储法

把根节点存储在下标 i = 1 的位置，那左子节点存储在下标 2 * i = 2 的位置，右子节点存储在 2 * i + 1 = 3 的位置。以此类推，B 节点的左子节点存储在 2 * i = 2 * 2 = 4 的位置，右子节点存储在 2 * i + 1 = 2 * 2 + 1 = 5 的位置。

如果节点 X 存储在数组中下标为 i 的位置，下标为 2 * i 的位置存储的就是左子节点，下标为 2 * i + 1 的位置存储的就是右子节点。反过来，下标为 i/2 的位置存储就是它的父节点。

不过，上面的例子是一棵完全二叉树，所以仅仅“浪费”了一个下标为 0 的存储位置。如果是非完全二叉树，其实会浪费比较多的数组存储空间。

所以，如果某棵二叉树是一棵完全二叉树，那用数组存储无疑是最节省内存的一种方式。因为数组的存储方式并不需要像链式存储法那样，要存储额外的左右子节点的指针。这也是为什么完全二叉树会单独拎出来的原因，也是为什么完全二叉树要求最后一层的子节点都靠左的原因。

3. 二叉树的遍历

经典的方法有三种，前序遍历、中序遍历和后序遍历。

• 前序遍历是指，对于树中的任意节点来说，先打印这个节点，然后再打印它的左子树，最后打印它的右子树。

  preOrderTraverse(callback) {
      const preOrderTraverseNode = (node, callback) => {
          if (node !== null) {
              callback(node.key)
              preOrderTraverseNode(node.left, callback)
              preOrderTraverseNode(node.right, callback)
          }
      }
      preOrderTraverseNode(this.root, callback)
  }
  tree.inOrderTraverse(value => { console.log(value) })
  

• 中序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它本身，最后打印它的右子树。

  inOrderTraverse(callback) {
      const inOrderTraverseNode = (node, callback) => {
          if (node !== null) {
              inOrderTraverseNode(node.left, callback)
              callback(node.key)
              inOrderTraverseNode(node.right, callback)
          }
      }
      inOrderTraverseNode(this.root, callback)
  }
  tree.inOrderTraverse(value => { console.log(value) })
  

• 后序遍历是指，对于树中的任意节点来说，先打印它的左子树，然后再打印它的右子树，最后打印这个节点本身。

  postOrderTraverse(callback) {
      const postOrderTraverseNode = (node, callback) => {
          if (node !== null) {
              postOrderTraverseNode(node.left, callback)
              postOrderTraverseNode(node.right, callback)
              callback(node.key)
          }
      }
      postOrderTraverseNode(this.root, callback)
  }
  

平时最常用的树就是二叉树。二叉树的每个节点最多有两个子节点，分别是左子节点和右子节点。二叉树中，有两种比较特殊的树，分别是满二叉树和完全二叉树。满二叉树又是完全二叉树的一种特殊情况。

二叉树既可以用链式存储，也可以用数组顺序存储。数组顺序存储的方式比较适合完全二叉树，其他类型的二叉树用数组存储会比较浪费存储空间。除此之外，二叉树里非常重要的操作就是前、中、后序遍历操作，遍历的时间复杂度是 O(n)。

（3）二叉查找树（Binary Search Tree）

二叉查找树是二叉树中最常用的一种类型，也叫二叉搜索树。

顾名思义，二叉查找树是为了实现快速查找而生的。不过，它不仅仅支持快速查找一个数据，还支持快速插入、删除一个数据。它是怎么做到这些的呢？这些都依赖于二叉查找树的特殊结构。

二叉查找树要求，在树中的任意一个节点，其左子树中的每个节点的值，都要小于这个节点的值，而右子树节点的值都大于这个节点的值。

1. 二叉查找树的查找操作

先取根节点，如果它等于我们要查找的数据，那就返回。

如果要查找的数据比根节点的值小，那就在左子树中递归查找；

如果要查找的数据比根节点的值大，那就在右子树中递归查找。

代码实现：

search(key) {
    const searchNode = (node, key) => {
        if (node === null) return false
        if (node.key === key) return node
        return searchNode((key < node.key) ? node.left : node.right, key)
    }
    return searchNode(root, key)
}

2. 二叉查找树的插入操作

二叉查找树的插入过程有点类似查找操作。新插入的数据一般都是在叶子节点上，所以我们只需要从根节点开始，依次比较要插入的数据和节点的大小关系。

如果要插入的数据比节点的数据大，并且节点的右子树为空，就将新数据直接插到右子节点的位置；如果不为空，就再递归遍历右子树，查找插入位置。同理，如果要插入的数据比节点数值小，并且节点的左子树为空，就将新数据插入到左子节点的位置；如果不为空，就再递归遍历左子树，查找插入位置。

代码实现：

class Node {
    constructor(key) {
        this.key = key
        this.left = null
        this.right = null
    }
}

class BinarySearchTree {

    constructor() {
        this.root = null
    }

    insert(key) {
        const newNode = new Node(key)
        const insertNode = (node, newNode) => {
            if (newNode.key < node.key) {
                if (node.left === null) {
                    node.left = newNode
                } else {
                    insertNode(node.left, newNode)
                }
            } else {
                if (node.right === null) {
                    node.right = newNode
                } else {
                    insertNode(node.right, newNode)
                }
            }
        }
        if (!this.root) {
            this.root = newNode
        } else {
            insertNode(this.root, newNode)
        }
    }
}
const tree = new BinarySearchTree()
tree.insert(11)
tree.insert(7)
tree.insert(5)
tree.insert(3)

3. 二叉查找树的删除操作

删除操作就比较复杂了 。针对要删除节点的子节点个数的不同，我们需要分三种情况来处理。

• 第一种情况是，如果要删除的节点没有子节点，只需要直接将父节点中，指向要删除节点的指针置为 null。比如图中的删除节点 55。

• 第二种情况是，如果要删除的节点只有一个子节点（只有左子节点或者右子节点），只需要更新父节点中，指向要删除节点的指针，让它指向要删除节点的子节点就可以了。比如图中的删除节点 13。

• 第三种情况是，如果要删除的节点有两个子节点，这就比较复杂了。需要找到这个节点的右子树中的最小节点，把它替换到要删除的节点上。然后再删除掉这个最小节点，因为最小节点肯定没有左子节点（如果有左子结点，那就不是最小节点了），所以，我们可以应用上面两条规则来删除这个最小节点。比如图中的删除节点 18。
  

代码实现：

function deleteNode(root, key){
    if (!root){
        console.log("删除失败");
        return root;
    }

    if (root.value > key){  //若当前结点值大于删除值，则继续在左子树中寻找删除值
        root.left = deleteNode(root.left, key);
    }else if (root.value < key){  //若当前结点值小于删除值，则继续在右子树中寻找删除值
        root.right = deleteNode(root.right, key);
    }else{  //找到与删除中相等的结点
        if (root.left === null & root.right === null){  //叶子结点
            root = null;
        }else if (root.left === null){  //只有右子树
            root = root.right;
        }else if (root.right === null){  //只有左子树
            root = root.left;
        }else{  //同时具有左右子树
            let prevNode = root.left;
            while(prevNode.right){  //寻找不大于当前结点值的最大结点值
                prevNode = prevNode.right;
            }
            root.value = prevNode.value;  //替换值
            root.left = deleteNode(root.left, prevNode.value);  //递归左子树，删除重复值的结点
        }
    } 
    return root;
}

4. 搜索最小值和最大值

min(node) {
    const minNode = node => {
        return node ? (node.left ? minNode(node.left) : node) : null
    }
    return minNode(node || this.root)
}

max(node) {
    const maxNode = node => {
        return node ? (node.right ? maxNode(node.right) : node) : null
    }
    return maxNode(node || this.root)
}

5. 时间复杂度分析

实际上，二叉查找树的形态各式各样。比如这个图中，对于同一组数据，构造了三种二叉查找树。它们的查找、插入、删除操作的执行效率都是不一样的。

图中第一种二叉查找树，根节点的左右子树极度不平衡，已经退化成了链表，所以查找的时间复杂度就变成了 O(n)。这是一种最糟糕的情况。

最理想的情况，二叉查找树是一棵完全二叉树（或满二叉树）。不管操作是插入、删除还是查找，时间复杂度其实都跟树的高度成正比，也就是 O(height)。

（4）相对散列表，二叉树的优势

• 散列表中的数据是无序存储的，如果要输出有序的数据，需要先进行排序。而对于二叉查找树来说，我们只需要中序遍历，就可以在 O(n) 的时间复杂度内，输出有序的数据序列。
• 散列表扩容耗时很多，而且当遇到散列冲突时，性能不稳定，尽管二叉查找树的性能不稳定，但是在工程中，我们最常用的平衡二叉查找树的性能非常稳定，时间复杂度稳定在 O(logn)。
• 笼统地来说，尽管散列表的查找等操作的时间复杂度是常量级的，但因为哈希冲突的存在，这个常量不一定比 logn 小，所以实际的查找速度可能不一定比 O(logn) 快。加上哈希函数的耗时，也不一定就比平衡二叉查找树的效率高。
• 散列表的构造比二叉查找树要复杂，需要考虑的东西很多。比如散列函数的设计、冲突解决办法、扩容、缩容等。平衡二叉查找树只需要考虑平衡性这一个问题，而且这个问题的解决方案比较成熟、固定。
• 为了避免过多的散列冲突，散列表装载因子不能太大，特别是基于开放寻址法解决冲突的散列表，不然会浪费一定的存储空间。

学习于：

极客时间《数据结构与算法之美》

JavaScript中的数据结构与算法学习