【文档说明】课件-算法与数据结构教学第5章二叉树与树C语言描述第2版.ppt，共(116)页，1.206 MB，由小橙橙上传

转载请保留链接：https://www.ichengzhen.cn/view-44679.html

以下为本文档部分文字说明：

5二叉树和树5.1二叉树及其抽象数据类型5.2二叉树的周游5.3二叉树的实现5.4二叉树的应用5.5树及其抽象数据类型5.6树的实现5.7树林线性结构和非线性结构。树形结构是以分支关系定义的层次结构，在现实世界中广泛存在，在计算机领

域中也有广泛应用。本章重点讨论二叉树的存储结构及其各种操作，并研究树和森林与二叉树之间的转换关系。5.1二叉树及其抽象数据类型➢5.1.1基本概念➢5.1.2主要性质➢5.1.3抽象数据类型二叉树：它是结点的有

限集合，这个集合或者为空集或者由一个根及两棵不相交的分别称作这个根的“左子树”和“右子树”的二叉树组成。它的每一个结点至多有两棵子树，并且子树有左右之分，不能随意颠倒。5.1.1基本概念二叉树的基本形态：左子树右子树右

子树左子树（1）空二叉树（2）只有一个根结点（3）有根结点和左子树（4）有根结点和右子树（5）有根结点和左，右子树➢父结点，左（右）子结点，边若结点x是二叉树中某一棵子树的根结点，结点y是x的左（右）子树的根，则称x是y的父结点；y是x的左（右）子结点；有序对<x，y>

称作从x到y的边。例如树t中，C是E的父结点，E是C的子结点，<C，E>是从C到E的边➢兄弟结点具有同一父结点彼此称作兄弟。树t中B，C互为兄弟，D，E互为兄弟。图5.2二叉树tABCDEF图5.2二叉树tABCDEF➢祖先，子孙若结点y在以结点x为

根的一个子树中，且y≠x，则称x是y的祖先，y是x的子孙。例如树t中，A是其它各结点的祖先；C是D,E,F的祖先。➢路径，路径长度如果x是y的一个祖先，又有x＝x0，x1，…，xn＝y，满足xi（i＝0，1，…，n-1）为xi+1的父结点，则称x0，x1，…，xn为从x到y的一条路径。n称

为这条路径的长度。例如树t中A，C，D，F是从A到F的一条路径，其长度为3。图5.2二叉树tABCDEF图5.2二叉树tABCDEF➢结点的层数规定根的层数为0，其余结点的层数等于其父母结点的层数加1。如t中，0层的结点是A，1层的结点有B，C，3层的结点是F。➢二叉树的

高度树中结点的最大层数称为二叉树的高度。例如树t中，树的深度为3。图5.2二叉树tABCDEF图5.2二叉树tABCDEF➢结点的度数结点的非空子树个数叫作结点的度数。例如t中A,B,C,D,E,F的度数分别为2,0,2,1,0,0➢树叶、分支结点左（右）子树均为空的结点称作树叶；否则称作分支结点

。例如树t中B，E，F都是树叶，其余结点都是分支结点。图5.2二叉树tABCDEF图5.2二叉树tABCDEF满二叉树：如果一棵二叉树的任何结点或者是树叶，或者有两棵非空子树，则此二叉树称作满二叉树。完全二叉树：如果一棵二叉树

只有最下面的两层结点度数可以小于2，并且最下面一层的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。完全二叉树不一定是满二叉树。满二叉树完全二叉树扩充二叉树：把原二叉树的结点都变为度数为2的分支结点，也就是说，如果原结点的度数为2，则不变，度数为1，则增加一个分支，度数为0（树叶）

增加两个分支。新增加的结点用小方框表示，称为外部结点,原来的结点称为内部结点。外部路径长度E：在扩充的二叉树里从根到每个外部结点的路径长度之和。内部路径长度I：在扩充的二叉树里从根到每个内部结点的路径长度之和。性质1.在非空二叉树的第i层上至多有2i个结点（i0）。归纳：i=0,

