分割咱们：有道技术团队助手：ydtech01 / 邮箱：mailto:ydtech@rd.netease.com

前言

树形构造，尤其是二叉树，在咱们平时开发过程中应用频率比拟高，但之前对于树形构造没有一个比拟零碎全面的理解和认知，所以借此机会梳理一下。

本文属于《你真的理解二叉树吗》系列文章之一，次要介绍的是树形构造的根底，在看完这篇文章之后，如果想要更加熟练掌握二叉树的话，能够看另一篇《你真的理解二叉树吗（手撕算法篇）》（下周公布）。

一、树形构造根底

相较于链表每个节点只能惟一指向下一个节点（此处说的链表是单向链表），树则是每个节点能够有若干个子节点，因而，咱们一个树形构造能够如下示意：

interface TreeNode {  data: any;  nodes: TreeNode[]}

1.1 树的度

PS: 在图构造中，也有度的概念，分为出度和入度，如果把树看作是图的一部分的话，那么严格来说，树的度其实是出度。不过，在树形构造中，咱们通常把度这个概念作为形容以后树节点有几个子节点。

即每个节点领有几个孩子，因而，二叉树的度最大是 2，链表（能够看成只有一个孩子的树）的度最大是1。

  • 定理： 在一个二叉树中，度为 0 的节点比度为 2 的节点多1。
  • 证实： 如果一个树有 n 个节点，那么，这棵树必定有 n-1 条边，也就是说，点的数量=边的数量+1(这个论断针对所有树形构造都实用，不仅仅是二叉树)如下图：

这个棵树有 7 个节点，节点与节点之间的连线，也就是边只有 6 条。

那么，咱们假如度为 0 的节点数量为 n0,度为 1的节点为数量 n1，度为 2 的节点数量为 n2，又因为是度为0的节点，阐明他的边的数量 N0=0，度为 1 的节点边的数量为 N1=n1 1，度为 2 的节点边的数量为 N2=n2 2，那么总共的节点数量为：

#由上可知，边数量的表达式如下

N0=0;

N1=1*n1;

N2=2*n2;

#由上可知，节点的数量=边的数量+1

n0 + n1 + n2 = N0 + N1 + N2 + 1;

#代入N0,N1,N2得：

n0 + n1 + n2 = 0 + n1 + 2*n2 + 1;

#化简得：

n0 = n2 +1;

#即度为0的节点数量永远比度为2的节点多一个

由此，咱们就证实了下面的定理，咱们把这个定理换个形容或者更容易了解：

在二叉树中，只有你晓得了有多少个叶子节点，那么度为2的节点数量就是叶子节点的数量减1，反之，晓得度为2的节点数量，那么叶子节点的数量就是度为2的节点数量加1。

1.2 树的遍历

    5   / \  1   4     / \    3   6

1.3 树的遍历思维

树天生就是一个适宜递归遍历的数据结构，因为每一次解决左子树和右子树的时候，其实就是递归遍历的过程。

  • 前序遍历：「根节点」「递归遍历左子树的输入后果」「递归遍历右子树的输入后果」
  • 中序遍历：「递归遍历左子树的输入后果」「根节点」「递归遍历右子树的输入后果」
  • 后序遍历：「递归遍历左子树的输入后果」「递归遍历右子树的输入后果」 「根节点」

1.4 思维发散

看到这里，有一些小伙伴可能会感觉似曾相识，是不是在哪里看过树相干的一些常识呢。其实在之前咱们学习栈这个数据结构的时候，就有探讨过这个话题。

咱们晓得，栈天生适宜用于表达式求值，那么，它在解决表达式求值的过程中，是怎么的一个逻辑构造呢？

如：3*(4+5) 这个表达式。其实，尽管咱们在解答的时候，应用的是栈的思维，但实际上在逻辑层面，咱们是在模仿一棵树的操作过程。不置信？那咱们来看看：

        [ * ][ 3 ]             [ + ]           [ 4 ]        [ 5 ]

下面，咱们将这个表达式拆借成了一个树形构造，当咱们表达式中遇到 () 时，阐明外面的子表达式须要优先解决，那么，咱们就把他看作是咱们二叉树的一个子树。

咱们都晓得，树的遍历思维是递归遍历， 是由下往上逐层解决问题，这样，在递归调用的过程中，他就会先解决右子树的子问题，失去后果之后，再与左子树计算出来的后果进行最终运算得出最终后果。

1.5 还原二叉树

如果咱们已知前序遍历后果、中序遍历后果、后续遍历后果三者中的任意两个，咱们就可能残缺的还原一颗二叉树。例如：

# 前序遍历输入后果1 5 2 3 4# 中序遍历输入后果5 1 3 2 4

