专业课课件数据结构第9讲6章

6.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码

6.6树和森林的表示方法一、树的三种存储结构二、树与二叉树的转换一、树的三种存储结构1.双亲表示法2.孩子链表表示法3.树的二叉链表(孩子-兄弟）存储表示法ABCDEFGr=0n=70

A

-11

B

02

C

03

D

04

E

25

F

26

G

5dataparent1.双亲表示法:

树

结点

typedefstructPTNode{Elemdata;

intparent;//双亲位置域

}

PTNode;

dataparent#defineMAX_TREE_SIZE100结点结构:C语言的类型描述:typedefstruct{

PTNodenodes[MAX_TREE_SIZE];

int

r,n；

//根结点的位置和结点个数

}

PTree;树结构:0

A1

B

2C

3

D

4

E

5

F

6

G

0123456r=0n=7ABCDEFG64

5

1

2

32.孩子链表表示法:1。树结点2。孩子链表的头结点3。孩子链表结点datafirstchildchildnextchildtypedefstructCTree{CTBoxnodes[MAX_TREE_SIZE];

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

};树结点:typedefstructCTNode{

intchild;

structCTNode*nextchild;}*ChildPtr;孩子链表结点:

typedefstructCTBox{Elemdata;ChildPtrfirstchild;//孩子链的头指针

};孩子链表头结点:3.树的二叉链表(孩子-兄弟）存储表示法ABCDEFG二叉树ABCEDFG

ABCEDFG树二叉链表存储表示firstchilddatanextsiblingC语言的类型描述:typedefstructCSNode{Elemdata;

structCSNode*firstchild,*nextsibling;}CSNode,*CSTree;

firstchilddatanextsibling

6.6树和森林的表示方法一、树的三种存储结构二、树与二叉树的转换1.树转换为二叉树2.二叉树还原成树3.森林转换成二叉树二、树与二叉树的转换举例：ABECDFGHIABEDCIIFG1.树转换为二叉树树转换为二叉树的步骤:加线：在兄弟结点之间加一连线；抹线：对任何结点，除了其最左的孩子外，抹掉该结点原先与其孩子之间的连线；旋转：将水平的连线和原有的连线，以树根结点为轴心，按顺时针方向粗略地旋转450。举例：ABEDCIHFGABECDFGHI2.二叉树还原成树二叉树还原成树的步骤加线：如果p结点是双亲结点的左孩子;

则将p结点的右孩子,右孩子的右孩子,……,沿着右分支搜索到的所有右孩子都分别与p结点的双亲用线连接起来;抹线：抹掉原二叉树中所有结点与右孩子的连线；调整：将结点按层次排列,形成树的结构.

森林和二叉树的对应关系设森林

F=(T1,T2,…,Tn);

T1

=(root，t11,t12,…,t1m);二叉树

B=(LBT,Node(root),RBT);3.森林转换成二叉树T1T11,T12,…,T1mT2,…,TnLBTRBTroot由森林转换成二叉树的转换规则为:若F=Φ，则B=Φ;

由ROOT(T1)

对应得到Node(root);否则，由(t11,t12,…,t1m)

对应得到LBT;由(T2,T3,…,Tn)

对应得到RBT。ABDCEFIHGJABCDEFHGIJ举例：ABCDHGIJEF

森林转换成二叉树的步骤:转换：将森林中的每一颗树转换成二叉树;连线：将各颗转换后的二叉树的根结点相连；旋转：将添加的水平线和原有的连线,

以第一颗树的根结点为轴心,按顺时针方向旋转450。6.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.1树的类型定义6.2二叉树的类型定义6.3二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码一、树的遍历二、森林的遍历三、树的遍历的应用6.7树和森林的遍历一.树的遍历

有三种搜索策略:按层次遍历:先根遍历:后根遍历:若树不空，则先访问根结点，然后依次先根遍历各棵子树。若树不空，则先依次后根遍历各棵子树，然后访问根结点。若树不空，则自上而下自左至右访问树中每个结点。层次遍历时顶点的访问次序：ABCDEFGHIJK先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDAABCDEFGHIJKBEFDCGHIJKA层次遍历时顶点的访问次序：先根遍历时顶点的访问次序：ABEFCDGHIJK后根遍历时顶点的访问次序：EFBCIJKHGDAABCDEFGHIJK中序遍历一、树的遍历二、森林的遍历三、树的遍历的应用6.7树和森林的遍历

BCDEFGHIJK1。森林中第一棵树的根结点；2。森林中第一棵树的子树森林；3。森林中其它树构成的森林。可以分解成三部分：二.森林的遍历

BCDEFGHIJK先序遍历：中序遍历：BEF

C

DGHIJKEFB

C

IJKHGD

若森林不空，则

1.访问森林中第一棵树的根结点;2.先序遍历森林中第一棵树的子树森林;3.先序遍历森林中(除第一棵树之外)其余树构成的森林。森林的先序遍历若森林不空，则

1.中序遍历森林中第一棵树的子树森林;

2.访问森林中第一棵树的根结点;3.中序遍历森林中(除第一棵树之外)其

余树构成的森林。森林的中序遍历FEKJIHG

CB

后序遍历：若森林不空，则

1.后序遍历森林中第一棵树的子树森林;

2.后序遍历森林中(除第一棵树之外)其

余树构成的森林。

3.访问森林中第一棵树的根结点;森林的后序遍历

BC

DEFG

H

I

J

KBEFDCGHIJK先序遍历：BEF

C

DGHIJK中序遍历：EFB

C

IJKHGD

树的遍历和二叉树遍历的对应关系？先根遍历树后根遍历二叉树先序遍历中序遍历后序遍历森林先序遍历中序遍历＝＝＝≠转换转换＝一、树的遍历二、森林的遍历三、树的遍历的应用6.7树和森林的遍历1。输出树中所有从根到叶子的路径2。构造树的存储结构三、树的遍历的应用1。输出树中所有从根到叶子的路径例如：对左图所示的树，其输出结果应为：ABACEACFGADABCDEFGABCDEFGABCEDFG树二叉链表存储表示firstchilddatanextsibling孩子－兄弟链表先序递归遍历，在遍历过程中使用堆栈保存路径

算法基本步骤:如果树空,则退出;否则:

结点进栈,

如果是树的叶子结点,则打印路径(栈中结点);

否则先序遍历第一个颗子树;

结点出栈；

依次先序遍历第一个颗子树的兄弟;ABCDEFGvoidAllPath(BitreeT,Stack&S){

if（T）{

Push(S,T->data);

if(!T->firstchild)Printstack(S);//一条路径

elseAllPath(T->firstchild,S);//遍历第一颗树

Pop(S);

AllPath(T->nextsibling,S);//遍历第一颗树的兄弟

}//if}//OutPath//输出森林中所有从根到叶的路径问题：字符序列的输入形式？ 树的存储结构？2。构造树的存储结构要求：从键盘输入一个字符序列，构造一棵树。ABCDEFGABCDEFG(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCDE

假设以二元组(双亲,结点)的形式，自上而下、自左而右依次输入树的各边，建立树的孩子-兄弟链表。ABCDEFG(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)ACDBE(‘C’,‘F’)F(‘E’,‘G’)GABCDEFG例如:对下列所示树的输入序列应为:(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)(‘C’,‘F’)(‘E’,‘G’)ABCD(‘#’,‘A’)(‘A’,‘B’)(‘A’,‘C’)(‘A’,‘D’)(‘C’,‘E’)EABCDErrrr(‘C’,‘F’)FFr(‘E’,‘G’)GGpvoidCreatTree(CSTree&T){T=NULL;

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

;scanf(&fa,&ch);)

{ p=GetTreeNode(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;}

//链接其它孩子结点

6.1树的类型定义6.2二叉树的类型定义6.3

二叉树的存储结构6.4二叉树的遍历6.5线索二叉树6.6树和森林的表示方法6.7树和森林的遍历6.8哈夫曼树与哈夫曼编码6.8哈夫曼树与

哈夫曼编码一.最优树的定义二.如何构造最优树三.前缀编码

一、最优树的定义

路径长度：路径上分支的数目。

路径：从树中一个结点到另一个结点之间的分支所构成的通路。

结点的带权路径长度：从树根到该结点之间的长度l与结点权值w的乘积(l*w)

。

树的带权路径长度：树中所有叶子结点的带权路径长度之和：

WPL(T)=wklk

2754927975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954设有n个叶子结点，且每个叶子结点有一个权值，则包含这n个叶子结点的所有m叉树中，必存在一棵其带权路径长度取最小值的树，称为“最优树”。最优树可能不止一个！定义：6.8哈夫曼树与

哈夫曼编码一.最优树的定义二.如何构造最优树三.前缀编码27975492WPL(T)=72+52+23+43+92=60WPL(T)=74+94+53+42+21=8954二、如何构造最优树（哈夫曼算法）问题：已知n个权值，用n个权值作为叶子结点，构造一棵二叉树，使该二叉树的带权路径长度最短。27975492WPL(T)=60WPL(T)=8954二、如何构造最优树（哈夫曼算法）根据给定的n个权值{w1,w2,…,wn}，构造n棵二叉树的集合：F={T1,T2,…,Tn}，其中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;(1)在F中选取其根结点的权值为最小的两棵二叉树,分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;(2)从F中删去这两棵树，同时加入刚生成的新树;(3)重复

(2)

和

(3)

两步，直至F中只含一棵树为止。问题：已知n个权值，用n个权值作为叶子结点，构造一棵二叉树，使该二叉树的带权路径长度最短。例如:已知权值W={5,6,2,9,7}956275276976713952767139527952716671329哈夫曼树wpl＝6×2＋7×2＋5×3＋2×3＋9×2

＝65可以证明哈夫曼树是最优树例如:已知权值W={5,6,2,9}，构造最优三叉树9562

256139222579226

wpl＝2×2＋5×2＋6×2＋9×1

＝35

wp2＝2×2＋5×2＋6×1＋9×1

＝290如果（n－1）Mod（m－1）＝0，则n个结点正好构成一棵m叉的正则树。6.8哈夫曼树与

哈夫曼编码一.最优树的定义二.如何构造最优树三.前缀编码

假设电文由A,B,C,D四种字符组成.

它们的编码分别为00,01,10和11.

则电文‘ABACCDA’的编码为:00010010101100,

总长为14位.

为减少编码长度,重新设A,B,C,D四个字符的编码为0,00,1和01.

则电文编码为000011010,总长为9位.三、前缀编码ABA0000AAAABBBAA1,000,01,0011000101010011前缀编码指的是，编码字符集中任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。000101010010111ABCD00011011是前缀编码不是前缀编码是前缀编码(2)000101不是前缀编码(3)010010111是前缀编码ABCD(1)00011011是前缀编码ABCD01110000011011(1)D111A001B01000C1011(3)BCD010100011(2)AABCD01110000011011(1)ABCD011011010010101(3)那一种编码好？1。假设A,B,C,D概率相同,且概率值均为k（25％）wpl(1)=k*2*4＝8kwpl(3)=k*1+k*3*2+k*2＝9k2。概率不同,且A为0.5,B为0.1,C为0.1,D为0.3wpl(1)=0.5*2+0.1*2*2+0.3*2＝2Wpl(3)=0.5*1+0.1*2*3+0.3*＝1.7平均长度:平均长度:AAAABBBBABCD利用哈夫曼树可以构造一种不等长的二进制编码，并且构造所得的哈夫曼编码是一种最优前缀编码，使所传电文的总长度最短。举例:已知某系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H,其概率分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11

试设计哈夫曼编码.设权w={5,29,7,8,14,23,3,11}

ABCDEFGH设权w={5,29,7,8,14,23,3,11}295783142311538871511191429234229581000000111100011100010011001111011011101111举例:已知某系统在通讯联络中只可能出现八种字符A,B,C,D,E,F,G,H,其概率分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11

试设计赫夫曼编码.哈夫曼编码