结点数=1=20.假设对于j(0ji),结点数至多有2j.对于i=j+1,结点数至多为2*2j=2j+1.性质2.深度为k的二叉树至多有2k+1-1个结点（k0）。KkM=mi=2i=2k+1-1i=0i=020+21+22+…+2k5

.1.2主要性质性质3.对任何一棵非空二叉树T，如果叶结点数为n0，度为2的结点数为n2，则n0=n2+1。n0+n1+n2=所有结点的度数和+1=n1+2*n2+1性质4.具有n个结点的完全二叉树的深度k为log2n.n=20+21+22+…

+2k-1+mk=2k-1+mk2k-1n2k+1-12kn2k+1klog2nk+1k=log2n性质5.对于具有n个结点的完全二叉树，如果按从上到下和从左到右的顺序对二叉树中的所有结点从0开始到n-1进行编号，则对任意的下标为i的结点，有：1）如果i=0，则它是根结点，它

没有父结点；如果i>0,则它的父结点的下标为(i-1)/2;2）2i+1n-1，则下标为i的结点的左子结点的下标为2i＋1；否则下标为i的结点无左子结点。3）2i+2n-1，则下标为i的结点的右子结点的下标为2i＋2；否则下标为i的结点无右子结点。性质6

在满二叉树中，叶子结点的个数比分支结点的个数多1。由于满二叉树中，分支结点度数全部为2；其他结点都是叶子结点。根据性质3，n0=n2+1，可以得到此性质。性质7在扩充二叉树中，外部结点的个数比内部结点的个数多1。由于扩充二叉树都是满二叉树，根据性

质6可以得到此性质。性质8对任意扩充二叉树，外部路径长度E和内部路径长度I之间满足以下关系：E=I+2n其中，n是内部结点的个数。证明：当n=1时，I=0,E=2,此等式成立。设有n个内部结点的扩充二叉树，下式成

立。En=In+2n(1)对于n+1个内部结点的扩充二叉树，去掉一个作为原来二叉树路径长度为K的内部结点，内部路径长度变为：In=In+1-K(2)外部路径长度变为：En=En+1-2(K+1)+K=En+1-K-2即：En+1=En+K+2En+1=(In+2n)+K+2=(In+

1-K)+2n+K+2=In+1+2(n+1)代入（1）代入（2）abceef5.1.3抽象数据类型ADTBinTreeisoperationsBinTreecreateEmptyBinTree(void)创建一棵空的二叉树BinTreeconsBinTree(BinTreeNode

root,BinTreeleft,BinTreeright)返回一棵二叉树，其根结点是root，左右二叉树分别为left和rightintisNULL(BinTreet)判断二叉树t是否为空。BinTreeNoderoot(BinTreet)返回二叉树t的根结点；若为空二叉树，

则返回一个特殊值。BinTreeNodeparent(BinTreet,BinTreeNodep)返回结点p的父结点；当p为根时，返回一个特殊值。BinTreeleftChild(BinTreet,BinTreeNodep)返回p结点的左子树，当p结点没有左子树

时，返回一个特殊值。BinTreerightChild(BinTreet,BinTreeNodep)返回p结点的y右子树，当p结点没有右子树时，返回一个特殊值。endADTBinTree5.2二叉树的周游5.2.1什么是周游二叉树的周游(TraversingBinaryTree)：按某

条搜索路径访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。DLR5.2.2周游的分类深度优先周游三种方式：先根次序(DLR)中根序(LDR)后根次序(LRD)DLR先根次序：若二叉树不空，则（1）访问根结点；（2）先根次序周游左子树；（3）先根

次序周游右子树。ABDCEFIHG访问A先根次序周游A的左子树先根次序周游A的右子树ABDCEFIHG访问A先根次序周游A的左子树•访问B•先根次序周游B的左子树（访问D）•先根次序周游B的右子树(空操作)先根次序周游A的右子树•访问C•先根次序周游C的左子树（访问E、G）•

先根次序周游C的右子树（访问F、H、I）先序序列：ABDCEGFHI中根(对称)次序：若二叉树不空，则（1）中根次序周游左子树；（2）访问根结点；（3）中根次序周游右子树。中根次序周游A的左子树访问A中根次序周

