树和二叉树4(树和森另)

1一、双亲表示法二、孩子链表表示法三、树的二叉链表(孩子-兄弟）存储表示法6.4树和森林6.4.1树的存储结构2一、双亲表示法（顺序存储）

用一组连续空间存储树的结点，同时在每个结点中附设一个域指示其双亲的位置。aedbihgcf021345678dataparent

0a-11b02

c03d14e15f26g47h4

8i43

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}PTNode;#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:

dataparent4typedefstruct{PTNodenodes[MAX_TREE_SIZE];

intr,n;//根结点的位置和结点个数

}PTree;树结构:5(1)由于树中每个结点可有多个孩子，则每个结点可设多个指针成员，每个指针指向一个孩子。对于度为m的树，结点结构如下：datadegree

c1c2

…ckdatac1c2c3

…cm(2)每个结点有几个孩子，就有几个指针。二、孩子表示法（链式存储）问题：会有太多的空指针！(3)将每个结点的孩子结点排列起来，连接成一个单链表。n个结点有n个孩子链表，n个孩子链表的头指针可放在数组中，称为孩子链表。60a12

1b342c53d4e6785f6g7h8i孩子链表aedbihgcf0213456787typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子结点结构:

childnextchildC语言的类型描述:8

typedefstruct{Elemdata;ChildPtrfirstchild;//孩子链的头指针}CTBox;双亲结点结构

datafirstchildtypedefstruct{CTBoxnodes[MAX_TREE_SIZE];

intn,r;//结点数和根结点的位置

}CTree;树结构:带双亲的孩子链表：将双亲表示法和孩子表示法结合起来。aedbihgcf0

a-112

1b0342c053d14e16785f26g47h48i4021345678三、孩子兄弟表示法：又称树的二叉链表表示法即用二叉链表作树的存储结构。结点中的两个指针分别指向该结点的第一个孩子和下一个兄弟aedbihgcf

a

b

c

d

e

f

g

h

i

11typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;C语言的类型描述:结点结构:

firstchilddatanextsibling12ABCDEFGrootABCEDFGABCEDFG

画出以下存储结构root13树ABCED二叉树ABCEDA^BCDE^^^^^6.4.2森林与二叉树的转换

从树的链表表示的定义可知，任何一棵与树对应的二叉树，其右子树必空。若把森林中第二棵树的根结点看成是第一棵树的根结点的兄弟，则可导出森林和二叉树的关系。森林

二叉树ABCDEFGHIJABCFEGDIHJ15森林与二叉树互相转换的方法：一.森林转换成二叉树①将森林中的每棵树转换为二叉树；②将第i+1棵树作为第i棵树的右子树，依次连接成一棵二叉树；二.二叉树转换成森林①将二叉树根的右子树作为另一棵二叉树，将新分出的二叉树转换成森林；②将二叉树转换成森林；1247356891016

树的遍历1.按层次：先访问第一层的结点，之后访问第二层的结点。2.先根遍历：先访问根结点，依次先根遍历其各子树。3.后根遍历：依次后根遍历其各子树,再访问根结点。6.4.3树和森林的遍历17

树先根：ABEFCGIJD

后根：EFBIGJCDA二叉树先序遍历中序遍历ABCFEGDJIABCFEGDJI181.森林中第一棵树的根结点；2.森林中第一棵树的子树森林；3.森林中其它树构成的森林。可以分解成三部分:森林BCDEFGHIJK森林的遍历19若森林不空，则访问森林中第一棵树的根结点;先序遍历森林中第一棵树的子树森林；先序遍历森林中(除第一棵树之外)其余树构成的森林。先序遍历即：依次从左至右对森林中的每一棵树进行先根遍历。20

中序遍历

若森林不空，则中序遍历森林中第一棵树的子树森林;访问森林中第一棵树的根结点;中序遍历森林中(除第一棵树之外)其余树构成的森林。即：依次从左至右对森林中的每一棵树进行后根遍历。例如：先序遍历：ABCDEFGHIJ中序遍历：BCDAFEHJIG结论：二叉树森林先序遍历先序遍历中序遍历中序遍历ABCDEFGHIJABCFEGDIHJ22设树的存储结构为孩子兄弟链表typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;一、建树的存储结构二、先序遍历树（森林）三、求树(森林)的深度四、输出树中所有从根到叶子的路径一、建树的存储结构的算法:

和二叉树类似，不同的定义相应有不同的算法。

假设以二元组(F,C)的形式自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。ABCDEFG例如:对下列所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)可见，算法中需要一个队列保存已建好的结点的指针voidCreatTree(CSTree&T){T=NULL;

for(scanf(&fa,&ch);ch!=

;

scanf(&fa,&ch);){ p=New

CSNode；

p->data=ch;//创建结点

EnQueue(Q,p);//指针入队列

if(fa==

)T=p;//所建为根结点

else{

}//非根结点的情况

}//for}//CreateTree ……GetHead(Q,s);//取队列头元素(指针值)while(s->data!=fa){//查询双亲结点

DeQueue(Q,s);GetHead(Q,s);}if(!(s->firstchild))

