第六章 树和二叉树

第六章树和二叉树1第一页，共七十五页，编辑于2023年，星期四第六章树和二叉树6.1树的有关概念6.2二叉树6.3二叉树的遍历6.4遍历的应用6.5线索二叉树6.6树和森林6.7哈夫曼树及应用2第二页，共七十五页，编辑于2023年，星期四6.1

树的有关概念1.树的概念2.树的应用3.树的表示树的有关术语5树的基本操作3第三页，共七十五页，编辑于2023年，星期四1．树的概念

树是n个结点的有限集合，在任一棵非空树中：

（1）有且仅有一个称为根的结点。

（2）其余结点可分为个互不相交的集合，而且这些集合中的每一集合都本身又是一棵树，称为根的子树。树是递归结构，在树的定义中又用到了树的概念JIACBDHGFE4第四页，共七十五页，编辑于2023年，星期四从逻辑结构看：

1）树中只有根结点没有前趋；

2）除根外，其余结点都有且仅一个前趋；3）树的结点，可以有零个或多个后继；

4）除根外的其他结点，都存在唯一条从根到该结点的路径；5）树是一种分枝结构（除了一个称为根的结点外）每个元素都有且仅有一个直接前趋，有且仅有零个或多个直接后继。JIACBDHGFE1．树的概念

5第五页，共七十五页，编辑于2023年，星期四树的基本术语树的结点：包含一个数据元素及若干指向子树的分支；

孩子结点：结点的子树的根称为该结点的孩子；

双亲结点：B结点是A结点的孩子，则A结点是B结点的双亲；

兄弟结点：同一双亲的孩子结点；

堂兄结点：同一层上结点；

结点层：根结点的层定义为1；根的孩子为第二层结点，依此类推；

树的高度：树中最大的结点层

结点的度：结点子树的个数

树的度：树中最大的结点度。

叶子结点：也叫终端结点，是度为0的结点；

分枝结点：度不为0的结点；

森林；互不相交的树集合；

有序树：子树有序的树，如：家族树；

无序树：不考虑子树的顺序；6第六页，共七十五页，编辑于2023年，星期四5树的基本操作树的应用很广，应用不同基本操作也不同。下面列举了树的一些基本操作：

（以DOS元文件系统为例解释树的基本操作）

1）InitTree(&T);2）DestroyTree(&T);3）CreateTree(&T,definition);4）ClearTree(&T);5）TreeEmpty(T);6）TreeDepth(T);7）Root(T);8）Value(T,&cur_e);9）Assign(T,cur_e,value);10）Paret(T,cur_e);11）LeftChild(T,cur_e);12）RightSibling(T,cur_e);13）InsertChild(&T,&p,i,c);14）DeleteChild(&T,&p,i);15）TraverseTree(T,Visit());7第七页，共七十五页，编辑于2023年，星期四6.2二叉树一二叉树的概念二二叉树的性质三二叉树的存储结构8第八页，共七十五页，编辑于2023年，星期四一二叉树的概念1二叉树的定义二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树。说明1）二叉树中每个结点最多有两颗子树；二叉树每个结点度小于等于2;2）左、右子树不能颠例——有序树;3）二叉树是递归结构，在二叉树的定义中又用到了二叉树的概念;

A

F

G

E

D

C

B9第九页，共七十五页，编辑于2023年，星期四

A

F

G

E

D

C

B

(a)、(b)是不同的二叉树，(a)的左子树有四个结点，(b)的左子树有两个结点，(a)

A

G

E

D

B

C

F(b)10第十页，共七十五页，编辑于2023年，星期四

2．二叉树的基本形态

φ11第十一页，共七十五页，编辑于2023年，星期四3．应用举例例1可以用二叉树表示表达式

e

d

c

b

f

a

+

*

/

-

-

abcd-*+ef/--表达式的后缀表示

a+b*c–d–e/f-表达式的中缀表示

-+a*b–cd/ef-表达式的前缀表示

12第十二页，共七十五页，编辑于2023年，星期四3．应用举例例1可以用二叉树表示表达式

e

d

c

b

f

a

+

*

/

-

-

abcd-*+ef/--表达式的后缀表示

a+b*c–d–e/f-表达式的中缀表示

-+a*b–cd/ef-表达式的前缀表示

13第十三页，共七十五页，编辑于2023年，星期四下面是两个关于二叉树的性质性质1：在二叉树的第i层上至多有2i-1个结点（i>=1)

