前端数据结构与算法之树的基础部分（js 实现）-一一网

普通树

现实中的树是往上生长的，但是在计数据结构中图例中的树形结构一般是倒过来长的，因为这样从上到下比较好看一些。

一棵普通的树长这样：

从树的这种结构我们可以总结出以下几点相关概念

树结构的一些基础概念

父结点：如果某个结点拥有下一级结点，那么这个结点就叫做下一级的父结点。图例上的结点 3 是结点 8 的父结点。

孩子结点：如果某个结点有上一级结点，那么这个结点就叫做上一级结点的孩子结点。图例上的结点 2 是结点 1 的孩子结点。

根结点：树的最顶层结点，它没有父结点，只会有孩子结点。图例上的结点 1 就是根节点。

叶子结点：叶子结点处于树的某个分支的最末尾，它没有孩子结点。图例上的 5 6 7 8 9 10 这些结点都是叶子结点，因为它们没有孩子结点了。

子树：某个结点的孩子结点可以看做是一棵子树。图例上的结点 3 是根节点的孩子结点，以结点 3 为根结点的这棵树就叫做根结点 1 的子树。

树的层数：从根结点开始算为第 1 层，依次往下数第 2 层、第 3 层等。看图例所示。

深度：树的深度就是树的最大层数，比如：某棵树有 4 层，那它的深度就是 4。

度：子树的个数。如图例所示，根结点的子树有 3 棵（2 3 4），于是根结点的度为 3。又如结点 2 的子树有 3 棵（5 6 7），于是结点 2 的度为 3。

树的性质

非空树有且仅有一个根节点
从一个结点出发可以访问到其余的结点，并且从一个结点出发访问另一个结点的路径也有且仅有一条
父结点可以有多个子结点，根结点除外，其余结点有且仅有一个父结点

二叉树

概念：每个结点最多有两个孩子结点，满足这个条件的树就叫做二叉树。

会存在只有左子树和只会有右子树等情况

根据形态的不同又分为以下几种二叉树：

满二叉树（Perfect Binary Tree）

如果一棵二叉树的深度为 k 而且有 $2^k – 1$ 个结点，也就是说在这个深度下的叶子结点全都挂满了，那么称这棵二叉树是满二叉树，也可以叫完美二叉树。

完全二叉树（Complete Binary Tree）

如果一棵二叉树的深度为 k 且从第 1 层到第 k – 1 层该树都是满二叉树，第 k 层的结点都集中在左边且没有被完全填充，这样的一棵二叉树就叫做完全二叉树。

注意不要浪费时间纠结满二叉树和完全二叉树的区别，符合完全的特征就叫完全，符合满的特征就叫满，它们都能各安各家，不要听别人说什么满是完全的特例啥的把你绕晕了。

完全二叉树因为其特殊的形态，在对存储在其中的数据进行排序或者查找时可以用到它，效率比较高，所以常常会把一些数据转换成完全二叉树后再进行处理，后面学到了再详细介绍。

完满二叉树（Full Binary Tree）

满二叉树、完全二叉树和完满二叉树的英文名都不一样，但是中文翻译过来就有点不好区分了，满对应的是 Perfect，意为完美，完满对应的是 Full，表示每个父结点的子结点都饱满了。

如果一棵二叉树的所有非叶子结点的度都是 2，那么这个二叉树就叫做完满二叉树。

显然满二叉树是符合完满二叉树的特性的，但是满二叉树有自己的家，不会跑到这里来。

二叉树的性质

因为二叉树的形态简单，所以我们可以总结出一些二叉树的通用的性质：

假设二叉树的深度是 k，那么第 k 层最多有 $2^{k-1}$ 个结点。比如：一个深度为 4 的二叉树，它的第 3 层最多有 $2^{3 – 1} = 4$ 个结点。
第 k 层最多的节点数是第 k – 1 层的2倍。比如：第 3 层有 4 个结点，第四层最多有 8 个结点，比上一层多一倍。
假设二叉树的深度是 k，那么它最多会有 $2^k – 1$ 个结点。比如：深度为 4 的二叉树，最多有 $2^4 – 1 = 15$ 个结点。
在任意的二叉树上（整棵树或者是某个子树），设 $n_0$ 为度为 0 的叶子结点数， $n_1$ 为度为 1 的结点数， $n_2$ 为度为 2 的结点数。那么可以得到 $n_0$ 比 $n_2$ 多 1，也就是 $n_0 = n_2 + 1$ 。比如：一个深度为 4 的满二叉树，那么可以得到 $n_0 = 8, n_1 = 0, n_2 = 7$ 。
如果设 $n$ 为二叉树的结点总数，那么可以得到： $n = n_0 + n_1 + n_2$ 。在上例中就是 $n = 8 + 0 + 7 = 15$ 。我们还可以发现如果结点总数为 $n$ ，那么边的数量就是 $n – 1$ ，在上例中就是 $8 – 1 = 7$ 。
又因为度为 2 的结点下面有两条边，度为 1 的结点有一条边，叶子结点没有边，于是可以得到： $n – 1 = n_1 + 2 * n_2$ ，带入到上式中就可以得到 $n_0 + n_1 + n_2 = n_1 + 2 * n_2 + 1 ⇒ n_0 = n_2 + 1$ ，也就是说：叶子结点的数量比度为 2 的结点的数量多 1。上例中的 $n_0 = 8, n_2 = 7$ ，符合这个公式。

