0。前言至此，我们已经介绍了时序表、链表、栈、队列四种数据结构。它们有一个共同的特点，就是都是线性表，换句话说，它们都是线性结构，就像一根绳子。四种线性数据结构在【线性表】一文中已经介绍了线性表的定义，即由若干元素按照线性结构（一对一关系）组成的有限序列。关键词是一对一的关系。显然，在复杂的现实社会中，这种一对一的关系并不能更好地满足我们的需求。例如，在父母和多个孩子的关系中，一个父亲/母亲对应多个孩子。这显然不是一对一的关系，而是一对多的关系。那么此时我们如何描述这种一对多的关系呢？当然是用一对多关系的数据结构！有这样的数据结构吗？是的！本文将介绍这种数据结构——树及其特殊形式的二叉树。1.认识树1.0。什么是树？说到树木，大家脑海中第一个浮现的画面应该是这样的：图片来自网络。“多关系”特征的数据结构，因为树恰好可以很形象地解释这个特征。我们来分析一下。看上图这棵树（地上部分），它有根，从根枝往上，主干分叉出许多子树干，子树干继续分叉出许多小树枝，small树枝上有很多叶子...主干与次级树干是一对多的关系，次级树干与小树枝，小树枝与树叶。我们用圆圈来代表树干和树叶，把自然界中的树倒过来抽象出来。下图（为了方便，我们的数据都是字符类型）：一棵树可以看到，真正的树非常符合我们需要的数据结构，所以我们称这种数据结构为树（Tree）。1.1.名词和概念下面我们根据图片来认识一下树的相关名词。子树：树是有限集，子树是该集的子集。就像嵌套娃娃一样，一棵树包含它的子树。例如树T1的子树是树T2、T3、T4，树T2的子树是T5、T6。还有很多子树没有在上图中标出。节点（Node）：一个节点包括一个数据元素和几个指向其子树的分支。例如，在树T1中，节点A包括一个数据元素A和三个指向其子树的分支。上图中有17个节点。根节点（Root）：一棵树只有一个根，这是常识。在数据结构中，“根”是根节点。例如，节点A是树T1的根节点；节点C是树T1的子节点，是树T3的根节点。度：一个节点拥有的子树的数量。比如节点A的度数是3，节点G的度数是3，节点H的度数是1。叶子/终端节点：度数为0的节点称为叶子节点，很形象酒吧。例如，对于树T1，节点F、I、K、L、M、N、O、P和Q都是叶子。分支节点/非终端节点：与叶子节点相对，即度数不为0的节点。内部节点：顾名思义，树内部的节点，即不是树的节点根节点和叶节点。Child,Parent,Sibling,Cousin,Ancestor,Descendant的概念与家谱中的相同。例如对于节点B：节点A是它的父节点，节点E和F是它的子节点，节点C和D是它的兄弟节点，节点K是它的后代节点。层级（Level）：从根节点开始，根为第一层，根的子节点为第二层，依次递减。例如树T1中节点K的层级为4。深度/高度：指树的最大层级。例如树T1的深度为4。有序树：如果节点的子树是从左到右有序且不可逆序的，则为有序树，否则为无序树。对于有序树的孩子，最左边的孩子称为第一个孩子，最右边的孩子称为最后一个孩子。例如，如果树T1是一棵有序树，它的根节点的第一个孩子是节点B，最后一个孩子是节点D。1.2．树的递归概念前面已经介绍了树的概况和相关名词的概念，为了回答什么是树的问题，这里需要介绍三种常见的树结构。【空树】：空树，即没有节点的树。空树[只有根节点的树]：只有一个根节点，没有其他节点。只有根节点的树【普通树】普通树现在我们可以回答什么是树了：树（Tree）是N（N>=0）个节点的有限集。当N=0时，树是一棵空树当N=1时，树只有一个根节点当N>1时，除了一个根节点外，树的其余部分可以分成几个不相交的有限集，我们调用子树。一棵非空树只有一个根节点。父节点和子节点之间存在树的一对多关系。在树中，由于树和子树的概念，树的子树仍然是树，子树的子树仍然是树。比如：人的孩子还是人，人的孩子的孩子还是人。因为有父子孙的概念，所以根节点的子节点可以是其子树的根节点。举个例子：一个人对他的孩子来说是父亲，对他的父母来说就是儿子。这个概念就是递归的概念。即对于某个“物”，它的“孩子”与它本身并无本质区别。它做什么，它的“孩子”也会做什么。一路往下，“孙子”“曾孙”“曾曾孙”都是这样。为了说明递归的概念，我们将上图中的树递归分解为子树，下图中的每个区域都是一棵树（或子树）：递归求解树分解到最后，我们最终得到的是get可以说是一个叶子节点，或者说是一棵只有根节点的树。比如节点F、K、L。在分解的过程中，我们还可以发现，对于每一个节点，我们都可以把它看成是某棵树（子树）的根节点。例如，节点E和I是某个子树的根节点。这与一棵树只有一个根节点这一事实并不矛盾。这就好比我们说小明只能有一个亲生父亲，但不影响他是别人的父亲。整个过程就像在家谱上寻找祖先的后代。所以如果你对树的概念一无所知，你可以找一棵家谱查一查。至此，我们可以说树的定义是一个递归定义。一棵树是由一个根节点和它的子树组成的，子树也是由一个根节点和它的若干个子树组成的……也就是说，在树定义中使用了Treedefinitions。1.3.树和线性表对比看图直观感受什么是一对一关系（前驱节点和后继节点）什么是一对多关系（父节点和子节点）节点）。2.理解二叉树2.0。什么是二叉树？什么是二叉树？首先，它必须是一棵树，其次，它必须是二叉树。之前已经初步知道了这棵树，它的节点的子节点的数量是无限的，也就是想要多少孩子，就需要多少孩子，想要多少叉子。二叉树限制了孩子的数量，即每个节点最多只能有两个孩子（左孩子和右孩子），比如它是“二孩子树”。二叉树中节点A的左孩子是节点B，右孩子是节点C。二叉树是一棵有序树，其中每个节点最多有两个子树（即每个节点的度数最多为2).2.1.二叉树的几种形式1.空二叉树2.只有根节点的二叉树3.左子树空的二叉树4.右子树空的二叉树5.左右子树都为空的二叉树2.2.满二叉树和完全二叉树满二叉树的特点是“满”，即每一层的节点数都是最大节点数。满二叉树T2第三层没有达到最大节点数，少了一个节点；T3第四层没有达到最大节点数，少了7个节点。完全二叉树是相对于满二叉树而言的，见下图：红色部分为编号二叉树是有序树，满二叉树和完全二叉树按照“自上而下”的顺序进行,从左到右”数字，如上所示。完全二叉树中所有节点的编号必须与完全二叉树中相同编号的节点的位置完全相同。也就是说，一棵完全二叉树的节点不能按照“从上到下，从左到右”的顺序被打断。T3的节点C没有左孩子，并且在该顺序中明显被中断。3.二叉树遍历3.0。如何穿越？在线性表中，我们的遍历非常简单粗暴，找到线性表的头部，使用循环直接走到线性表的尾部，完成遍历。在树中，我们不能再做这么简单粗暴的事情了，因为树是一对多的关系，所以从头到尾的遍历是不可能的。遍历的本质是打印出元素线性排列的顺序。（遍历不仅仅是打印，为了方便，我们的遍历是打印元素。）遍历树的矛盾在于我们的树不是线性的。为了解决这个矛盾，我们能不能约定一个顺序，树的元素按照这个顺序线性排列，然后从头到尾遍历是一件简单粗暴的事情？答案是肯定的。我们知道树是递归定义的，二叉树递归由根节点、左子树、右子树三部分组成。所以我们必须同意的是这三个部分中的哪一个先出现。按照人们从左到右写的约定，我们也约定了先左子树后右子树的顺序（当然也可以先右后左），那么根节点只有三个地方放置。根节点>>左子树>>右子树，称为前序（root）遍历左子树>>根节点>>右子树，称为中序（root）遍历左子树>>右子树>>根节点，称为后序（root)遍历约定好后，只需要按照顺序递归，就像找家谱一样。我们以遍历下图中的二叉树为例：为了方便，我们绘制null，并用颜色标记所有子树。3.1.前序遍历前序遍历的递归描述如下：如果二叉树为空，则不进行操作；点击这一步？左孩子节点和右孩子节点呢？前面说过一句话：对于每一个节点，我们可以把它看成是一棵树（子树）的根节点。就像你的儿子将成为别人的父亲一样。所以我们只要递归访问根节点，递归的把每个节点都变成“根节点”，就可以完成遍历。所以与其说是遍历节点，不如说是遍历“根节点”。我们只是递归地找出“所有根节点”并输出它们。（因为每个节点都可以看作一个根节点）所以遍历的重点是把所有的节点都转化为根节点，又因为每棵树只有一个根节点，所以我们要不停地递归分解子树（先把左边的子树，然后是右子树）直到它到达NULL。过程如下：前序遍历顺序为：ABDEGCF如果觉得文字描述不够直观，可以在我之前写的文章[1]中找到二叉树遍历过程的动态图。3.2.中序遍历中序遍历的递归描述如下：如果二叉树为空，则不进行操作；否则：中序遍历左子树访问根节点。右子树的中序遍历过程如下：中序遍历的顺序为：DBGEACF3.3。后序遍历后序遍历的递归描述如下：如果二叉树为空，则不进行任何操作；遍历顺序为：DGEBFCA4。总结概念和原则是实践的基础。如果不了解这些，那么代码实现就无从下手。这里先介绍一下二叉树的概念和原理。参考[1]二叉树遍历过程动态图：https://blog.csdn.net/m0_47335900/article/details/106157797[2]GitHub：https://github.com/xingrenguanxue/Simple-DS-and-Easy-Algo[3]Gitee：https://gitee.com/xingrenguanxue/Simple-DS-and-Easy-Algo