利用归纳法证明性质2：深度为k的二叉树至多有2k-1个结点（k>=1)

第比数列求和性质3：对任何一棵二叉树T,如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+114第十四页，共七十五页，编辑于2023年，星期四两种特殊的二叉树满二叉树：如果深度为k的二叉树，有2k-1个结点则称为满二叉树；

A

G

F

E

D

C

B

A

C

BK=3的满二叉树K=2的满二叉树15第十五页，共七十五页，编辑于2023年，星期四完全二叉树：如果一颗二叉树只有最下一层结点数可能未达到最大，并且最下层结点都集中在该层的最左端，则称为完全二叉树；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉树(c)不是完全二叉树

A

G

F

E

D

C

B16第十六页，共七十五页，编辑于2023年，星期四下面是两个关于完全二叉树的性质性质4具有n个结点的完全二叉树的深度为：log2n+1对完全二叉树的结点编号：从上到下，每一层从左到右

A

F

E

D

C

B123456性质5：在完全二叉树中编号为i的结点，1）若有左孩子，则左孩编号为2i；2）若有右孩子，则有孩子结点编号为2i+1；3）若有双亲，则双亲结点编号为i/2；17第十七页，共七十五页，编辑于2023年，星期四三．二叉树存贮结构

1二叉树的顺序结构完全二叉树的顺序结构用一组连续的内存单元，按编号顺序依次存储完全二叉树的元素

顺序结构图示

1234567m-1

ABCDEF

A

F

E

D

C

B12345618第十八页，共七十五页，编辑于2023年，星期四二叉树的顺序结构假想，我们补齐二叉树所缺少的那些结点，对二叉树结点编号

A

F

G

E

D

C

B7162453

A

F

G

E

D

C

B981019第十九页，共七十五页，编辑于2023年，星期四123456789m-1

AB

C

DE

F

G二叉树的顺序结构图示将二叉树原有的结点按编号存储到内存单元“相应”的位置上162453

A

F

G

E

D

C

B981020第二十页，共七十五页，编辑于2023年，星期四2二叉链表二叉链表中每个结点包含三个域：数据域、左指针域、右指针域∧

D

A

B

∧C

∧∧

E

∧∧

F

∧

A

F

E

D

C

B3三叉链表三叉链表中每个结点包含四个域：数据域、双亲指针域、左指针域、右指针域二叉链表图示21第二十一页，共七十五页，编辑于2023年，星期四4

静态链表上面二叉链表或三叉链表是用指针实现，是一种动态的链式存储结构，链式存储结构也可用一维数组来实现，用一维数组表示的二叉链表或三叉链表，称为静态链表

A

F

E

D

C

B孩子结点在数组中的位置-1表示无左或右孩子静态二叉链表A13C-15B-1-1E-1-1F-1-1D4

0123456Lchilddatarchild22第二十二页，共七十五页，编辑于2023年，星期四6.3二叉树的遍历一.二叉树的遍历方法二.遍历的递归算法23第二十三页，共七十五页，编辑于2023年，星期四遍历：按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问一次。访问：含义很广，可以是对结点的各种处理，如修改结点数据、输出结点数据。遍历是各种数据结构最基本的操作，许多其他的操作可以在遍历基础上实现。

如何访问二叉树的每个结点，而且每个结点仅被访问一次？？24第二十四页，共七十五页，编辑于2023年，星期四二叉树的遍历方法二叉树由根、左子树、右子树三部分组成二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树令：L：遍历左子树

D：访问根结点

R：遍历右子树

有六种遍历方法：

DLR，LDR，LRD，

DRL，RDL，RLD

约定先左后右,有三种遍历方法：DLR、LDR、LRD，分别称为

先序遍历、中序遍历、后序遍历

A

F

G

E

D

C

B25第二十五页，共七十五页，编辑于2023年，星期四先序遍历（DLR）若二叉树非空

（1）访问根结点；（2）先序遍历左子树；

（3）先序遍历右子树；

先序遍历序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍历右图所示的二叉树（1）访问根结点A

（2）先序遍历左子树：即按DLR的顺序遍历左子树（3）先序遍历右子树：即按DLR的顺序遍历右子树26第二十六页，共七十五页，编辑于2023年，星期四中序遍历（LDR）若二叉树非空

（1）中序遍历左子树

（2）访问根结点（3）中序遍历右子树

