-
【数据结构】树形结构——树的定义和术语
树形结构是一类重要的非线性数据结构。在客观世界中广泛存在的各种层次结构都可用树形结构来表示，如社会组织机构、人类社会的族谱等。本章首先引入树和二叉树的基本概念，重点介绍二叉树的存储结构及其各种操作，研究树和森林与二叉树的转换关系，并讨论树的典型应用问题。
目录
一、树的定义和术语
直观地看，树形结构是数据元素（结点）之间有分支，并且具有层次关系的结构，可用于表示数据元素之间存在的一对多关系。
1. 树的定义
树是由n(n>=0)个结点构成的有限集合，当n=0时称为空树。若树非空，则具有以下两个性质：
（1）有且仅有一个特定的结点，称为根。
（2）其余的结点可分为m个互不相交的集合T1,T2,……,Tm，其中每一个集合都是一棵树，并且称为根的子树。
2. 树的基本术语
树结点：树中一个独立单元。包含一个数据元素及若干指向其子树的分支。
树根：树中唯一没有前驱的结点。
结点的度：结点拥有的子树数，称为结点的度。
数的度：树中各结点的度的最大值。
树叶：度为0的结点。
双亲和孩子：把一个树结点的直接前驱称为该结点的双亲；反之，把一个树结点的所有直接后继称为该结点的孩子。
兄弟：同一双亲的孩子之间互称兄弟。
树的层次和深度：从根算起，根为第一层，根的孩子为第二层，树中任一结点的层次等于它的双亲的层次加1。树中各结点层次的最大值称为树的深度或高度。
有序树和无序树：如果树中结点的各子树可看成从左至右是有次序的（即不能互换），则称该树为有序树，否则称为无序树。在有序树最左边子树的根称为第一孩子，最右边子树的根称为最后一个孩子。
森林：m(m>=0)棵互不相交的树的集合。对树中每个结点而言，其子树的集合即为森林。由此也可以以森林和树的相互递归定义来描述树。
3. 树的表示
树除了可以用图形表示之外，还有多种表示方法：广义表表示法、层号表示法、凹入表示法、以嵌套集合表示法等
4. 树的遍历
在树的应用中，经常会要求对树中的所有结点进行访问，且每个结点仅访问一次，这就是树的遍历。可把对结点的访问看成打印结点的关键字、数据项或结点编号，把遍历看成是按序输出结点表。对于树结构来说，就需要按照某种特定次序来规范对树中所有的结点进行访问。具体的遍历方式有先序遍历和后序遍历两种。
下面用递归方式定义这两种遍历：
（1）若T是一棵空树，那么对T进行先根和后根遍历所得到的结果都是空。
（2）若T是一棵单节点树，那么对该树进行先根和后根访问所得到的结果是该结点本身。
（3）若T是由一个根结点n和m棵不相交的子树构成，则：
① 树的先根遍历：首先访问根结点n；其次依次按先根遍历T1，按先根遍历T2……直到最后先根遍历Tm。
② 树的后根遍历：先按后根遍历n的所有子树，最后访问根结点n。
二、二叉树
二叉树就是度为2的有序树，是最重要的一种树形结构。二叉树的存储和处理比普通树简单，同时普通树都可以方便地转化为二叉树来存储和处理
1. 二叉树的定义
二叉树是一种特殊的树形结构。定义如下：
（1）由n(n>=0)个结点所构成的集合，此集合可以为空。
（2）二叉树的根结点下可分为两个互不相交的子树，子树有左右之分，次序不能任意颠倒，称为左子树和右子树，且左右子树均为二叉树。
2. 二叉树的性质
二叉树是有序树的特例，具有下列重要性质：
（1）在二叉树的第i层上至多有 2^(i-1) 个结点（i>=1）。
（2）深度为k的二叉树至多有2^k-1个结点（k>=1）。
（3）对任意一棵二叉树T，如果其终端点数为n0，度为2的结点树为n2，则n0=n2+1。
（4）具有n个结点的完全二叉树的深度为[log2n]+1，[log2n]为不大于logn的最大整数。
注：① 特别的，一棵深度为k且有2^k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层上的结点数都是最大结点数。
② 对满二叉树的结点进行连续编号，约定编号从根结点起，自上而下，自左至右。由此可引出完全二叉树的定义。深度为k、有n个结点的二叉树，当且仅当其每一个结点都与深度为k的满二叉树中编号从1~n的结点一一对应时，称为完全二叉树。完全二叉树具有的特点是：1.叶子结点只可能在层次最大的两层上出现。2.对任一结点，若其右分支下的子孙的最大层次为r，则其左分支下的子孙的最大层次必为r或r+1。
（5）如果对一棵有n结点的深度为[log2n]+1，完全二叉树的结点按层序编号，同层按从左至右，则对任一结点i（1<=i<=n）。于是有：
① 如果i=1，则结点i是二叉树的根，无双亲；如果i>1，则其双亲是结点[i/2]。
② 如果2i>n，则结点i无左孩子（结点i为叶子结点）；否则，其左孩子是结点2i。
③ 如果2i+1>n，则结点i无右孩子；否则，其右孩子是结点2i+1。
3. 二叉树的存储结构
通常，二叉树可以采用以下两种存储结构
3.1 顺序存储结构
用一组地址连续的存储单元存储二叉树中的各个结点。为了便于对二叉树结点进行查找或处理，存储时需要将普通二叉树的各个结点按照它们在完全二叉树的对应结点位置依次存放到数组相应的存储单元中。二叉树的顺序存储结构定义如下：
- #define TREEMAX 1000
- ElemType SqTree[TREEMAX];
一般来说，顺序存储结构只适用于完全二叉树或满二叉树的存储，因为普通二叉树采用顺序存储结构进行存储时，将导致存储单元的浪费。最坏情况下，对于一个深度为k且只有k个结点的右支树来说，存储时需要2^k-1个单元。
3.2 链式存储结构
采用链式存储结构存储二叉树时，可以根据树中的结点树动态申请所需要的结点，从而避免存储空间的浪费。
可以设计不同的结点结构来构造二叉树不同形式的链式存储结构。
由二叉树的定义可知，每个二叉树的结点由一个数据元素和分别指向其左、右子树的两个分支组成。因此，定义二叉树的结点结构时至少应包含三个域：数据域和左、右指针域。其中，数据域保存结点的信息；左指针域存放指向其左子树根的信息；右指针域存放指向其右子树根的信息。有时，为了便于找到结点的双亲，则可在上述结点结构中增加一个指向其双亲结点的指针域。利用这两种结点结构所得的二叉树的存储结构分别称为二叉链表和三叉链表。
在实际应用中多采用二叉链表的表示方式，下面给出二叉链表的结点结构定义：
- typedef struct BitNode{
- TElemType data;
- struct BitNode *lchild,*rchild;
- }BitNode,*BiTree;
4. 二叉树的三种遍历方法
二叉树的遍历是指按照一定次序访问树中所有结点，并且每个结点仅被访问一次的过程。它是二叉树最基本的运算，也是二叉树中所有其他运算的基础。遍历二叉树的实质是对二叉树的线性化过程，即遍历的结果是将非线性结构的树中结点排成一个线性序列，二叉树的遍历按访问根节点的先后次序不同，可分为先序遍历、中序遍历和后序遍历。
下面对二叉树的遍历讨论中，二叉树都采用二叉链表的存储结构。
4.1 二叉树的先序遍历
根据二叉树的递归特性，先序遍历二叉树的递归过程如下：
（1）访问根结点
（2）先序遍历左子树
（3）先序遍历右子树
- void PreOrder(BiTree p)
- {
- if(p!=NULL)
- {
- printf("%c",p->data); //访问根结点
- PreOrder(p->lchild); //先序遍历左子树
- PreOrder(p->rchild); //先序遍历右子树
- }
- }
从上面的算法中可以看出，先序遍历的递归过程简短而易于理解。依照递归算法执行过程中递归工作栈的状态变化状况可以直接写出相应的非递归算法。非递归算法中借助栈来完成整个遍历过程。算法的基本步骤如下：
（1）当前指针指向根结点。
（2）若结点不为空，访问该结点。
（3）若结点右孩子不为空，则右孩子进栈。
（4）当前指针指向结点左孩子重复步骤（2）~（3），直至左孩子为空。
（5）依次退栈，当前指针指向出栈结点。
（6）若栈非空或当前指针非空，继续步骤（2），直至结束。
由此可以写出先序遍历的非递归算法：
- void Preorder_n(BitTree p)
- {
- BiTree stack[MAX],q;
- int top=0,i;
- for(i=0;i<MAX;i++) stack[i]=NULL;
- q=p;
- while(q!=NULL)
- {
- printf("%c",q->data); //访问当前结点
- if(q->rchild!=NULL) stack[top++]=q->rchild; //当前结点右孩子进栈
- if(q->lchild!=NULL) q=q->lchild; //左子树不为空，进入左子树
- else if(top>0) q=stack[--top]; //左子树为空，栈不空，出栈
- else q=NULL;
- }
- }
4.2 二叉树的中序遍历
中序遍历二叉树的递归过程如下：
（1）中序遍历左子树
（2）访问根结点
（3）中序遍历右子树
- void InOrder(BiTree p)
- {
- if(p!=NULL)
- {
- InOrder(p->lchild); //中序遍历左子树
- printf("%c",p->data); //访问根节点
- InOrder(p->rchild); //中序遍历右子树
- }
- }
同样也可以利用栈来实现中序遍历的非递归算法，算法的基本步骤如下：
（1）当前指针指向根结点。
（2）当前指针进栈，当前指针指向其左孩子。
（3）重复步骤（2），直至左孩子为空。
（4）依次退栈，输出当前指针所指结点。
（5）将当前指针指向右孩子。
（6）若栈非空或当前指针非空，执行步骤（2），直至结束。
4.3 二叉树的后序遍历
后序遍历二叉树的递归过程如下：
（1）后序遍历左子树
（2）后序遍历右子树
（3）访问根结点
- void PostOrder(BitTree p)
- {
- if(p!=NULL)
- {
- PostOrder(p->lchild); //后序遍历左子树
- PostOrder(p->rchild); //后序遍历右子树
- printf("%c",p->data); //访问根结点
- }
- }
后序遍历的非递归算法比先序和中序的非递归算法复杂一些。按照后序遍历的过程，在遍历左子树之前，就要将根结点的地址保存在栈中，以便能在左子树遍历完成之后，从栈中弹出根结点地址，通过根结点走到右子树；但因为还没有遍历右子树，所以类似的，在遍历右子树之前，必须再次将根结点压入栈中，在遍历完右子树后，才能访问它。由于一个结点要进栈、出栈两次，就要对它是第一次进栈还是第二次进栈的情况加以区分。可以通过为结点增加标志位或与刚刚访问的结点相比较的方法，达到判断该结点是否应该访问的目的。
因此要引入一个标志栈flag[max]，对应结点的标志为0，表明左子树遍历，标志为1，表明右子树遍历。后序遍历二叉树的非递归算法步骤如下：
（1）当前指针指向根结点。
（2）当前指针不为空，进栈，所对应标志为0，当前指针指向其左孩子，重复直至左孩子为空。
（3）判断栈顶元素的标志，若为1，则依次退栈，输出结点，直至标志为0。
（4）若栈顶元素的标志为0，将当前指针指向栈顶元素的右孩子，并置标志为1，进栈；若当前指针为空，则退栈，输出结点，直至标志为0。
（5）若栈非空或当前指针非空，执行步骤（2），直至结束。
三、线索二叉树
二叉树的遍历实际上是对一个非线性结构进行线性化的操作，使结点按照某个次序进行排列。以二叉链表作为存储结构时，只能找到结点的左、右孩子信息，而不能直接得到该结点在任一遍历序列中的前驱和后继信息，这种信息只有在遍历的动态过程中才能得到。这对于经常需要进行查找结点前驱或后继的访问不方便。
根据二叉树的特性，n个结点的二叉树，采用链式存储结构时，有n+1个空链域，可以利用这些空链域存放指向结点的直接前驱和直接后继结点的指针。为此做如下规定：当结点的左指针为空（即无左子树）时，令该指针指向按某种方式遍历二叉树时该结点的前驱结点；当结点的右指针为空（即无右子树）时，令该指针指向按某种方式遍历二叉树时该结点的后继结点。为了避免概念混淆，可定义这种指向结点的前驱或后继的指针信息为线索。
- typedef struct BiThrNode
- {
- ElemType data;
- struct BiThrNode *lchild,*rchild; //左右指针
- int ltag,rtag; //左右指针类型标志，0表示指针，1表示线索
- }*BiThrTree;
为了方便起见，依照线性表的存储结构，在二叉树的线索链表上也添加一个头结点，并令其lchild域的指针指向二叉树的根结点，其rchild域指针指向某种次序遍历时访问的最后一个结点；反之，令二叉树中序序列中第一个结点的lchild域指针和最后一个结点rchild域的指针均指向头结点。这样二叉树建立了一个双向线索链表。
在线索二叉树上进行遍历，只要先找到序列中的第一个结点，然后依次找结点后继直至其后继为空时为止。例如，在中序线索二叉树中寻找某个结点的后继结点有以下两种情况：
（1）若结点的右标志位1，则其右指针指向的结点就是后继。
（2）若结点的右标志位0，则其右指针指向右子树，根据中序遍历的定义，沿着右子树寻找最左的结点，即顺着右子树的左指针向下，直到左标志为1的结点，就是其后继结点。
由此可以给出中序线索二叉树的遍历算法。
- void InOrderTraverse_Thr(BiThrTree root)
- {
- p=root->lchild; //p指向二叉树的根结点
- while(p!=root) //若不为空树
- {
- while(p->ltag==0)
- p=p->lchild;
- printf("%c",p->data); //访问其左子树为空的结点
- while(p->rtag==1&&p->rchild!=root) //访问右线索所指后继结点
- {
- p=p->rchild;
- printf("c",p->data);
- }
- p=p->rchild; //进入右子树
- }
- }
对于先序线索二叉树和中序线索二叉树，可以不用栈来实现二叉树的遍历，而对于后序线索二叉树，在进行后续遍历时仍需要栈。可分为三种情况：
（1）若结点x是二叉树的根，则后继为空。
（2）若结点x是双亲的右孩子或是其双亲的左孩子且其双亲没有右子树，则其后继结点为双亲结点。
（3）若结点x是其双亲的左孩子，且其双亲有右子树，则其后继为双亲的右子树上按后序遍历列出的第一个结点。
四、哈夫曼树
1. 哈夫曼树的概念
哈夫曼树，是指权值为w1,w2……,wn的n个叶节点所构成的二叉树中带权路径长度最小的二叉树。从树中的一个结点到另一个结点之间的分支构成这两个结点之间的路径，路径上的分支数目称做路径长度。树的路径长度是从树根到每一个结点的路径长度之和。完全二叉树是这种路径长度最短的二叉树。
在许多的应用中，常常将树中的结点赋予一个有着某种意义的实数，称此实数为该结点的权。从根结点到该结点之间的路径长度与该结点上权的乘积称为结点的带权路径长度。树中所有叶子结点的带权路径长度之和称为该树的带权路径长度，通常记作：WPL。
2. 哈夫曼树的构造
（1）根据给定的n个权值(w1,w2,…,wn)，对应结点构成n棵二叉树的森林T=(T1,T2,…,Tn)，其中每棵二叉树Ti(1<=i<=n)中都只有一个带权值为wi的根结点，其左右子树均为空。
（2）在森林T中选取两棵结点的权值最小的树作为左右子树构造一棵新的二叉树，一般结点按左小右大排列，且置新的二叉树的根结点的权值为其左右子树上根的权值之和。
（3）在森林T中，用新得到的二叉树代替这两棵树。
（4）重复步骤（2）和步骤（3），直到T只含有一棵树为止。这棵树就是哈夫曼树。
哈夫曼树在构造过程中需要存储结点的权值，同时对于每个结点还需要知道其双亲及孩子结点。因此哈夫曼树的结点结构与一般二叉树不同。若采用顺序存储方式，哈夫曼树的结点结构定义如下：
- typedef struct{
- char data;
- int weight;
- int parent;
- int lchild;
- int rchild;
- }HNodeType;
根据上述结点存储定义，假设结点信息已存储在一个数组中。哈夫曼树的构造算法基本步骤如下：
（1）哈夫曼树结点初始化。每个结点都是一棵独立的二叉树，parent、lchild、rchild均初始化为-1。
（2）依次选择两个权值最小且无双亲的结点，合并为一棵子树，直到建树完成。
具体算法如下：
- void HuffmanTree(HNodeType HuffNode[],int n){
- int i,j,m1,m2,x1,x2;
- for(i=0;i<2*n-1;i++){
- HuffNode[i].parent=-1;
- HuffNode[i].lchild=-1;
- HuffNode[i].rchild=-1;
- }
- for(i=0;i<n-1;i++){
- m1=m2=MAXVALUE;
- x1=x2=0;
- for(j=0;j<n+1;j++){
- if(HuffNode[j].weight<m1 && HuffNode[j].parent==-1){
- m2=m1;
- x2=x1;
- m1=HuffNode[j].weight;
- x1=j;
- }else if(HuffNode[j].weight<m2 && HuffNode[j].parent==-1){
- m2=HuffNode[j].weight;
- x2=j;
- }
- }
- HuffNode[x1].parent=n+i;
- HuffNode[x2].parent=n+i;
- HuffNode[n+i].weight=HuffNode[x1].weight+HuffNode[x2].weight;
- HuffNode[n+i].lchild=x1;
- HuffNode[n+i].rchild=x2;
- }
- }
五、哈夫曼编码
1. 哈夫曼编码的概念
在电报业务和数字通信中，可以用0和1组成的编码表示一个字母或其他字符，用编码序列表示字符序列以进行远距离传送。长途通信的代价是比较高的，希望用尽可能短的编码序列长度来传递给定的信息量，以提高通信的效率和降低传输的成本。
如果根据字符出现的次数为每个字符设计长度不等的编码，使用频率高的字符采用尽可能短的编码，则传送电文的总长便可减少。但是长短不同的编码也会给翻译带来不便，产生歧义。因此，若要设计长短不等的编码，则必须是任一个字符编码都不是另一个字符编码的前缀，这种编码称作前缀编码。
若需要编码的字符为C1、C2，……，Cn，它们在电文中出现的频率分别为W1、W2，……，Wn，以字符作为叶子结点构造一棵哈夫曼树。规定哈夫曼树中每个分支结点的左分支表示0，右分支表示1，将从根结点到每个叶子结点所经过路径上的0和1连接起来，作为叶结点所代表字符的编码。这样得到的编码称为哈夫曼编码。在哈夫曼编码中，每个字符的编码长度就等于根结点到字符所在叶子结点的路径长度。由哈夫曼树的定义可知，哈夫曼树是带权路径长度最小的二叉树，树的路径长度就是每个字符的编码长度与其出现频率的乘积之和，因此利用哈夫曼树构造的编码总长度最短。由于从根到叶结点只有一条唯一的路径，且不经过其他叶子结点，因此哈夫曼编码是一种不等长的前缀编码。
2. 哈夫曼编码的实现
哈夫曼编码过程由于是从叶子向上追溯到根，编码过程记录下的是每一个字符逆序的编码，因此除了存储从叶子到根经过的编码外，还需记录编码的起始位置start。每个字符的哈夫曼编码的存储结构定义如下：
- typedef struct{
- int bit[MAXBIT];
- int start;
- }HCodeType;
生成哈夫曼编码的过程如下：
（1）由叶子结点出发，向上直到树根，向上的过程中，结点若为其双亲的左孩子，则编码为0；否则编码为1，由于是从叶子向上追溯到根，所以编码也是从后向前，记住编码的起始位置start。
（2）直到所有叶子结点均编码结束为止。
- void HuffmanCode(HNodeType HuffNode[],HCodeType HuffCode[],int n){
- HCodeType cd;
- int i,j,c,p;
- for(i=0;i<n;i++){
- cd.start=n-1;
- c=i;
- p=HuffNode[c].parent;
- while(p!=1){
- if(HuffNode[p].lchild==c)
- cd.bit[cd.start]=0;
- else
- cd.bit[cd.start]=1;
- cd.start--;
- c=p;
- p=HuffNode[c].parent;
- }
- for(j=cd.start+1;j<n;j++){
- HuffCode[i].bit[j]=cd.bit[j];
- }
- HuffCode[i].start=cd.start;
- }
- }
六、树和森林
树是一种非线性结构，为了存储一棵树，必须把树中各结点之间一对多的关系反映在存储结构中。由于一个m阶的普通树中，每一个结点的孩子可以是0~m个，所以相对于二叉树而言，树的存储结构要复杂，一般有如下几种存储结构。
1. 树的存储结构
1.1 双亲表示法
双亲表示法是以一组连续空间存储树的结点，同时在每个结点中附设一个标志指示其双亲结点在表中的位置，该存储结构定义如下：
- #define MAX_TREE_SIZE 100
- typedef struct PTNode //树的结点定义
- {
- TElemType data;
- int parent; //指向结点的双亲
- }PTNode;
- typedef struct PTree //树的定义
- {
- PTNode node[MAX_TREE_SIZE];
- int r,n; //根的位置和结点数
- }PTree;
根结点R的parent域为-1，这种存储结构利用了每个结点（除根以外）只有唯一双亲的性质。在这种结构中，查找某个结点的双亲非常方便，但是求结点的孩子时需要遍历整棵树。
1.2 孩子表示法
由于树中每个结点可能有多棵子树，因此可以采用多重链表来表示，即每个结点有多个指针域，分别指向其孩子结点。
树的孩子表示法需要按照树的度m为每个结点分配指针域，而每个结点的孩子个数可能不同，当m很大时，指针域的存储单元利用率很低。如果按每个结点的实际孩子数来分配指针单元，结点的大小可变，会给存储管理带来不便。一个较好的解决办法就是为每个结点建立一个孩子链表。n个结点的树由n个这样的单链表组成，每个链表的表头结点存放该结点的值和指向其孩子的头指针。
- typedef struct CTNode
- {
- int child;
- struct CTNode *next;
- }*ChildPtr;
- typedef struct
- {
- TElemType data;
- ChildPtr firstchild; //孩子链表头指针
- }CTBox;
- typedef struct
- {
- CTBox nodes[MAX_TREE_SIZE];
- int n,r; //结点数和根结点的位置
- }
1.3 孩子兄弟表示法
孩子兄弟表示法又称树的二叉链表表示法。树中的每个结点由三个域组成：data域存储结点的数据信息，firstchild域为指向结点的第一个孩子的指针，nextbrother域为指向下一个兄弟的指针。每个结点的左指针指向孩子结点，而右指针指向兄弟结点，并且根结点的右指针为空。树的孩子兄弟表示法为实现树、森林、二叉树之间的转换提供了基础。
- typedef struct CSNode
- {
- ElemType data;
- struct CSNode *firstchild,*nextsibling;
- }CSNode,*CSTree;
2. 树、森林与二叉树的转换
二叉树的二叉链表表示法和树的孩子兄弟表示法都是以二叉链表作为存储结构，结点的定义相同，只是解释不同。因此，可以找到树和二叉树之间的对应关系，即给定一棵树，可以找到唯一的一棵二叉树与之对应。
森林是树的有限集合，可以将森林看成一棵树，其中所有树的根结点彼此看成兄弟结点。这样也可以导出森林和二叉树的对应关系。
2.1 森林转换成二叉树
若F={T1,T2,……,Tm}是森林(m>=0)，则可按如下规则转换成一棵二叉树B=(root,LB,RB)。
（1）若m=0，则B为空树。
（2）若m>0，则B的根root即为森林F中第一棵树的根ROOT(T1)；B的左子树LB是从森林的第一棵树T1中根结点的子树森林F1={T11,T12,……,T1m1}转换而成的二叉树；B的右子树RB是从森林F中除T1外的剩余部分F'={T2,T3,……,Tm}转换而成的二叉树。
具体操作步骤如下：
① 先将森林中的每一棵树转换为二叉树。
② 按森林中的次序，依次将后一棵树作为前一棵树的右子树，并将第一棵树的根作为目标二叉树的根。
2.2 二叉树转换为森林
如果B=(root,LB,RB)是一棵二叉树，则可按如下规则转换成森林F：
（1）若B为空，则F为空。
（2）若非空，则F中第一棵树T1的根ROOT(T1)即为二叉树B的根root；T中根结点的子树森林F1是由B的左子树LB转换而成的森林；F中除T1之外其余树组成的森林F'={T2,T3……,Tm}是由B的右子树RB转换而成的森林。
具体步骤如下：
① 若二叉树非空，则二叉树根及其左子树为第一棵树的二叉树形式。
② 二叉树根的右子树又可看作是剩余二叉树构成的森林，再继续分离出一棵树，直至产生一棵没有右子树的二叉树为止。
3. 森林的遍历
3.1 树的遍历
树的遍历主要有先根遍历、后根遍历和层次遍历三种。
（1）先根遍历。若树非空，则：
① 访问根结点。
② 依次先根遍历根的各个子树。
（2）后根遍历。若树非空，则：
① 依次后根遍历根的各个子树。
② 访问根结点。
（3）层次遍历。若树非空，则：
① 访问根结点。
② 按从左至右的次序依次访问各层结点。
对树的先根遍历与其对应的二叉树的先根遍历序列一致；对树的后根遍历与其对应的二叉树的中序遍历序列一致。
3.2 森林的遍历
按照森林和树相互递归的定义，可以推出森林的两种遍历方法。
（1）森林的先根次序遍历。
① 访问第一棵树的根结点。
② 先根次序遍历第一棵树的子树森林。
③ 先根次序遍历除第一棵树以外的其余的子树。
先根次序遍历森林同它所对应的二叉树的先序遍历次序一致。
（2）森林的后根次序遍历。
① 后根次序遍历第一棵树的子树森林。
② 访问第一棵树的根结点。
③ 后根次序遍历除第一棵树以外的其余的子树。
后根次序遍历森林同它所对应的二叉树的中序遍历次序一致。
由此可见，当以二叉链表为树的存储结构时，森林的先根遍历和后根遍历可借用二叉树的先序遍历和中序遍历的算法实现。
附：系列文章
-
相关阅读:
三个案例带你入门Thymeleaf。模板引擎，终于不用在后端拼接前端代码了。
PCB沉金包边工艺流程与主要作用经验总结
这3种职场话语，值得我们慎重思考
观察者模式(大话设计模式)C/C++版本
（二）springboot整合redis，基于注解快速实现缓存功能
Kubernetes带你从头到尾捋一遍
Java注解相关
一、基本数据类型（数组）
【2023美团后端-8】删除字符串的方案,限制不能连续删
【前端面试考点】
- 原文地址：https://blog.csdn.net/m0_68111267/article/details/127454209