游A的右子树ABDCEFIHGABDCEFIHG中根次序周游A的左子树•中根次序周游B的左子树（访问D）•访问B•中根次序周游B的右子树(空操作)访问A中根次序周游A的右子树•中根次序周游C的左子树（访问E、G）•访问C•中根次序周游C的右子树（访问H、F、I）中序序列：DB

AEGCHFI后根次序：若二叉树不空，则（1）后根次序周游左子树；（2）后根次序周游右子树；（3）访问根结点。后根次序周游A的左子树后根次序周游A的右子树访问AABDCEFIHGABDCEFIHG后根次序周游A的左子树•后根次序周游B的左子树（访问D）•后根次序周游B的右子树(

空操作)•访问B后根次序周游A的右子树•后根次序周游C的左子树（访问G、E）•后根次序周游C的右子树（访问H、I、F）•访问C访问A后序序列：DBGEHIFCA⚫广度优先周游⚫若二叉树的高度为h，则从0到h层逐层如下处理：从左到右逐个访问存在的结点。AB

DCEFIHG对右图所示二叉树进行广度优先搜索，得到：A,B,C,D,E,F,G,H,I如图所示的二叉树•先序序列为：ABDEHKMNCFG•中序序列为：DBHEMKNAFCG•后序序列为：DHMNKEBFGCAABEDCHKNMGF5.2.3一个例子如图所示的二叉树是表达式(a-

b)÷(c+d)的语法结构图。•先序序列为：÷-ab+cd•中序序列为：a-b÷c+d•后序序列为：ab-cd+÷÷－ba＋dc5.2.4周游的抽象算法递归算法•先根次序•中根次序•后根次序非递归算法*•先根次序•中根次序•后根次序12算法5.1voidpreOrder(BinTreet){if(

t==NULL)return;visit(root(t));preOrder(leftChild(t));preOrder(rightChild(t));}理解递归算法：大事化小小事化了根据是数学归纳法算法证明：设二叉树结点个数为n，则：算法5.1vo

idpreOrder(BinTreet){if(t==NULL)return;visit(root(t));preOrder(leftChild(t));preOrder(rightChild(t));}算法证明

：设二叉树结点个数为n，则：当n=0时，t=NULL，算法做空操作，算法功能成立。算法5.1voidpreOrder(BinTreet){if(t==NULL)return;visit(root(t));preOrder(leftChild(t));preOrder(right

Child(t));}算法证明：设二叉树结点个数为n，则：当n=0时，t=NULL，算法做空操作，算法功能成立。假设n<i时,算法功能成立，则当n=i时：访问根算法5.1voidpreOrder(BinTre

et){if(t==NULL)return;visit(root(t));preOrder(leftChild(t));preOrder(rightChild(t));}算法证明：设二叉树结点个数为n，则：当n=0时，p=NULL，算法做空操作，算法功能成立。假设n<i时,算法功能成立，则当n

=i时：访问根周游根的左子树左子树中结点个数<i，根据归纳假设算法功能成立算法5.1voidpreOrder(BinTreet){if(t==NULL)return;visit(root(t));preOrder(leftChild(t))

;preOrder(rightChild(t));}算法证明：设二叉树结点个数为n，则：当n=0时，p=NULL，算法做空操作，算法功能成立。假设n<i时,算法功能成立，则当n=i时：访问根周游根的左子树周游根的右子树右子树

