目录
一、树的介绍
1.定义 :
没有父结点的结点称为根结点，一棵树中有且只有一个称为“根”的结点；并且有若干个互不相交的子树，这些子树本身也是一棵树。
每个结点都只有有限个子结点或无子结点；每一个非根结点都有且只有一个父结点。
2.相关概念 :
1° 父结点和子结点——针对于两个结点的关系，被指向的结点称为子结点，指向该结点的结点称为父结点。如下图所示 :
2° 深度——令根结点为树的第一层，从根结点开始到最底层结点的层数称为树的深度。如下图所示 :
3° 叶子结点和非叶子结点——叶子结点指没有子结点的结点；非叶子结点指有子结点的结点，非叶子结点也叫非终端结点。如下图所示 :
4° 度——某一个结点的子结点的个数，称为该结点的度；对应地，取一棵树中度最大的结点的度，称为这棵树的度。如下图所示 :
3.简单分类 :
1° 一般树——任意一个结点的子结点的个数都不受限制。如下图所示 :
2° 二叉树——任意一个结点的子结点的个数最多有2个，且子结点的位置不可更改（即左子树和右子树），所以二叉树都是有序树。
Δ二叉树又可再分类 :
①一般二叉树
②满二叉树——在不增加树的层数的前提下，无法再向树中再多添加一个结点的二叉树，称为满二叉树。如下图所示 :
③完全二叉树——在满二叉树的前提下，从树的最下层最右边开始连续删除若干个结点，最后形成的树就是完全二叉树。即，除了最后一层外，其余层都是满结点。所以可以说，满二叉树就是完全二叉树的一种特例（一个结点不删）。完全二叉树如下图所示 :
3° 森林——n个互不相交的树的集合。（整体上称为森林）如下图所示 :
4.相关应用 :
1° 树是数据库中数据组织的一种重要形式。
2° 操作系统中子父进程的关系本身就是一棵树。
3° 面向对象语言中类的继承关系本身就是一棵树。
4° 哈夫曼树（最优树）是对树的重要应用。
二、树的存储
1.二叉树的存储 :
1° 二叉树连续存储
因为二叉树不是线性结构，因此——要用线性结构存储非线性结构，如果仅仅存储有效的结点，无法判断连续存储中谁先存谁后存的问题（解决方法——先序中序后序）；而且，如果仅仅存储有效的结点，无法根据所存的结点推断出树原先的形状。
所以，连续存储时，必须要求当前二叉树提前转化为完全二叉树。
Δ完全二叉树的两个优点——
①将不存在的结点虚拟化，相当于每个结点都有编号，那么根据当前结点的编号就可以推算出当前结点在树的第几层。
②查找某个结点的父结点和字结点速度很快，判断某结点有没有子结点速度也很快。
Δ完全二叉树的缺点——
①所需内存空间大，有内存的浪费。
2° 二叉树链式存储（常用）
链式存储，即像链表一样离散存储，如下图所示 :
树中的每个结点都分为了三部分——第一部分指向左子结点；第二部分用于保存有效数据；第三部分指向右子结点。
链式存储可以轻松解决连续存储中遇到的两个难题，因此链式存储较为简单。并且，链式存储可以仅存放有效结点，减少了内存空间的浪费，n个结点最多只浪费n + 1个内存空间。（空指针域的浪费）
2.普通树和森林的存储 :
1° 普通树的存储
同样是为了解决非线性结构用线性结构来存储的问题，常见的存储方式有4中——
①“双亲表示法” :
用结构体类型表示结点类型，在该结构体类型的数组中，每个结点元素分为两部分，一部分用于存放当前结点的数据，另一部分用于存放父结点的下标（其中，由于根结点没有父结点，因此根结点元素中存放的下标为-1）。如下图所示 :
②“孩子表示法” :
孩子表示法是一个“数组 + 链表”的格式，与双亲表示法类似，仍然是一个结构体类型的数组，只不过每个元素的第二部分变成了一个指针域，可以将子结点挂载到后面形成链表，如下图所示：
③“双亲孩子表示法” :
“双亲表示法”求父结点方便；“孩子表示法”求子结点方法。而“双亲孩子表示法”则同时兼具了“双亲表示法”和“孩子表示法”的优点。在“双亲孩子表示法”中，每个结点元素被分成了三部分，第一部分用于存储当前结点本身的有效数据，第二部分用于存储父结点的下标，第三部分是用于挂载子结点的指针域。说白了，就是把上面两种方法合起来了。如下图所示 :
④二叉树表示法 : （常用）
“双亲孩子表示法”虽然牛逼，但是不易通过程序来实际操作，因此平时使用更多的是“二叉树表示法”，顾名思义，就是将当前树转化为一棵二叉树，再进行存储。
一棵普通树转化为一棵二叉树的方法如下 :
任意一个结点需要满足两个条件——①左指针域指向它的第一个孩子（第一个子结点）；②右指针域指向指向它的下一个兄弟。如下图所示 :
2° 森林的存储
森林的存储和普通树类似，都使用了二叉树表示法，需要将森林先转换为二叉树。
森林转化为二叉树的方法同普通树转化为二叉树的方法类似 :
唯一不同的地方在于，需要先将森林中的树互相看作兄弟，那么就将森林转化为了一棵“没有根结点的树”；然后再按照普通树转化为二叉树的方法进行转化即可。如下图所示 :
三、树的遍历
1.二叉树先序遍历 :
先序遍历遵循三个原则——
①先访问根结点；
②再遍历左子树；
③再遍历右子树；
举个例子——如下图所示 :
上图是一棵普通二叉树，如果对它进行先序遍历，访问结果如何呢？
①首先访问整棵树的根结点A；
②然后先序访问A的左子树；A的左子树的根结点是D，所以接下来要访问D；
③接着访问D的左子树；D的左子树的根结点是I，所以接下来要访问I；接着访问I的左子树，因为I的左子树为空，所以接着访问I的右子树；因为I的右子树也为空，所以“I”这棵树访问完毕；I子树访问完毕，代表D的左子树访问完毕，接下来要访问D的右子树；
④又因为D的右子树也是一棵子树，所以要先访问该子树的根结点E；因为E子树的左子树为空，右子树也为空，所以E子树访问完毕；E子树访问完毕，代表D子树的左右子树都访问完毕；D子树访问完毕，代表A树的左子树访问完毕。
⑤接下来要访问A的右子树B；先访问根结点B；
⑥然后再访问B子树的左子树；因为B子树的左子树也是一棵树，所以要访问B子树的左子树的根结点F；
⑦接着，访问F子树的左子树J；先访问根结点J，因为J的左右子树都为空，所以J子树访问完毕；
⑧J子树访问完毕，代表F的左子树访问完毕，接下来要访问F子树的右子树；又因为F子树的右子树也是一棵树，所以接下里要访问根结点G；因为G子树的左右子树都为空，所以G子树访问完毕；G子树访问完毕，代表F子树的右子树访问完毕；F子树的右子树访问完毕，代表F子树访问完毕，代表B子树的左子树访问完毕；
⑨接下来要访问B子树的右子树，首先访问B子树的右子树的根结点C；
⑩再访问C子树的左子树，C子树的左子树为H，访问根结点H，因为H子树的左右子树均为空，所以H子树访问完毕；H子树访问完毕，代表了C子树的左子树访问完毕，接下来访问C子树的右子树；又因为C子树的右子树为空，所以C子树访问完毕；C子树访问完毕，代表B子树的右子树访问完毕；B子树的右子树访问完毕，代表B子树访问完毕；B子树访问完毕，代表A树的右子树访问完毕；A树的右子树访问完毕，代表A树访问完毕，即整棵树访问完毕。
最后的访问顺序是——ADIEBFJGCH。如下图所示 :
先序遍历的底层原理 :
用到了递归的思想！当我们想先序遍历某棵树时，必须首先去先序遍历该树的左子树，而要想遍历该树的左子树，又得去先序遍历该左子树的左子树，依次递归下去，直到某棵左子树的左子树为空了，再去遍历该子树的右子树，然后再递归回去，直到把整棵树遍历完毕。
2.二叉树中序遍历 :
中序遍历遵循三个原则——
①先遍历左子树；
②再访问根结点；
③再遍历右子树；
举个例子——如下图所示 :
上图是一棵普通二叉树，如果对它进行中序遍历，访问结果如何呢？
①先访问A的左子树D，又因为D不是一棵空树，所以要先访问D的左子树I，因为I的左子树为空，所以最先访问的是I子树的根结点I；
②接着，再访问I子树的右子树，因为I子树的右子树为空，所以I子树访问完毕；I子树访问完毕，代表D子树的左子树访问完毕，接下来访问根结点D；
③继续，遍历D的右子树，因为D的右子树E的左子树为空，所以接下来访问E子树的根结点E；
④然后，遍历E的右子树，因为E的右子树H的左子树为空，所以要访问根结点H；又因为H子树的右子树也为空，所以H子树遍历完毕；H子树遍历完毕，代表E子树的右子树遍历完毕；E子树的右子树遍历完毕，代表E子树遍历完毕，代表D子树的右子树遍历完毕；D子树的右子树遍历完毕，代表D子树遍历完毕，代表A树的左子树遍历完毕；
⑤所以接下来要访问A树的根结点A；
⑥继续，访问A树的右子树B，因为B子树的左子树不为空，所以要访问B子树的左子树F；又因为F的左子树为空，所以访问根结点F；又因为F子树的右子树为空，所以F子树遍历完毕；
⑦F子树遍历完毕，代表B子树的左子树遍历完毕，接下来访问B子树的根结点B；最后，遍历B子树的右子树，因为B子树的右子树为空，所以B子树遍历完毕；B子树遍历完毕，代表A树的右子树遍历完毕，整棵树遍历完毕。
最后的访问顺序是——IDEHAFB。如下图所示 :
3.二叉树后序遍历 :
后序遍历遵循三个原则——
①先遍历左子树；
②再遍历右子树；
③再访问根结点；
举个例子——如下图所示 :
上图是一棵普通二叉树，如果对它进行后序遍历，访问结果如何呢？
①先访问A树的左子树D，因为D也有左子树，所以先访问D树的左子树I；又因为I子树的左右子树均为空，所以最先访问的是I子树的根结点I；
②I子树访问完毕，代表D子树的左子树访问完毕；接下来访问D子树的右子树H，H与I同理，所以要访问根结点H；
③H子树访问完毕，代表D子树的右子树访问完毕；接下来访问D子树的根结点D；
④D子树访问完毕，代表A树的左子树遍历完毕，接下来要遍历A树的右子树B；B子树的左子树F不为空，所以要先遍历F子树；又因为F子树的左子树为空，所以接下来访问F子树的右子树的根结点G；
⑤G子树访问完毕，代表F子树的右子树访问完毕，所以接下来访问F子树的根结点F；
⑥F子树遍历完毕，代表B子树的左子树遍历完毕，接下来要遍历B子树的右子树C，所以接下来要访问的是B子树的右子树C的根结点C；
⑦C子树遍历完毕，代表B子树的右子树遍历完毕，接下来访问根结点B；
⑧B子树遍历完毕，代表A树的右子树遍历完毕，所以最后访问的是A树的根结点A；整棵树后序遍历完毕。
最后的访问顺序是——IHDGFCBA。如下图所示 :
其实，总结一下不难发现——二叉树的先序遍历，中序遍历和后序遍历，最大的区别就是对根结点的访问顺序不同。先序遍历先访问根结点（根左右）；中序遍历中间访问根结点（左根右）；后序遍历最后访问根结点（左右根）；而三者对于左右树的访问顺序是一致的，都是先左后右。
四、树的还原
1.概述
无论是先序，中序还是后序遍历，仅通过一棵二叉树的一种遍历结果，都无法还原出原本的二叉树。但是，假若我们可以得知某个二叉树的先序序列和中序序列，或者中序序列和后序序列，我们就可以推算出原始的唯一确定的一棵二叉树。（PS : 通过先序序列和后序序列也无法还原出原始的二叉树，即必须有一个是中序序列）。
2.已知先序和中序求后序 :
已知某棵二叉树的先序序列和中序序列，要想求出对应的后序序列，本质上还是要先还原出原始的二叉树，然后再去求它的后序序列。
Δ方法 :
1° 根据先序遍历“根左右”的特点，先序序列中先出现的结点一定是根结点；
2° 根据中序遍历“左根右”的特点，每个根结点的左面的结点一定位于该根结点的左子树上；每个根结点的右面的结点一定位于该根结点的右子树上。若中序序列中，某个根结点的左面或右面没有其他非根结点，说明该根结点的左子树或右子树为空。
Δ举栗 :
若已知某二叉树的先序序列为： ABDGHCEFI；中序序列为：GDHBAECIF。请画出该二叉树的初始形态，并求出其后序序列。
答 :
首先，根据先序序列“根左右”的特点，先序序列中第一个结点为A，说明A结点是整棵二叉树的根结点；
其次，根据中序遍历“左根右”的特点，中序序列中A结点左面的结点“GDHB”就一定在A结点的左子树上，而A结点右面的结点“ECIF”就一定在A结点的右子树上；
我们先来看A树的左子树。已知“GDHB”一定在A树的左子树上，那么谁是A树左子树的根结点？回到先序序列，“GDHB”在先序序列中先出现的是Ｂ结点，所以Ｂ结点就是Ａ树左子树的根结点；再来到中序序列，“GDHB”中，“GDH”均在Ｂ的左面，说明Ｂ结点的左子树不为空且由“GDH”这三个结点组成；而“GDH”中，最先在先序序列出现的是D结点，说明D结点就是B子树的根结点；继续，再来到中序序列，“GDH”中，G在D左面，H在D右面，所以可知D的左子树和右子树分别为G和H；D子树搞定，则B子树的左子树搞定，又因为在中序序列中，B和A直接没有其他的结点了，说明B子树的右子树为空，至此整个A树的左子树可以画出来，如下图所示 :
我们再来看A树的右子树。已知“ECIF”一定在A结点的右子树上，因为在先序序列中，C最先出现，所以A结点右子树的根结点就是C；又因为中序序列“ECIF”中，Ｅ在Ｃ的左面，“IF”在Ｃ的右面，所以Ｃ子树的左子树为Ｅ，而“IF”一定在C子树的右子树上；又因为“IF”在先序序列中Ｆ先出现，所以Ｆ为Ｃ子树右子树的根结点，而中序序列中“IF”I在F的左面，则表示I是Ｆ结点的左子树。至此，我们可画出原始的完整的二叉树——Ａ树的模样，如下图所示 :
接着，我们可以根据还原出的二叉树，写出它的后序序列——GHDBEIFCA。
3.已知中序和后序求原始二叉树 :
已知中序和后序求原始二叉树的方法，与已知先序和中序求原始二叉树的方法类似。只不过不同的地方在于——先序序列中是谁先出现谁是根结点；而后序序列中是谁后出现谁是根结点，反过来了。对于中序序列，仍然是根结点左面的结点位于该根结点的左子树上，根结点右面的结点位于该根结点的右子树上。
Δ方法 :
1° 根据后序遍历“左右根”的特点，后序序列中最后出现的结点一定是整棵树的根结点；
2° 根据中序遍历“左根右”的特点，每个根结点的左面的结点一定位于该根结点的左子树上；每个根结点的右面的结点一定位于该根结点的右子树上。若中序序列中，某个根结点的左面或右面没有其他非根结点，说明该根结点的左子树或右子树为空。
Δ举栗 :
若已知某二叉树的中序序列为：BDCEAFHG；后序序列为：DECBHGFA。请画出该二叉树的初始形态，并求出其先序序列。
答 :
首先，根据后序遍历“左右根”的特点，后序序列中最后一个结点为A，说明A结点是整棵二叉树的根结点；
其次，根据中序序列“左根右”的特点，中序序列中A结点左面的结点“BDCE”就一定在A结点的左子树上，而A结点右面的结点“FHG”就一定在A结点的右子树上；
我们先来看A树的左子树。"BDCE"这几个结点中，最后在后序序列出现的是B结点，说明B结点就是A树左子树的根结点；再回到中序序列，B结点左面没有其他结点，说明B结点的左子树为空，而B结点右边是"DCE"结点，说明B结点的右子树由“DCE”结点构成；继续，“DCE”中，最后在后序序列出现的是Ｃ结点，说明Ｃ结点是Ｂ结点的右子树的根结点；又因为中序序列中Ｄ在Ｃ左面，Ｅ在C右面，说明D和E分别为C结点的左右子树；至此，C子树搞定——>B子树的右子树搞定——>B子树搞定——>A子树的左子树搞定。我们可以先画出A树目前的样子，如下图所示 :
我们再来看A树的右子树。 “FHG”这几个结点中，最后在后序序列中出现的是F结点，说明F结点是A树右子树的根结点；又因为在中序序列中，“FHG”，F结点左面没有其他结点，说明F结点的左子树为空；F结点右面是“HG”结点，说明Ｆ结点的右子树不为空且由“HG”结点构成；根据后序序列中Ｇ结点后出现，说明Ｇ结点是Ｆ结点右子树的根结点。而中序序列中G结点右面没有其他结点，说明G结点的右子树为空，又因为Ｈ位于G左面，说明H是G结点的左子树的根结点。至此，G子树搞定——>F子树搞定——>A子树的右子树搞定。现在我们可以画出A树完整的原始的样子，如下图所示 :
五、树的程序演示
1.静态创建与遍历
以链式二叉树为例——
将如下二叉树静态创建出来并分别进行先序，中序和后序的遍历 :
代码如下 :
# include <stdio.h>
# include <malloc.h>
typedef struct BTreeNode
{
char data;
struct BTreeNode * pLeftChild;
struct BTreeNode * pRightChild;
} BTN, * PBTN; //B代表Binary，二进制
PBTN create_Tree(void);
void preTraversing(PBTN); //preorder，先序遍历
void inTraversing(PBTN); //inorder，中序遍历
void postTraversing(PBTN); //postorder，后序遍历
int main(void)
{
PBTN pTree = create_Tree();
printf("\n先序序列：");
preTraversing(pTree);
printf("\n中序序列：");
inTraversing(pTree);
printf("\n后序序列：");
postTraversing(pTree);
return 0;
}
PBTN create_Tree(void)
{
PBTN pA = (PBTN) malloc(sizeof(BTN));
PBTN pB = (PBTN) malloc(sizeof(BTN));
PBTN pC = (PBTN) malloc(sizeof(BTN));
PBTN pD = (PBTN) malloc(sizeof(BTN));
PBTN pE = (PBTN) malloc(sizeof(BTN));
pA->data = 'A';
pA->pLeftChild = pB;
pA->pRightChild = pC;
pB->data = 'B';
pB->pLeftChild = pB->pRightChild = NULL;
pC->data = 'C';
pC->pLeftChild = pD;
pC->pRightChild = pE;
pD->data = 'D';
pD->pLeftChild = pD->pRightChild = NULL;
pE->data = 'E';
pE->pLeftChild = pE->pRightChild = NULL;
return pA;
}
void preTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
printf("%c ", pRoot->data);
if (NULL != pRoot->pLeftChild)
preTraversing(pRoot->pLeftChild);
if (NULL != pRoot->pRightChild)
preTraversing(pRoot->pRightChild);
}
}
void inTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
if (NULL != pRoot->pLeftChild)
inTraversing(pRoot->pLeftChild);
printf("%c ", pRoot->data);
if (NULL != pRoot->pRightChild)
inTraversing(pRoot->pRightChild);
}
}
void postTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
if (NULL != pRoot->pLeftChild)
postTraversing(pRoot->pLeftChild);
if (NULL != pRoot->pRightChild)
postTraversing(pRoot->pRightChild);
printf("%c ", pRoot->data);
}
}运行结果 :
2.动态创建与遍历
动态创建二叉树，即二叉树的结点分配由程序员自主设计。
代码如下 :
# include <stdio.h>
# include <malloc.h>
# include <stdlib.h>
typedef struct BTreeNode
{
char data;
struct BTreeNode * pLeftChild, * pRightChild;
} BTN, * PBTN; //B代表Binary，二进制
PBTN create_Tree(PBTN);
void preTraversing(PBTN); //preorder，先序遍历
void inTraversing(PBTN); //inorder，中序遍历
void postTraversing(PBTN); //postorder，后序遍历
int main(void)
{
PBTN pTree = NULL;
pTree = create_Tree(pTree);
printf("\n先序序列：");
preTraversing(pTree);
printf("\n中序序列：");
inTraversing(pTree);
printf("\n后序序列：");
postTraversing(pTree);
return 0;
}
PBTN create_Tree(PBTN pRoot)
{
char value; //临时变量，用于表示当前结点的数据域
PBTN p; //临时变量，用于表示当前结点的指针
printf("请输入结点的值：value = ");
scanf("%c", &value);
getchar();
/*
getchar()这行代表很重要，
因为Windows操作系统中，输入Enter键达到的效果是"\r\n"，
所以需要getchar()函数来吃掉后面的'\n'，不然会直接将
剩下的\n赋值给下一次调用create_Tree函数时的value，使得运行结果达不到预期。
*/
if ('#' == value)
return NULL;
/*
当用户输入'#'时，返回NULL给主调函数，
表示上一级结点没有左孩子或者右孩子。
*/
p = (PBTN) malloc(sizeof(BTN));
if (NULL != p)
{
p->data = value;
}
else
{
printf("动态分配内存失败!");
exit(-1);
}
if (!pRoot)
pRoot = p; //如果当前根结点为空，就创建根结点。
printf("\n请输入%c结点的左子树的根结点\n", value);
p->pLeftChild = create_Tree(pRoot); //递归创建左子树
printf("\n请输入%c结点的右子树的根结点\n", value);
p->pRightChild = create_Tree(pRoot); //递归创建右子树
return p;
}
void preTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
printf("%c ", pRoot->data);
if (NULL != pRoot->pLeftChild)
preTraversing(pRoot->pLeftChild);
if (NULL != pRoot->pRightChild)
preTraversing(pRoot->pRightChild);
}
}
void inTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
if (NULL != pRoot->pLeftChild)
inTraversing(pRoot->pLeftChild);
printf("%c ", pRoot->data);
if (NULL != pRoot->pRightChild)
inTraversing(pRoot->pRightChild);
}
}
void postTraversing(PBTN pRoot)
{
if (NULL != pRoot)
{
if (NULL != pRoot->pLeftChild)
postTraversing(pRoot->pLeftChild);
if (NULL != pRoot->pRightChild)
postTraversing(pRoot->pRightChild);
printf("%c ", pRoot->data);
}
}运行效果 : (如下GIF图)
最后该二叉树的遍历结果如下图所示 :
可以看到，其实up就是把上面静态构建二叉树的实例又给大家演示了一遍????。当然，为了确定我们的程序能正常运行，这次up瞎写一个，如下GIF图所示 :
最后遍历的结果如下图所示 : 
我们可以根据先序序列和中序序列画出我们设计的二叉树，如下图所示 :
嗯，看着还不错。