中序遍历序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍历右图所示的二叉树（1）中序遍历左子树：即按LDR的顺序遍历左子树

（2）访问根结点A（3）中序遍历右子树：即按LDR的顺序遍历右子树27第二十七页，共七十五页，编辑于2023年，星期四后序遍历（LRD）若二叉树非空

（1）后序遍历左子树

（2）后序遍历右子树（3）访问根结点

后序遍历序列：D,G,E,B,F,C,A例：后序遍历右图所示的二叉树（1）后序遍历左子树：即按LRD的顺序遍历左子树

（2）后序遍历右子树：即按LRD的顺序遍历右子树（3）访问根结点A

A

F

G

E

D

C

B28第二十八页，共七十五页，编辑于2023年，星期四

e

d

c

b

f

a

+

*

/

-

-

后序遍历序列：abcd-*+ef/-

中序遍历序列：a+b*c–d–

e/f

先序遍历序列：-+a*b–cd/ef例：先序遍历、中序遍历、后序遍历下图所示的二叉树29第二十九页，共七十五页，编辑于2023年，星期四按层遍历:从根出发,依次访问第一层、第二层…结点

A

F

G

E

D

C

B按层遍历序列:ABCDEFG30第三十页，共七十五页，编辑于2023年，星期四若二叉树非空（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；二.遍历的递归算法先序遍历（DLR）的定义：上面先序遍历的定义等价于：若二叉树为空，结束——基本项（也叫终止项）若二叉树非空——递归项（1）访问根结点；（2）先序遍历左子树（3）先序遍历右子树；31第三十一页，共七十五页，编辑于2023年，星期四先序遍历递归算法

voidPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//本算法先序遍历以T为根结点指针的二叉树

if(T){//若二叉树不为空，

Visit(T->data)；//访问根结点

PreOrderTraverse(T->lchild,Visit);//先序遍历T的左子树，

PreOrderTraverse(T->rchild,Visit);//先序遍历T的右子树

}//PreOrderTraverse最简单的Visit函数是：

StatusPrintElement(TElemTypee){//输出元素e的值

printf(e);

returnOK;}

∧

D

A

B∧C

∧∧

E∧∧

F∧T32第三十二页，共七十五页，编辑于2023年，星期四2中序遍历递归算法

voidInOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。

//本算法中序遍历以T,为根结点指针的二叉树

if(T){////若二叉树不为空，访问根结点，遍历右子树

InOrderTraverse(T->lchild,Visit);//中序遍历T的左子树

Visit(T->data)；//访问根结点

InOrderTraverse(T->rchild,Visit);//中序遍历T的右子树

}//InOrderTraverse

33第三十三页，共七十五页，编辑于2023年，星期四3后序遍历递归算法

voidPostOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。//本算法后序遍历以T为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树不为空，

PostOrderTraverse(T->lchild,Visit);//后序遍历T的左子树

PostOrderTraverse(T->rchild,Visit);//后序遍历T的右子树，

Visit(T->data)；//访问根结点

}//PostOrderTraverse

34第三十四页，共七十五页，编辑于2023年，星期四遍历的非递归算法中序遍历的非递归算法(使用栈实现非递归中序遍历)StatusInOrderTraverse(BiTreeT,Status(*Visit)(TelemTypee)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。//中序遍历二叉树T的非递归算法，对每个数据元素调用函数Visit。InitStack(S);p=T;While(p||!StackEmpty(s)){if(p){Push(s,p);p=p->lchild;}//根指针进栈，遍历右子树else{//根指针退栈，访问根结点，遍历右子树

Pop(S,p);Visit(p->data);p=p->rchild;}//else}//WhilereturnOK;}//InOrderTraverse35第三十五页，共七十五页，编辑于2023年，星期四按层遍历算法与图的广度优先遍历类似,利用队列实现树的按层遍历StatusLevelTraverse(BiTreeT,Status(*Visit)(TelemTypee)){//采用二叉链表存储结构，Visit是对数据元素操作的应用函数。使用辅助队列Q,按层遍历二叉树T。

InitQueue(Q);//建空的辅助队列Qp=T;Visit(p->data)，EnQueue(Q,p)//访问p所指结点,p入队

While(!QueueEmpty(Q)){DeQueue(Q,p);//队头元素出队,并赋值给p

p=p->lchild,Visit(p->data);EnQueue(Q,p);p=p->rchild,Visit(p->data);EnQueue(Q,p);}//while}//LevelTraverse36第三十六页，共七十五页，编辑于2023年，星期四6.4遍历的应用