{s->firstchild=p;r=p;}

//链接第一个孩子结点else

{r->nextsibling=p;r=p;}

//链接其它孩子结点

27ABCEDA^BCDE^^^^^二、先序遍历树（森林）的递归算法：28voidpre_order_tree(CSTreeT){

for(p=T;p;p=p→nextsibling){printf(p→data)；

if(p→firstchild≠NULL)pre_order_tree(p→firstchild)；

}}//preorder递归算法：29voidOutPath(BitreeT){

while(T){printf(p→data)；

if(T->firstchild)

OutPath(T->firstchild);

T=T->nextsibling;

}//while}//OutPath//while循环写的遍历算法30ABCEDA^BCDE^^^^^三、求树的深度的算法：31intDepth(CSTreeT){if(T==NULL)return0;else{d1=Depth(T->firstchild);d2=Depth(T->nextsibling);returnmax(d1+1,d2)}三、求树的深度的算法：32四、输出树中所有从根到叶子的路径的算法:ABCDEFGHIJK例如：对左图所示的树，其输出结果应为：ABEABFACADGHIADGHJADGHK33voidOutPath(BitreeT){

while(T){printf(p→data)；

if(T->firstchild)

OutPath(T->firstchild);

T=T->nextsibling;

}//while}//OutPath//原有遍历算法34voidOutPath(BitreeT,Stack*S){

while(T){

Push(*S,T->data);

if(!T->firstchild)Printstack(*S);

elseOutPath(T->firstchild,S);

Pop(*S);

T=T->nextsibling;

}//while}//OutPath//输出森林中所有从根到叶的路径3536互联网上的域名如同我们现实生活中的门牌号码，可以在纷繁芜杂的网络世界里准确无误地把我们指引到我们要访问的站点。37结点间的路径长度：

两个结点之间的分支数。结点的权值：

附加在结点上的信息。结点带权路径：

结点上权值与该结点到根之间的路径长度的乘积。6.5哈夫曼树及其应用6.5.1最优二叉树——哈夫曼树ABCDEFGHIJ38树的带权路径长度：

(WeightPathLength)

树中所有叶子结点的带权路径长度之和。WPL=(叶到根的平均路径长度)哈夫曼(huffman)树：使WPL取最小值的二叉树，又称最优二叉树ABCDEFGHIJ203050例：有n个叶子结点，第i个叶子结点的权值为Wi，根到该结点的路径长度为Li，则：39例如，给定权值{5,4,7,2,5}，可生成多棵二叉树WPL=2*1+7*3+4*3+5*3+5*3=6557254(a)57254(b)WPL=2*1+4*2+5*3+7*4+5*4=7340WPL=(2+4)*3+(7+5+5)*2=52WPL=(5+5+7)*2+(2+4)*3=5257254(c)57254(d)41如何构成一棵最优二叉树？

(哈夫曼算法)

(1)根据n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn}，其中每棵二叉树Ti只有一个带权为Wi的根结点，其左右子树均空。(2)在F中选两棵根结点的权值最小的树作为左右子树构成一棵新的二叉树，且根结点的权值为其左右子树根结点的权值之和。(3)在F中删除这两棵树，同时将新的二叉树加入F(4)重复(2)、(3)，直到F只含一棵树为止。9例如:已知权值W={5,6,2,9,7}5627257697671392576713925792571667132944哈夫曼树的应用:在解决某些判定问题时的最佳判定算法。例:将学生百分成绩按分数段分级的程序。若学生成绩分布是均匀的，可用二叉树结构来实现。a<60a<70a<80a<90不及格中等良好优秀及格YNYNYNYN输入10000个数据，则需进行28000次比较。读入一个a值平均判断：(1+2+3+4+4)*0.2=2.8(次)45分数0—5960—6970—7980—8990—99比例0.050.150.40.30.10学生成绩分布不是均匀的情况：构造一棵哈夫曼树：再将每一比较框的两次比较改为一次：WPL=0.4*1+0.3*2+0.15*3+(0.05+0.1)*4=2.05WPL=(0.4+0.3+0.1)*2+(0.05+0.15)*3=2.20输入10000个数据，仅需进行22000次比较。0.40.050.10.150.150.30.30.670≤a<80a<60及格中等良好80≤a<9060≤a<70不及格优秀YNYNYNYN