二叉树的广义表表示形式

广义表表示法，简单点说就是这样的： $LS=(a_1,a_2,…,a_n)$ 形式，我们用广义表来表示一棵树的话就是这样样子的：

设 root 为根结点，left 为左结点，right 为右结点，那么用广义表就可以一般地表示成： $root(left, right)$ 。
于是有：

root 说明只有根结点；

root(left) 说明只有左结点，右结点为空；

root(, right) 说明左结点为空，只有右结点；

root(left, right) 说明左右结点都有。

例如：9(8(7, 6), 5(4, 3))，可以表示一棵以 9 为根节点的二叉树

它有什么用？

假设有一个霍夫曼树，以及使用霍夫曼编码后的二进制数据，那么你把数据传给别人的同时，也需要把码表传给对方，否则对方是无法解码的。
这时就可以使用广义表的形式把霍夫曼树传给对方，就可以根据广义表转成霍夫曼树，于是就可以解码了。

二叉树的结构

理论学完后咱们来看一下如何创建一棵二叉树。

根据定义，二叉树包含三个部分：数据域，左结点和右结点

/**
 * 二叉树结构
 * @param {*} data 结点数据
 */
function BinaryTree(data) {
  this.data = data;
  this.lchild = null;
  this.rchild = null;
}
复制代码

手动创建一棵二叉树以作备用

先手动创建一棵二叉树吧，这样能直观的感受到它的结构是什么样的。当然你也可以写一个函数来生成。

const root = new BinaryTree(1);
root.lchild = new BinaryTree(2);
root.rchild = new BinaryTree(3);
root.lchild.lchild = new BinaryTree(4);
root.lchild.rchild = new BinaryTree(5);
root.rchild.lchild = new BinaryTree(6);
root.rchild.rchild = new BinaryTree(7);
复制代码

创建好后，它看起来是这样的：

二叉树的遍历

因为这篇文章是基础部分，所以咱们先来学习如何遍历二叉树。

二叉树有三种普遍认可的遍历方式，当然你也可以自创自己的遍历方式，比如奇偶遍历（先遍历奇数编号的结点再遍历偶数编号的结点，虽然是我随便想的）。说这句话的目的就是为了说明，不要把自己的思路给限制死了。

注意：先序、中序、后序说的序，指的是父结点，也就是当前遍历的结点的处理顺序。

本文使用递归来遍历二叉树。

先序遍历

先序遍历说的就是遍历当前结点的时候，先输出当前结点，再输出左结点，最后输出右结点。

于是对于广义表：1(2,3)，就会输出：1, 2, 3

/**
 * 二叉树的先序遍历
 * @param {*} node 树
 */
function preorder(node) {
  // 遍历到当前结点的时候，先输出当前结点
  console.log(node.data);
  // 然后再进入左子树
  if (node.lchild !== null) {
    preorder(node.lchild);
  }
  // 最后进入右子树
  if (node.rchild !== null) {
    preorder(node.rchild);
  }
}
// 使用上面创建好的 root
// 会输出：1 2 4 5 3 6 7
preorder(root);
复制代码

中序遍历

中序遍历说的就是遍历当前结点的时候，先输出左结点，再输出当前结点，最后输出右节点。

于是对于广义表：1(2,3)，就会输出：2, 1, 3

/**
 * 二叉树的中序遍历
 * @param {*} node 树
 */
function inorder(node) {
  // 先输出左结点
  if (node.lchild !== null) {
    inorder(node.lchild);
  }
  // 再输出当前结点
  console.log(node.data);
  // 最后输出右结点
  if (node.rchild !== null) {
    inorder(node.rchild);
  }
}
// 输出：4 2 5 1 6 3 7
inorder(root);
复制代码

后序遍历

后序遍历说的就是遍历当前结点的时候，先输出左结点，再输出当右结点，最后输出当前节点。

于是对于广义表：1(2,3)，就会输出：2, 3, 1

/**
 * 二叉树的后续遍历
 * @param {*} node 树
 */
function postorder(node) {
  // 先输出左结点
  if (node.lchild !== null) {
    inorder(node.lchild);
  }
  // 再输出右结点
  if (node.rchild !== null) {
    inorder(node.rchild);
  }
  // 最后输出当前结点
  console.log(node.data);
}
// 输出：4 2 5 6 3 7 1
postorder(root);
复制代码