下面是两种遍历形式的输入后果，咱们晓得，前序遍历的第一个节点肯定是根节点，所以，此时，咱们就曾经晓得，原二叉树的根节点为 1，接下来，咱们拿这个 1 的节点到中序遍历的输入后果中，找到1的地位。

又因为中序遍历的输入后果是左根右，那么，咱们不难晓得，在 1 右边的就是原二叉树的左子树的中序遍历输入，在1左边的就是原二叉树的右子树的中序遍历输入。这样，咱们就能够把中序遍历输入分成以下几块：

# 切割中序遍历后果        5            1            3 2 4 # 左子树        根          右子树# 由上可知，咱们左子树就曾经进去了，就只有一个节点，就是5，然而右子树还是一个序列，那么咱们持续往下走。# 由上，咱们曾经晓得了原二叉树的左子树序列、和右子树序列，那么，咱们也来切割以下前序遍历后果        1            5            2 3 4#        根        左子树     右子树#切割了前序遍历后果之后，咱们找到右子树的序列，他的序列的第一位就是右子树的根节点，也就是2，找到根节点后，就很简略了，反复下面的步骤，在二叉树的中序遍历后果的右子树中就能找到右子树的左子树和右子树别离为3和4，到此，我么就曾经还原了这颗二叉树了    1   / \  5   2     / \    3   4

下面只有5个节点的树，是不是很简略呢？接下来，咱们再来一个略微难一点的的思维题：

已知10个节点的二叉树的前序遍历后果和中序遍历后果，还原这个二叉树。

前序遍历输入序列：1 2 4 9 5 6 10 3 7 8

中序遍历输入序列：4 9 2 10 6 5 1 3 8 7

# 由2.可知，1是根节点，所以左子树序列：4     9     2     10     6     5 ；右子树序列：3     8     71.中序：             4     9     2     10     6     5             1                         3     8     7        # 断言：1是根节点2.前序：                1         2     4     9     5     6     10                             3     7     8        # 由1.2可知，2是根节点，所以左子树序列：4     9 ；右子树序列：10     6     51.1中序：            4     9             2             10     6     5                                    # 断言：2是根节点1.2前序：            2                4     9        5     6     10                                     # 由1.2.1可知，4是根节点，所以9是右子树1.1.1中序：            4        9                                                                # 断言：4是根节点1.2.1前序：            4        9                                                                # 由1.2.2可知，5是根节点，所以左子树序列为：10        61.1.2中序：            10        6        5                                                        # 断言：5是根节点1.2.2前序：            5        6        10                                                        # 由1.2.2.2可知，6为根节点，所以10位左子树1.1.2.1中序：        10        6                                                                # 断言：6为根节点1.2.2.2前序：        6        10                                                                # 由2.2可知，3位根节点，所以右子树序列为：8        72.1中序：            3        8        7                                                        # 断言：3为根节点2.2前序：            3        7        8                                                        # 由2.2.2可知，7为根节点，所以8为左子树2.1.1中序：            8        7                                                                # 断言：7为根节点2.2.2前序：            7        8                                                                # 最终二叉树长成这样                 1                /       \            2         3          /    \       \         4      5       7          \    /       /           9  6       8             /            10

1.6 二叉树的常见分类

1.6.1 齐全二叉树（Complete Binary Tree）

只有在最初一层的右侧短少节点的二叉树叫做齐全二叉树，也就是说，齐全二叉树的左侧是满的，只有右侧才容许有空节点。
                  1            /           \           2             3          /   \         /  \         4     5       6

齐全二叉树是一个十分优良的一个数据结构，它有以下两个次要的特点，可能让咱们在性能和程序实现上有更好的体验。

节点编号可计算

从下面的齐全二叉树中，咱们能够看出一个法则：

编号为 n 的节点，他的左子树根节点的编号必然为 2n，他的右孩子的根节点的编号必然为 2n+1，如上图2的左子树根节点的编号为4，就是2 2=4。右子树根节点的编号为5，也就是2 2+1=5。

那么利用这个法则，咱们能够干什么呢？

咱们晓得，一般的二叉树，除了存储数据用的数据域之外，还须要额定的存储空间用来存储左子树和右子树的指针，也就是指针域。如果咱们能通过下面的法则间接计算出以后节点左子树和右子树根节点的编号，那是不是就不须要额定的存储空间去存储左右子树的存储地址了，当一个树足够大的时候，这能够给咱们节俭相当大的一个存储空间。