1.求二叉树的叶子结点个数2.建立二叉链表

37第三十七页，共七十五页，编辑于2023年，星期四例1编写求二叉树的叶子结点个数的算法

输入：二叉树的二叉链表

结果：二叉树的叶子结点个数∧

D

A

B

∧C

∧∧

E

∧∧F

∧Tvoidleaf(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点的个数。本算法在先序遍历二叉树的过程中，统计叶子结点的个数//第一次被调用时，n=0if(T){

if(T->lchild==null&&T->rchild==null)n=n+1;//若T所指结点为叶子，则累加。

leaf(T->lchild);leaf(T->rchild);}//if}//leaf与先序遍历算法比较一下！38第三十八页，共七十五页，编辑于2023年，星期四voidleaf(BiTreeT){//采用二叉链表存贮二叉树，n为全局变量，用于累加二叉树的叶子结点,的个数。//本算法在先序遍历二叉树的过程中，统计叶子结点的个数第一次被调用时，n=0if(T){//若二叉树为空，结束返回

//若二叉树不为空，在先序遍历二叉树的过程中，统计叶子结点的个数

if(T->lchild==null&&T->rchild==null)n=n+1;leaf(T->lchild);leaf(T->rchild);}//if}//leaf

viodPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){

//采用二叉链表存贮二叉树，visit()是访问结点的函数。本算法先序//遍历以为根结点指针的二叉树，对每个数据元素调用函数Visit()

if(T){//若二叉树为空，返回

//若二叉树不为空，访问根结点；遍历左子树，遍历右子树

Visit(T->data)；

PreOrderTraverse(T->lchild,Visit);

PreOrderTraverse(T->rchild,Visit);

}//PreOrderTraverse比较先序遍历算法和计算叶子结点算法，有什么相同和不同？结构类似函数名不同访问结点时调用visit()访问结点时统计叶子结点的个数39第三十九页，共七十五页，编辑于2023年，星期四例2建立二叉链表

输入：二叉树的先序序列

结果：二叉树的二叉链表

遍历操作访问二叉树的每个结点，而且每个结点仅被访问一次。是否可在利用遍历，建立二叉链表的所有结点并完成相应结点的链接？基本思想：输入（在空子树处添加字符*的二叉树的）先序序列（设每个元素是一个字符）按先序遍历的顺序，建立二叉链表的所有结点并完成相应结点的链接

A

F

E

D

C

B*******ABD*F**CE***40第四十页，共七十五页，编辑于2023年，星期四StatusCreateBiTree(BiTree&T){//输入（在空子树处添加字符*的二叉树的）先序序列（设每个元素是//一个字符）按先序遍历的顺序，建立二叉链表，并将该二叉链表根结//点指针赋给Tscanf(&ch);if(ch==‘*’)T=NULL;//若ch==‘*’则T=NULL返回

else{//若ch!=‘*’if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->date=ch;//建立（根）结点

CreateBiTree(T->lchild);//构造左子树链表，并将左子树根结点指针//赋给（根）结点的左孩子域

CreateBiTree(T->rchild);//构造右子树链表，并将右子树根结点指针//赋给（根）结点的右孩子域}

returnOK;}//CreateBiTree41第四十一页，共七十五页，编辑于2023年，星期四∧

D

A

B∧C

∧∧E∧∧F∧T先序序列：ABDFCE（在空子树处添加*的二叉树的）先序序列：

ABD*F**CE***

A

F

E

D

C

B*******

A

F

E

D

C

B42第四十二页，共七十五页，编辑于2023年，星期四掌握利用先序和中序，中序和后序来建立一个二叉树

已知一个二叉树的先序和中序，怎样建立二叉树？先序：-+a*b–cd/ef

中序：a+b*c–d–

e/f

已知一个二叉树的后序和中序，怎样建立二叉树？中序：a+b*c–d–

e/f

后序：abcd-*+ef/-43第四十三页，共七十五页，编辑于2023年，星期四小结

小结1二叉树：或为空树，或由根及两颗不相交的左子树、右子树构成，并且左、右子树本身也是二叉树；2二叉树即可以用顺序结构存储，也可用链式结构存储；3遍历：按某种搜索路径访问二叉树的每个结点，每个结点仅被访问一次。二叉树的遍历可以分解为：访问根，遍历左子树和遍历右子树，本课程介绍了三种遍历算法：先序遍历、中序遍历、后序遍历；44第四十四页，共七十五页，编辑于2023年，星期四HW:6.16.3(不用交）6.146.276.285月16号交作业45第四十五页，共七十五页，编辑于2023年，星期四6.4线索二叉树1.线索二叉树和线索链表2.二叉树的线索化3.线索二叉树的遍历46第四十六页，共七十五页，编辑于2023年，星期四1线索二叉树和线索链表

加上结点前趋后继信息（线索）的二叉树称为线索二叉树

A

G

H

E

D

C

B

F以中序遍历为例，通过遍历可以得到二叉树结点的中序序列。中序遍历序列：D,B,H,E,A,F,C,G在中序序列中，D的后继是B，H的前趋是B，后继是E…47第四十七页，共七十五页，编辑于2023年，星期四线索链表

线索二叉树的存贮方法：T∧

D∧

A

B

C

∧

F

∧∧

H∧

E∧∧

G

∧

A

G

H

E

D

C

B

F2)每个n个结点的二叉链表，有n+1个空指针域。可利用这些的空指针域存放结点的前趋和后继指针。这种二叉链表称为线索链表1）

为每个结点增加二个指针域48第四十八页，共七十五页，编辑于2023年，星期四线索二叉树

A

G

H

E

D

C

B

F孩子指针前趋指针后继指针线索链表头结点F11E01G11D11A00B00H11C000149第四十九页，共七十五页，编辑于2023年，星期四2.二叉树的线索化StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT)A00B00C00D00∧∧H00∧∧E00∧G00∧∧F00∧∧在二叉树加线索F11E01G11D11A00B00H11C0001头结点50第五十页，共七十五页，编辑于2023年，星期四二叉树的二叉线索存储表示

typedefenum{Link,Thread}PointerTag;//Link==0指针Thread==1线索

typedefstructBiThrNode{TElemTypedata;StructBiThrNode*lchild,*right;PointerTagLTag,RTag;}BiThrNode,*BiThrTree;51第五十一页，共七十五页，编辑于2023年，星期四StatusInOrderThreading(BiThrTree&Thrt,BiThrTreeT){//中序遍历二叉树T，并将其中序线索化，Thrt指向头结点。if(Thrt=(BiThrTree)malloc(sizeof)(BiThrNode)))exit(OVERFLOW);Thrt->Ltag=Link;Thrt->Rtag=Thread;//建头结点Thrt->rchild=Thrt;//右指针回指if(!T)Thrt->lchild=Thrt;//若二叉树空，则左指针回指else{Thrt->lchild=T;//若二叉树非空，则左指针指向根结点

pre=Thrt;//头结点看作是中序序列第一个结点的前趋

InThreading(T);//中序遍历进行中序线索化

Pre->rchild=Thrt;pre->Rtag=Thread;//最后一个结点线索化

Thrt->rchild=pre;}returnOK;}//InOrderThreading52第五十二页，共七十五页，编辑于2023年，星期四voidInThreading(BiThrTreep){if(p){InThreading(p->lchild);//左子树线索化if(!p->lchild){p->Ltag=Thread;p->lchild=pre;}//为当前结点加上前趋线索if(!p->rchild){pre->Rtag=Thread;pre->rchild=p;}//为当前结点的前趋加上后继线索pre=p;//保持pre指向p的前趋InThreading(p->rchild);//右子树线索化}//if}//InThreading53第五十三页，共七十五页，编辑于2023年，星期四基本思想：1）若p所指结点的右孩子域为线索，则p的右孩子结点即为后继结点；2）若p所指结点的右孩子域为孩子指针，则p的后继结点为其右子树的最左下结点；中序遍历序列：D,B,H,E,A,F,C,G3．线索二叉树的遍历F11E01G11D11A00B00H11C0001头结点①②③54第五十四页，共七十五页，编辑于2023年，星期四线索链表的遍历算法VoidInOrderTraverse_Thr(BiThrTreeT,Status(*Visit)(TE1emTypee)){