中结点个数<i，根据归纳假设算法功能成立算法5.1voidpreOrder(BinTreet){if(t==NULL)return;visit(root(t));preOrder(leftChild(t));preOr

der(rightChild(t));}算法5.2二叉树中序周游的递归算法voidinOrder(BinTreet){if(t==NULL)return;inOrder(leftChild(t));vi

sit(root(t));inOrder(rightChild(t));}算法5.3二叉树后根次序周游的递归算法voidpostOrder(BinTreet){if(t==NULL)return;postOrder(leftChild(t));postOrd

er(rightChild(t));visit(root(t));}广度优先周游算法5.8广度优先周游二叉树voidlevelOrder(BinTreet){BinTreec,cc;Queueq=createEmptyQueue();if(t=

=NULL)return;c=t;enqueue(q,c);while(!isEmptyQueue(q)){c=frontQueue(q);dequeue(q);visit(c);cc=leftChild(c);if(cc!=NULL)enqueue(q,cc);cc=rightCh

ild(c);if(cc!=NULL)enqueue(q,cc);}}5.3二叉树的实现➢5.3.1顺序表示➢5.3.2链接表示➢5.3.3线索二叉树*用一组地址连续的存储单元按层次次序依次存储完全二叉树的结

点。5.3.1顺序表示ABCGFEDHIJABCDEFGHIJ下标0123456789对于一般二叉树，则应将其每个结点与完全二叉树上的结点相对照，存储在一维数组的相应分量中。图5.11一般二叉树及其顺序表示采用顺序表示，类型声明如

下：structSeqBinTree/*顺序树类型定义*/{intMAXNUM;intn;DataType*nodelist;}；typedefstructSeqBINTree*PSeqBINTree;运算的实现算法5.9返

回下标为p的结点的父结点的下标intparent_seq(PSeqBinTreet,intp){if(p<0||p>=t->n)return–1;return(p-1)/2;}算法5.10返回下标为p的结点的

左子结点的下标intleftChild_seq(PSeqBinTreet,intp){if(p<0||p>=t->n)return–1;return2*p+1;}算法5.11返回下标为p的结点的右子结点的下标intrightChild_seq(PSeqBinTreet

,intp){if(p<0||p>=t->n)return–1;return2*(p+1);}5.3.2链接表示二叉树的链接表示是指用一个链表来存储一棵二叉树，二叉树中的每一个结点用链表中的一个链结点来存储，最常用的链接表示方式是左-右指针表示法（llink-

rlink表示法，也称做二叉链表），这种表示法在每个链结点中除存储结点本身的数据外，再设置两个指针字段：llink和rlink，分别存放结点的左子女和右子女所在链结点的存储地址，当结点的某个子女为空时，则相应的指针为空指针。structBinTreeNode;/*二

叉树中结点*/typedefstructBinTreeNode*PBinTreeNode;structBinTreeNode{DataTypeinfo;/*数据域*/PBinTreeNodellink;/*指向左

子女*/PBinTreeNoderlink;/*指向右子女*/};typedefstructBinTreeNode*BinTree;算法5.12返回结点p的左子结点的地址PBinTreeNodeleftChild_link(PBinTreeNodep){if(p==N

ULL)returnNULL;returnp->llink;}算法5.13返回结点p的右子结点的地址PBinTreeNoderightChild_link(PBinTreeNodep){if(p==NULL)returnNULL;returnp->rlink;}ABDC

EFIHGtAB^C^EF^I^^H^^G^^D^图5.12(a)二叉树的二叉链表表示ABDCEFIHG图5.12(b)三叉链表表示t二叉树的生成周游是二叉树各种操作的基础，可以在周游过程中进行各种操作，如

可以在周游过程中生成结点，从而建立一棵二叉树。ABDCEFIHG@@@@@@@@@@例：输入字符序列：ABD@@@CE@G@@FH@@I@@建立如图所示的二叉树，其中，@表示空结点。算法按先根序列创建二叉树

ABDCEFIHG@@@@@@@@@@@算法根据先根序列创建二叉树inti=0;BinTreecreateRest_BTree(char*string)/*递归创建从根开始的二叉树*/{PBinTreeNodepbnode;

charch;ch=string[i++];if(ch=='@')pbnode=NULL;else{pbnode=newstructBinTreeNode;pbnode->info=ch;pbnode->llink=createRest_BTre

e(string);//构造左子树pbnode->rlink=createRest_BTree(string);//构造右子树}returnpbnode;}算法5.1voidpreOrder(BinTreet){if(t=

=NULL)return;visit(root(t));preOrder(leftChild(t));preOrder(rightChild(t));}算法5.1voidpreOrder(BinTreet){if(t==NULL)return;cout<<t->info;preOrder(t-

>llink);preOrder(t->rlink);}//输出二叉树voiddisptree1(BinTreep){//先序输出p为根的二叉树if(p==NULL){cout<<"@";return;}cout<<p->info