下面通过计算来代替记录存储地址的办法，引申出一个咱们在日常工作中常常会应用到的一个算法思维：记录式与计算式思维的转换

  • 记录式（节省时间，消耗空间，无需计算，间接取值，即：空间换工夫）： 把信息存起来，用到的时候取出来用。
  • 计算式（节俭空间，消耗工夫，无需存储，计算取值，即：工夫换空间）：通过计算失去的，如1+1=2中的2就是咱们通过计算 1+1 这个表达式失去的后果。

这两种形式各有各的优缺点，脱离问题自身比拟这两种形式的优劣是没有意义的，咱们应该联合具体问题，看应用哪种形式能给你带来更大的收益。

场景一：当内存空间无限，对计算工夫要求不强时，如在一个内存较小的机器中运行一段程序，咱们会抉择计算式，用工夫换空间。

场景二：当咱们内存空间足够大，并且对计算速度有要求时，如企业级应用服务器上运行实时计算数据时，咱们会抉择记录式,用空间换工夫，因为一个企业级的利用，个别内存是足够大的，还能够动静扩容，这时候，工夫所带来的效益就远大于空间所带来的的效益了。

可应用间断的存储空间存储

除了节点编号（即节点地址）可计算这个个性外，齐全二叉树因为他的编号是间断的，从上到下升序且间断的序列，因而，咱们能够把齐全二叉树存储在一个间断的存储区，如:数组中，数组下标为 0 的元素寄存1号节点，为1的元素寄存2号节点。

利用这个个性，咱们在实现一个齐全二叉树时，能够无需像实现一般二叉树一样独自定义一个构造，并别离定义数据域和指针域来别离存储数据和指针，咱们齐全能够应用一个数组间接存储数据，这也是咱们齐全二叉树最常见的表现形式。

咱们来设想一下：你在程序中实现时用的是一维的线性构造，即数组来示意的，但在你的脑海里，应该要把它转化为二维的树形构造来思考问题，这也是一个绝对高级的编程逻辑思维能力，让咱们可能在脑海中将看到的数据结构“编译”成它真正运行时的模样。

当然，要有这样的能力，可不是久而久之的事件，须要通过大量的锤炼能力具备这种能力，至多，笔者写下此行的这一刻，是没方法达到这个境界的。

1.6.2 满二叉树（Full Binary Tree）

没有度为1的节点的二叉树叫做满二叉树，即所有节点要么没有子节点，要么有两个子节点。

PS: 咱们常常在网上看到很多文章博客上会把完满二叉树的定义放在满二叉树上，其实是谬误的，完满二叉树的具体定义见下文。

                  1            /            \           2              3         /   \           /  \        4     5            6    7             / \            8   9

1.6.3 完满二叉树（Perfect Binary Tree）

所有节点的度都为2。由此能够看出完满二叉树的定义还是与满二叉树有区别的。咱们能够说完满二叉树是非凡的满二叉树。
                  1            /           \           2             3         /   \          /  \        4     5           6    7

二、树结构深刻了解

2.1 节点

树的节点代表一个汇合，子节点就代表在父汇合下互不相交的子集，这样说可能难以了解，那么，咱们来看上面的一个图：

      5  /       \ 2         3# 下面的二叉树，5节点，咱们能够把它当做是一个选集，而上面的两个子节点2和3则是这个选集下的两个互不相交的子集，两个子集相加应该等于选集

由上图咱们能够得出一个论断：

树的一个节点代表一个汇合，而子节点代表选集上面互不相交的子集，所有的子集相加可能失去选集。

2.2 边

树的每一条边代表关系。

三、学习二叉树的作用

3.1利用于各种场景下的查找操作

因为二叉树构造包含人造递归结构、与二分思维完满符合的个性，使得二叉树及其各种变种构造极其适宜在各种场景下进行高效的查找操作，咱们计算机底层也有诸多设计时基于二叉树与二叉树变种构造的，便是因为其优良的性能可能提供高效而稳固的查找效率。

3.2 有助于了解高级数据结构的根底

  • 齐全二叉树（保护汇合最值的神兵利器）

    • 堆
    • 优先队列

  • 多叉树/森林

    • 解决字符串及相干转换问题的神兵利器

      • 字典树
      • AC自动机

    • 解决连通性问题的神兵利器

      • 并查集

  • 二叉排序树

    • 语言规范库中重要的数据检索容器的底层实现

      • AVL树（二叉均衡树）
      • 2-3树（二叉均衡树）
      • 红黑树（二叉均衡树）

  • 文件系统、数据库底层的重要数据结构

    • B树/B+树(多叉均衡树)

3.3 练习递归技巧的最佳抉择

学习递归的顶层思维形式:

设计/了解一个递归程序：

  1. 数学归纳法 => 构造归纳法