//T指向头结点，头结点的左链lchild指向根结点，//中序遍历二叉线索树T算法，对每个数据元素调用函数Visit。

P=T->lchild;//p指向根结点

While(p!=T){//空树或遍历结束时，p==TWhile(p->Ltag==Link)p=p->lchild;//找到最左下结点；访问之

Visit(p->data))while(p->Rtag==Thread&&p->rchild!=T){//若p所指结点的右孩子域为线索且不是最后一个结点

p=p->rchild;Visit(p->data);//访问后继结点}p=p->rchild;//若p所指结点的右孩子域不是线索

}returnOK;}//InOrderTraverse_Thr为了增加算法的可读性，这里对书上算法作了简化，没有考虑访问结点出错的情况（即我们假设调用函数visit()访问结点总是成功的。55第五十五页，共七十五页，编辑于2023年，星期四6.6树和森林一.树的存储结构二.树和二叉树的转换三.

树的遍历四.森林

56第五十六页，共七十五页，编辑于2023年，星期四

一．树的存贮结构1双亲表示法双亲表示法：通过保存每个结点的双亲结点的位置，表示树中结点之间的结构关系。

双亲表示类型定义#defineMAX_TREEE_SIZE100typedefstructPTNode{TelemTypedata;intparent;//双亲位置域}PTNode;typedefstruct{PTNodenodes[MAX_TREE_SIZE];intn;//结点数}Ptree;IACBDHGFEA-1B0C0D0E1F1G2H3I3012345678.dataparent9T.nodesT.n结点数双亲结点在数组中的位置-1表示无双亲57第五十七页，共七十五页，编辑于2023年，星期四2、孩子表示法孩子表示法：通过保存每个结点的孩子结点的位置，表示树中结点之间的结构关系。方法1