;disptree1(p->llink);disptree1(p->rlink);}算法5.1voidpreOrder(BinTreet){if(t==NULL)return;cout<<t->info;pre

Order(t->llink);preOrder(t->rlink);}voiddispTree2(BinTreet){//以括号表示法D(L,R)输出二叉树tif(t==NULL)return;cout<<t->info;if(t->ll

ink!=NULL||t->rlink!=NULL){cout<<"(";dispTree2(t->llink);cout<<",";dispTree2(t->rlink);cout<<")";}}作业：

p.166复习题1、2、8p.168算法题1补充题：1.证明算法5.2二叉树中序周游的递归算法的正确性。网络课堂测试：5二叉树与树（1）5.4二叉树的应用➢5.4.1堆与优先队列*➢5.4.2哈夫曼树及其应用5.4.2哈夫曼树及其应用扩充二叉树的外部路径长度：其中：li为从根到第i

个外部结点的路径长度，m为外部结点的个数1miiEl==扩充二叉树的带权的外部路径长度其中：wi是第i个外部结点的权值，li为从根到第i个外部结点的路径长度，m为外部结点的个数。1miiiWPLwl=

=哈夫曼树假设有一组（无序）实数｛w1,w2,w3,…,wm｝，现要构造一棵以wi（i=1,2,…，m）为权的m个外部结点的扩充的二叉树，使得带权的外部路径长度WPL最小。满足这一要求的扩充二叉树就称为哈夫曼树或最优二叉树。⚫例如以下是

带有相同权值5,4,7,2,5的四棵二叉树。24575(a)24575(b)27545(c)24575(d)它们的带权路径长度分别为：(a)WPL=21+74+54+53+42=73(b)WPL=73+43+53+53+2

1=65(c)WPL=52+52+23+43+72=52(d)WPL=43+23+72+52+52=52其中(c)和(d)树的带权路径长度为最小。可以验证它们恰为最优二叉树。在解某些判定问题时，利用赫夫曼树可以得到最佳判定算法。例如，编制一个将百分制转换成五级分制的程序。通

常的算法是：If(a<60)b=‘E’;elseif(a<70)b=‘D’;elseif(a<80)b=‘C’;elseif(a<90)b=‘B’;elseb=‘A’；⚫在实际生活中，学生的成绩在五个等级上的分布是不均匀的

。假设其分布规律如下表示：分数0~5960~6970~7980~8990~100比例数0.050.150.400.300.10d<60d<90d<80d<70EDCABYYYYNNNN0.050.150.40.30.1WPL=3.15d<60CBDAEY

YYYNNNN0.40.30.150.050.1WPL=2.0570≤d＜8080≤d＜9060≤d＜70d<60d<70d<80CEDNNYYYYd<90AN0.1NB0.30.40.150.05WPL=2.2赫夫曼最早给出了一个带有一般规律得算法，俗称赫夫曼算法。现以

最优二叉树为例叙述如下：(1)根据给定得n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树均空。(2)在F中选取两棵根结点的权值最小的树

作为左右子树，构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。(3)在F中删除这两棵树，同时将新得到的二叉树假如F中。重复(2)、(3)，直到F只含有一棵树为止。哈夫曼树的构造——哈夫曼算法54725(1)赫夫曼树的构造过程42575(2)642

557(3)10642755(4)6101342755(5)6131023设d={d1,d2,…,dn}w={w1,w2,…,wn}d为要编码的字符集合，w为d中各种字符出现的频率。要求：（1）编码总长最短；（2）若did

j,di编码不是dj编码的前缀。哈夫曼树的应用——哈夫曼编码A00B01C10D11原文：ABAACCBADCA电文：0001000010100100111000编码电文长度为22⚫如果希望电文长度尽可能地短，可以考虑让原文中出现次数多的字符采用尽可能短的编码。A0B00C1D01原文：AB

