树

树是一种递归的数据结构，与链表类似：

• 一棵树有且只有一个根节点。
• 每个节点有 0 到多个子节点。
• 每个子节点还有 0 到多个子节点。
• 以此类推。
• 每个节点还会保存节点的值

相邻的节点称为邻居节点，没有子节点的节点称为叶子节点，树的层数称为树的高度。​

除根节点外，子节点以及它后续节点形成的树称为子树。

应用

树是应用最为广泛的数据结构之一，例如：

• HTML DOM / Virtual DOM 结构。
• 索引。
• 文件系统。
• 自动补全功能。

等等等等。

分类

树的分类有多种，根据子节点的数量不同，可分为二叉树、三叉树或多叉树。最常见的是二叉树，每个节点最多有两个子节点。多叉树常见的有字典树。 对于二叉树，根据节点的排列和数量，也分为下面几种常见的类型：

• 完全二叉树（Completed Binary Trees）：每一层的节点都拥有 2 个子节点，最后一层除外，最后一层空缺的节点必须在右边，左边必须填满。
• 满二叉树（Full Bnary Trees）：每个节点要么有 2 个子节点，要么没有子节点，不能只有 1 个子节点。
• 完美二叉树（Perfect Binary Trees）：所有的节点都有两个子节点，最后一层都是叶子节点。
• 平衡二叉树（Balanced Binary Trees）：平衡二叉树的定义并不是很严格，不同的场景有不同的定义，对于一棵二叉树，如果大体上左右两棵子树看起来比较平衡，它就是平衡二叉树，有的定义是左右子树的每个节点的高度差都不大于 1。
• 二叉搜索树（Binary Search Trees）：左子节点的值 <= 该节点值 < 右子节点的值，并且左节点和它后续节点的值都小于等于该节点的值，右节点和它后续的值都大于该节点的值，这样形成的树方便进行搜索和排序，所以叫作二叉搜索树。对于和节点值相同的子节点应该放左边还是右边，不同的实现有不同的规定。
• 自平衡二叉搜索树（Self-Balancing Binary Search Trees）：这种树在平衡二叉树和搜索二叉树的基础上，会根据节点的插入和删除，自动保持平衡，常见的有红黑树和 AVL 树，不过这两种树的实现比较复杂。

JavaScript 实现

由于二叉树是最常用的数据结构，并且比较简单，我们来看一下它的 JavaScript 实现。另外对于树的遍历、查找、添加节点、删除节点等涉及的操作比较复杂，我们在后面的视频中再逐一学习，这里主要看一下二叉树的节点结构。 二叉树的代码与链表类似，我们使用一个 TreeNode class 来代表树的节点：

• 节点有一个 value 属性，保存树的值。
• 然后有 left 属性，保存左子节点的引用。
• 最后有 right 属性，保存右子节点的引用。
• 子节点的类型都是 TreeNode，这是一个递归的类型。
• 在构造函数中赋值的时候，如果没给其中的某些属性传值，那么就给它们设置默认值，value 默认为 0，left 和 right 子节点默认为 null。

class TreeNode {
  constructor(value, left, right) {
    this.value = value ? value : 0;
    this.left = left ? left : null;
    this.right = right ? right : null;
  }
}

之后可以定义一个 BinaryTree class，里边保存一个根节点的值，因为树也是递归结构，所以通过根节点可以找到所有子节点，类的剩余部分可以定义和二叉树有关的操作：

class BinaryTree {
  constructor(root) {
    this.root = root;
  }
  // 其它方法
}