不及格Ya<90a<80a<70a<60优秀中等及格良好YNNNYYYN46

哈夫曼编码是二进制编码形式，用于(网络)通信中，它作为一种最常用无损压缩编码方法，在数据压缩程序中具有非常重要的应用。

如需传送字符串‘ABACCDA’，只有4种字符:A、B、C、D，只需两位编码。如分别编码为00、01、10、11，上述字符串的二进制总长度为14位。

在传送信息时，希望总长度尽可能短，可对每个字符进行不等长度的编码，且出现频率高的字符编码尽量短。如A、B、C、D的编码分别为0、00、1、01时，上述电文长度会缩短，但可能有多种译法。如‘0000’可能是‘AAAA’,‘ABA’,‘BB’。6.5.2哈夫曼编码47若要设计不等长编码，任一字符的编码都不是另一个字符编码的前缀。这种编码称为前缀编码。

可利用二叉树来设计二进制的前缀编码，将每个字符出现的频率作为权，设计一棵哈夫曼树，左分支为0，右分之为1，就得到每个叶子结点的编码。95271667132900001111000111100101例如：编码：0、00、1、01就不是前缀编码。[结论1]存储结构：#defineN字符数目；#defineM结点数目；//m=2n-1huffman树用静态三叉链表做存储结构，且0号单元不用huffman编码用指向字符的指针数组来动态管理存储；且0号单元不用[证]：m=n0+n1+n2

，因为：n1=0,n2=n0-1,

所以：m=2n0–1,即m=2n-1.huffman树中没有度为1的结点。[结论2]有n个叶子结点的huffman树中共有m=2n-1个结点。49Data

ABDCENFGI...lchild245070000...rchild306089000...

123456789

FAHDBCGFEI123456789补充：静态链表存储typedefstruct{

chardata；

intweight；

intparent，lch，rch；

}NodeType；

//huffman树结点类型

typedefchar**HufCode

；

//动态分配指针数组存储huffman编码typedef

NodeType

HufTree[M+1]；

//静态三叉链表存储huffman树1234hcd例：设有4个结点a、b、c、d，权值分别为(0.4，0.3，0.1，0.2)。dataweightparentlchrcha

0.4000

b

0.3000

c

0.1000

d

0.20000.303450.6

0

2561.0016770123456750‘\0’10‘\0’110‘\0’111‘\0’61.0

01

0.4

01

0.3

01

0.10.21.0a0.6b0.3cd算法1：已知n个字符的权值，生成一棵huffman树。voidhuff_tree(intw[n],HufTree&ht){//w存放权值for(i=1；i≤n；i++){//哈夫曼树初始化ht[i].weight=w[i-1]；ht[i].parent=0；ht[i].lch=0；ht[i].rch=0

}；ht[n+1..m].parent=0；for(i=n+1；i≤m；i++){

//构造n-1个非叶子结点select(i-1,s1,s2)；

//在ht[1..i-1]中选择两个双亲为0并且权值最小的两个结点,//最小结点位置为s1,次小的位置为s2。

ht[i].weight=ht[s1].weight+ht[s2].weightht[i].lch=s1；ht[i].rch=s2；

ht[s1].parent=i；ht[s2].parent=i；}；}//huff_tree5301234

cd0123dataweightparentlchrcha

0.4000

b

0.3000

c

0.1000

d

0.20000.30

3450.6

0

2561.00

167701234567561234hcd0‘\0’10‘\0’110‘\0’111‘\0’hcdtypedef

char**

HufCode；

//动态分配指针数组存储huffman编码HufCode

hcd;char*cd;‘\0’start0start

‘\0’0

算法2：由huffman树求n个字符的haffman编码voidhuf_code(HufCode

&hcd，HufTree

ht，intn){hcd=(hufcode)malloc((n+1)*sizeof(char*))；//指针数组空间cd=(char*)malloc(n*sizeof(char)）；//求编码的临时空间for(i=1；i≤n；i++){

cd[n-1]=‘\0’；//编码结束符

start=n-1；c=i；f=ht[c].parent；

while（f≠0