AACCBADCA电文：00000110000110编码电文长度为14？前缀编码：若要设计长短不等的字符编码，则必须保证任何一个字符的编码都不是另一个字符的编码的前缀。按前缀编码翻译电文，一定能唯一地被翻译成原文。可以利用哈夫曼树的原理来设计二

进制前缀编码。用构造哈夫曼树以完成哈夫曼编码：把d1,d2,…,dn作为外部结点，把w1,w2,….,wn作为外部结点的权，构造哈夫曼树。在哈夫曼树中把从每个结点引向其左子女的边上标上0；把从每个结点引向其右子女的边上标上1。从根结点到叶子结点的路径上的数字拼接起来就是这个叶

子结点字符的编码。A5B2C3D1原文：ABAACCBADCA电文：01100010101100111100电文长度为20ACBD000111A0B110C10D1115.5树及其抽象数据类型树的表示方法：(c)凹入表（a）树形表示ABCDEFIJGH(A(

B(D)(E(I)(J))(F))(C(G)(H)))(d)嵌套括号表示法CDEIJFGHAB(b)文氏图树是包括n(n>=0)个结点的有限集T。当T非空时，满足：（1）有且仅有一个特别标出的称为根的结点；（2）除根结点外，其余结点可分为m（m>=0）个互不相交非空的有限集

T1,T2,…,Tm,其中每一个集合本身又是一棵树，称为根的子树(Subtree)。空树：不包括任何结点的树。5.5.1基本概念⚫在树中也可以定义父结点、子结点、路径、路径长度、结点的度、树的度等概念，与前面二叉树中定义相同。无序树、有序树对子树

的次序不加区别的树叫作无序树。对子树之间的次序加以区别的树叫作有序树。例如在图5.24中，按无序树的概念t和t'是同一棵树，按有序树的概念则是不同的树，本章讨论的树一般是有序树。结点的次序在有序树中可以从左到右地规

定结点的次序。按从左到右的顺序，我们可以把一个结点的最左边的子结点简称为最左子结点，或直接称为长子，而把长子右边的结点称为次子。例如在t中结点B是结点A的长子，结点C是结点A的次子，是结点B的兄弟。5.5.2抽象数据类型ADTTreeisoperation

sTreecreateEmptyTree(void)创建一颗空树TreeconsTree(Nodep,Treet1,...,Treeti)以p为根，t1,...,ti为子树创建一颗树intisNull(

Treet)判断树t是否为空树Noderoot(Treet)返回树t的根结点。Nodeparent(Nodep)返回结点p的父结点。TreeleftChild(Treet)返回树t的长子树。TreerightSi

bling(Treet)返回树t的右兄弟树。endADTTree5.5.3树的周游周游的定义:按某一规律系统的访问树中的所有结点，并使每个结点恰好被访问一次。周游的方法：按深度方向和按宽度方向周游。按深度方向（以

右图为例）先根次序后根次序先根次序(1,2,3,5,8,9,6,10,4,7)（1）访问根结点；（2）从左到右按先根次序周游根结点的每棵子树。后根次序(2,8,9,5,10,6,3,7,4,1)（1）从左到右按后根次序周游根结点的每棵子树;（2）访问

根结点。按宽度方向周游先访问层数为0的结点，然后从左到右逐个访问层数为1的结点，依此类推，直到访问完树中的全部结点。层次序列（1，2，3，4，5，6，7，8，9，10）5.6树的实现structParTreeNode/*树中结点

结构*/{DataTypeinfo;/*结点中的元素*/intparent;/*结点的父结点位置*/};structParTree{structParTreeNodenodelist[MAXNUM];/*存放树中的结点*/intn;/

*树中结点的个数*/};typedefstructParTree*PParTree;5.6.1父指针表示法用一组连续空间存储树的结点，并附设一个指示器指示其双亲结点的位置。结构类型如下：优点：a)容易找到父结点及其所有的祖先；