：多重链表（类似二叉链表）

两种方式：定长结点不定长结点定长结点

优点结点结构一致，便于实现树的操作。缺点是浪费一些内存。

不定长结点

优点：节省内存

缺点：不定长会使一些操作实现复杂一些58第五十八页，共七十五页，编辑于2023年，星期四A

B

C

D

E∧F∧G∧H∧I

012345678…99结点数和根的位置9013∧245∧8∧6∧7T.nodesT.nT.rdatafirstchild树的孩子链表图示结点的孩子结点链表IACBDHGFE方式II

孩子链表：对树的每个结点用线性链表存贮它的孩子结点59第五十九页，共七十五页，编辑于2023年，星期四树的孩子链表类型定义typedefstructCTNode{//孩子结点

intchild;structCTNode*next;}*ChildPtr;typedefstruct{TElemTypedata;ChildPtrfirstchild;//孩子链表头指针}CTBox;typedefstruct{CTBoxnodes[MAX_TREE_SIZE];intn,r;//结点数和根的位置；}CTree;A

B

C

D

E∧F∧G∧H∧I

012345678…999013∧245∧8∧6∧7T.nodesT.nT.rdatafirstchild60第六十页，共七十五页，编辑于2023年，星期四3孩子兄弟表示法孩子兄弟表示法用二叉链表作为树的存贮结构孩子兄弟表示法类型定义

typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;IACBDHGFEAIHDGFCEB树的孩子兄弟表示法图示B的第一个孩子结点B的右兄弟结点61第六十一页，共七十五页，编辑于2023年，星期四IACBDHGFE此二叉链表既是树(a)的孩子兄弟表示又是二叉树(b)的二叉链表(a)(b)由此可将树与二叉树对应起来AIHDGFCEBFIABDHGCE62第六十二页，共七十五页，编辑于2023年，星期四二树与二叉树的转换

二叉树与树都可用二叉链表存贮，以二叉链表作中介，可导出树与二叉树之间的转换。树与二叉树转换方法树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子63第六十三页，共七十五页，编辑于2023年，星期四树根结点X的第一个孩子结点X紧邻的右兄弟二叉树根结点X的左孩子结点X的右孩子IACBDHGFEFIABDHGCE64第六十四页，共七十五页，编辑于2023年，星期四三树的遍历

先根遍历先访问根，然后依次先根遍历每一颗子树。

例先根遍历序列

A

BEF

CG

DHI后根遍历依次后根遍历根的每一颗子树，然后访问根。

后根遍历序列EFB

GC

HIDA

树的先根遍历对应二叉树的先序遍历；树的后根遍历对应二叉树的中序遍历。不论是先根遍历还是后根遍历都是对树按深度方向的遍历，也可按宽度方向（按层）遍历树。IACBDHGFE65第六十五页，共七十五页，编辑于2023年，星期四四森林森林：树的集合

将森林中树的根看成兄弟，可用树孩子兄弟表示法存储森林；用树与二叉树的转换方法，进行森林与二叉树转换；可用树的遍历方法对森林进行遍历；

J