若 k0 是正确的，假如 ki 是正确的，那么 k(i+1) 也是正确的。如求解斐波那契数列：

function fib(n) {    // 首先要确定k0是正确的，也就是前提条件（边界条件）是正确的，在这题中，k0就是n=1时，后果为1，n=2时，后果为2    if(n <= 2) return n;  return fib(n - 1) + fib(n - 2);}
  1. 赋予递归函数一个明确的意义

下面代码中，fib(n)代表第n项斐波那契数列的值。

  1. 思考边界条件

在下面的代码中，咱们的边界就是已知条件，n=1 时为 1，n=2 时为 2，须要对这个边界进行非凡解决。

  1. 实现递归过程

解决完边界问题后，就能够递归持续往下走了。

如果让你设计一个二叉树的前序遍历的程序，你会怎么设计呢？

  1. 函数意义：前序遍历以root为根节点的二叉树；
  2. 边界条件：root为空时无需遍历，间接返回root；
  3. 递归过程：别离前序遍历左子树和前序遍历右子树。
// 函数意义：前序遍历以root为根节点的二叉树function pre_order(root) {  // 边界条件：root为空时无需遍历，间接返回root  if(!root) return root;  console.log(root.val);  // 递归过程：别离前序遍历左子树和前序遍历右子树  pre_order(root.left);  pre_order(root.right);}

3.4 应用左孩子有兄弟法节俭空间

将任意的非二叉树转换成二叉树，如将一个三叉树转换成二叉树：

# 留神，要始终保障二叉树的右边是子节点，左边是兄弟节点# 原三叉树          1        / | \       2  3  4         / \        5   6                    # 依照左孩子右兄弟的形式转换成二叉树         1        /       2        \         3        /  \       5    4        \         6# 因为2是1的孩子，所以放在左子树，因为3是2的兄弟，所以放在2的右子树，4是3的兄弟，放在3的右子树，5是3的孩子，放在3的左子树，6是5的兄弟，所以放在5的右子树

大家能够发现，当只是将一棵树通过左孩子右兄弟法转换成二叉树时，根节点的右子树始终为空，那么，咱们是不是能够无效地利用这个右子树，把多棵树合并到一棵二叉树中呢？例如上面的示例，就是将两颗二叉树合并到了一起，造成了森林。

# 如果要把上面的两棵树合并到一个二叉树中呢          1                 7        / | \             /    \       2  3  4           8      9         / \        5   6           1     /           \    2             7     \           /      3         8    /   \        \   5     4        9    \     6# 这样，咱们就将两棵树合并成一颗树了，也就是森林了。这棵树看似一颗二叉树，但其实示意的是两棵树组成的森林

家喻户晓的Alpha Go的算法源码中实现的蒙特卡罗树搜索算法框架的具体实现算法，称之为信念下限树算法（UCT）就是采纳了左孩子右兄弟法实现的一颗搜寻树，用来示意整个棋盘的场面，失常来说，如果要存储一个棋盘的场面的话，会存储一个树形的构造中，但因为棋盘场面状况太多了，有可能造成一个 100 多叉以上的树，在Alpha Go 中为了防止这种状况，就把这个100多叉树通过左孩子有兄弟的表示法转换成了二叉树。有趣味的同学能够去看一下 pachi。

那么，为什么说这种形式可能节俭空间呢？大家想想，一个三叉树，他的每个节点都会有三个指针域用于存储他的子树，不论是否有子树，都要预留这些空间，如下面的三叉树，有6个节点，总共有18个指针域，其中无效的指针域只有 5 个（所谓无效指针域就是指针域不是指向空的，即边的数量=节点数量 -1 ），那么就还有 18-5=13 个指针是空着的。如果采纳左孩子右兄弟的形式转换成二叉树，咱们来看看总共有 12 个指针域，而无效指针域有 5 个，那么就只有 12-5=7 个指针域空着，显著比之前的 13 个节俭了大量空间。

一个领有n个节点的k叉树，他最多会有 k * n 条边，他的边实际上只有 n-1 条，那么他节约了：kn - (n-1)=(k-1)n+1条边，这就意味着，当咱们分叉越多，咱们节约的空间就会越多，所以，咱们要把k叉树转换成二叉树，因为二叉树节约的边为：n+1，只跟咱们理论存储数据的节点无关。

四、结语

到了这里，咱们对于二叉树的一些基础知识就聊的差不多了，为了管制篇幅以及不同根底的小伙伴的接受程度，就不再开展更深的探讨了。原本还要跟大家一起刷一刷对于二叉树的算法题坚固一下二叉树的一些相干常识的，不过这样就会导致这篇文章又臭又长，所以，还是把它拆分成两篇文章吧。