b)能找到结点的子女和兄弟；缺点：a)没有表示出结点之间的左右次序；b)找结点的子女和兄弟比较费事。改进方法：按一种周游次序在数组中存放结点,。常见的一种方法是依次存放树的先根序列，如下图：(a)(b)图5.5一棵树的父指针表示算法5.65.75.6.2树的子表表示法结点表中

的每一元素又包含一个子表，存放该结点的所有子结点。结点表顺序存放，子表用链接表示。structEdgeNode/*子表中节点的结构*/{intnodeposition;structEdgeNode*link;};structChiTreeNode/

*结点表中节点的结构*/{DataTypeinfo;structEdgeNode*children;};子表表示的树结构定义如下：structChiTree/*树结构*/{structChiTreeNodenodelist[MAXNUM];introot;/*根结点的位置*/intn;/

*结点的个数*/}typedefstructChiTree*PChiTree;求某个结点的最左子女运算很容易实现，找到结点的全部子女也很容易，但求某个结点的父母和右兄弟实现起来比较费事。另一个缺点是：合并若干个

子树构成一个新树时（createTree_chitree操作）也要考虑多个结点表的合并问题，由于这些结点表通常用顺序方式表示，所以合并起来比较麻烦。infoparent0a1b2d3e4h5i6j7c8f9g1

72346895图5.6树的子表表示法children在树的每个结点中，除信息域外，增加指向其最左子女和右兄弟的指针。structCSNode;/*树中结点结构*/typedefstructCSNode*PCSNode;//结点的指针类型

structCSNode/*结点结构定义*/{DataTypeinfo;/*结点中的元素*/PCSNodelchild;/*结点的最左子女的指针*/PCSNodersibling;/*结点的右兄弟的指针*/}

;typedefstructCSNode*CSTree;/*树类型定义*/5.6.3树的长子-兄弟表示法tabdcehijfg图5.7树的长子兄弟表法树林：是m（m>=0）棵互不相交的树所

组成的集合。树林中所有的树都是有序的，彼此称为兄弟。5.7树林先根次序周游：首先访问树林中第一棵树的根结点；然后先根次序周游根结点的所有子树构成的树林；最后先根周游除去第一棵树后剩下的树林。A,B,C,K,

D,E,H,F,J,G5.7.1树林的周游后根次序周游：首先后根次序周游第一棵树根结点的所有子树构成的树林；然后访问第一棵树的根结点；最后后根周游除去第一棵树后剩下的树林。B,K,C,A,H,E,J,F,G,

D5.7.2树林的存储表示•父指针表示法•子表表示法•长子-兄弟表示法树林的父结点表示方法infoparent0A1B2C3K4D5E6H7F8J9G12359867树林的子表表示法tABDCEHJ

KFG树林的长子兄弟表示法5.7.3树林与二叉树的转换1.树、树林转换为二叉树执行步骤：（1）在所有相邻的兄弟结点之间连一条线；（2）对每个非终端结点，只保留它到其最左子女的连线，删去它与其它子女的连线；（

3）以根结点为轴心，将整棵树进行旋转。树、树林二叉树ABCKDEFGHJ图5.20树林转换为二叉树ABCKDEFGHJ⚫树->二叉树ABDCEFHG•兄弟连线•保留父母到第一个(最左)孩子的连线•去除父母与其它孩子的连线•第一个

孩子作为左孩子，右兄弟降为右子女ABDCEFHGABDCEFHG2.二叉树转换为树、树林执行步骤：（1）若某结点是其父母的左子女，则把该结点的右子女，右子女的右子女，……,都与该结点的父母用线连接起来；（2）去掉原二叉树中所有父

母到右子女的连线。ABDCEKHFJG图5.22二叉树转换为树林ABDCEKHFJG图5.22二叉树转换为树林⚫P.166⚫复习题6、11、12、13、14⚫网络课堂测试：5二叉树与树（2）⚫实验4.1----4.4小结⚫树、树林、二叉树的一些基本概念和术语；⚫二叉链表存储结构⚫树、二叉

树的周游⚫哈夫曼树的构造方法及应用