数据结构第六章学习教案.pptx

《数据结构第六章学习教案.pptx》由会员分享，可在线阅读，更多相关《数据结构第六章学习教案.pptx（81页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、会计学1数据结构数据结构(sh j ji u)课件第六章课件第六章第一页，共81页。2第第第第6 6章章章章 树和二叉树（树和二叉树（树和二叉树（树和二叉树（Tree&Binary Tree Tree&Binary Tree）6.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索(xin su)二叉树6.4 树和森林6.5 赫夫曼树及其应用特点：非线性结构，一个直接(zhji)前驱，但可能有多个直接(zhji)后继（1：n）第1页/共81页第二页，共81页。36.16.1 树的基本概念树的基本概念树的基本概念树的基本概念1.树的定义2 若干术语3.逻辑结构4.存储(cn ch)结构5.树的

2、运算第2页/共81页第三页，共81页。41.1.树的定义树的定义树的定义树的定义(dngy)(dngy)注1：过去(guq)许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个或多个(n0)结点组成的有限集合T，有且仅有一个结点称为(chn wi)根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树。第3页/共81页第四页，共81页。5树的表示法有几种树的表示法有几种树的表示法有几种树的表示法有几种(j(j zh zh n n)：图形表示法嵌套集合表

3、示法广义表表示法目录(ml)表示法左孩子右兄弟表示法这些表示法的示意图参见(cnjin)教材P120树的抽象数据类型定义参见教材P118-119第4页/共81页第五页，共81页。6图形图形图形图形(txng)(txng)表示表示表示表示法：法：法：法：教师学生其他人员2003级 2004级 2005级2006级河南大学物理系计算机系化学系叶子(y zi)根子树第5页/共81页第六页，共81页。7广义广义广义广义(gu(gu ngy)ngy)表表示法表表示法表表示法表表示法(A(B(E(K,L),F),C(G),D(H(M),I,J)根作为由子树森林组成(z chn)的表的名字写在表的左边dat

4、alink 1 link 2.link n麻烦问题：应当(yngdng)开设多少个链域?第6页/共81页第七页，共81页。8左孩子左孩子左孩子左孩子(hi zi)(hi zi)右兄弟右兄弟右兄弟右兄弟表示法表示法表示法表示法AAB BC CDDE EF FGGHHI IJ JKKL LMM数据左孩子 右兄弟(A(B(E(K,L),F),C(G),D(H(M),I,J)第7页/共81页第八页，共81页。9 树的抽象数据类型定义树的抽象数据类型定义树的抽象数据类型定义树的抽象数据类型定义(dngy)(dngy)（见教材(jioci)P118-119）ADT Tree数据对象(duxing)D:数据

5、关系R:基本操作 P：ADT Tree若D为空集，则称为空树；/允许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系：root 唯一 /关于根的说明 DjDk=/关于子树不相交的说明 /关于数据元素的说明D是具有相同特性的数据元素的集合。/至少有15个第8页/共81页第九页，共81页。102.2.若干若干若干若干(rugn)(rugn)术语术语术语术语即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支(fnzh)的所有结点即该结点下层子树中的任一结点ABCGEID

6、HFJMLK 根 叶子(y zi)森林有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。第9页/共81页第十页，共81页。112.2.若干若干若干若干(rugn)(rugn)术语（续）术语（续）术语（续）术语（续）即树的数据元素结点挂接的子树数（有几个直接后继就是(jish)几度，亦称“次数”）结点(ji din)结点(ji din)的度结点(ji din)的层次终端结点(ji din)分支结点(ji din)树的度树的深度(或高度)ABCGEIDHF

7、JMLK从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的度 ；树的深度1334第10页/共81页第十一页，共81页。123.3.树的逻辑树的逻辑树的逻辑树的逻辑(lu j)(lu j)结构结构结构结构 (特点特点特点特点)：一对多（一对多（一对多（一对多（1:n1:n1:n1:n），有多个直接后继），有多个直接后继），有多个直接后继），有多个直接后继(huj)(huj)(huj)(huj)（如家谱树、目录树等等），但只有一（如家谱树、目录树

8、等等），但只有一（如家谱树、目录树等等），但只有一（如家谱树、目录树等等），但只有一个根结点，且子树之间互不相交。个根结点，且子树之间互不相交。个根结点，且子树之间互不相交。个根结点，且子树之间互不相交。4.树的存储(cn ch)结构 讨论1：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。第11页/共81页第十二页，共81页。13讨论讨论讨论讨论(t(t oln)3oln)3：树的链式存储方案应该怎样制定：树的链式存储方案应该怎样制定：树的链式存储方案应该怎样制定：树的链式存储方案应该怎样制定？可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的

9、结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。可规定为：从上至下、从左至右将树的结点依次存入内存。重重重重大大大大缺缺缺缺陷陷陷陷：复复复复原原原原困困困困难难难难（不不不不能能能能唯唯唯唯一一一一(wi(wi(wi(wi y)y)y)y)复复复复原原原原就就就就没没没没有有有有实实实实用用用用价价价价值值值值）。讨论2：树的顺序存储方案(fng n)应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）；不等长结构太复杂（要定义好多种结构类型

10、）。解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。二叉树二叉树第12页/共81页第十三页，共81页。145.5.树的运算树的运算树的运算树的运算(yn sun)(yn sun)要明确：要明确：要明确：要明确：1.1.普普普普通通通通树树树树（即即即即多多多多叉叉叉叉树树树树）若若若若不不不不转转转转化化化化为为为为二二二二叉叉叉叉树树树树，则则则则运运运运算算算算很很很很难实现。难实现。难实现。难实现。2.2.二二二二叉叉叉叉树树树树的的的的运运运运算算算算仍仍仍仍然然然然是是是是插插插插入入入入、删删删删除除除除、修修修修改改改改、查查查查找找找找、排排排排序序序序等

11、等等等，但但但但这这这这些些些些(zhxi)(zhxi)操操操操作作作作必必必必须须须须建建建建立立立立在在在在对对对对树树树树结结结结点点点点能够能够能够能够“遍历遍历遍历遍历”的基础上！的基础上！的基础上！的基础上！（遍遍遍遍历历历历指指指指每每每每个个个个结结结结点点点点都都都都被被被被访访访访问问问问且且且且仅仅仅仅访访访访问问问问一一一一次次次次，不不不不遗遗遗遗漏不重复）。漏不重复）。漏不重复）。漏不重复）。本章重点：二叉树的表示(biosh)和实现第13页/共81页第十四页，共81页。156.2 6.2 6.2 6.2 二叉树二叉树二叉树二叉树为何要重点研究每结点最多只有两个为何

12、要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个为何要重点研究每结点最多只有两个“叉叉叉叉”的树？的树？的树？的树？二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；二叉树的结构最简单，规律性最强；可可可可以以以以证证证证明明明明，所所所所有有有有(suyu)(suyu)(suyu)(suyu)树树树树都都都都能能能能转转转转为为为为唯唯唯唯一一一一对对对对应应应应的的的的二二二二叉叉叉叉树树树树，不不不不失失失失一一一一般般般般性。性。性。性。1.二叉树的定义(dngy)2.二叉树的性质3.二叉树的存储结构（二叉树的运算(yn sun

13、)见6.3节）第14页/共81页第十五页，共81页。161.1.1.1.二叉树的定义二叉树的定义二叉树的定义二叉树的定义(dngy)(dngy)(dngy)(dngy)定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为(chn wi)左子树和右子树的二叉树组成。逻辑结构：一对二（1：2）基本特征:每个结点最多只有两棵子树（不存在度大于2的结点）；左子树和右子树次序不能颠倒（有序树）。基本形态：问：具有问：具有(jyu)3(jyu)3个结点的二叉树可能有几种不同形态？普个结点的二叉树可能有几种不同形态？普通树呢？通树呢？5种/2种第15页/共81页第十六页，共81页。1

14、7二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义二叉树的抽象数据类型定义(dngy)(dngy)(dngy)(dngy)（见教材（见教材（见教材（见教材P121-122P121-122P121-122P121-122）ADT BinaryTree数据对象(duxing)D:数据关系R:基本操作 P：ADT BinaryTree若D=，则R=；若D，则R=H；存在二元关系：root 唯一(wi y)/关于根的说明 DjDk=/关于子树不相交的说明 /关于数据元素的说明 /关于左子树和右子树的说明D是具有相同特性的数据元素的集合。/至少有20个第16页/共81页第十七页，

15、共81页。182.2.2.2.二叉树的性质二叉树的性质二叉树的性质二叉树的性质(xngzh)(xngzh)(xngzh)(xngzh)(3+2)(3+2)(3+2)(3+2)讨论1：第i层的结点(ji din)数至多是多少？（利用二进制性质可轻松求出）性质1:在二叉树的第i层上至多(zhdu)有2i-1个结点（i0）。性质2:深度为k的二叉树至多有2 2k k-1-1个结点（k0）。2i-1个提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，至多有多少个结点？（利用二进制性质可轻松求出）2k-1提问：深度为k时至少有 个结点？k第17页/共81页第十八页，共81页。19讨论讨论讨论讨论

16、3 3 3 3：二叉树的叶子：二叉树的叶子：二叉树的叶子：二叉树的叶子(y zi)(y zi)(y zi)(y zi)数和度为数和度为数和度为数和度为2 2 2 2的结点数之间有关系的结点数之间有关系的结点数之间有关系的结点数之间有关系吗？吗？吗？吗？性质(xngzh)3:对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21（即n0=n2+1）证明：证明：二二叉叉树树中中全全部部结结点点(ji(ji din)din)数数n nn0+n1+n2(n0+n1+n2(叶叶子子数数1 1度度结结点点(ji din)(ji din)数数2 2度结点度结点(ji din)(ji din

17、)数数)又又二二叉叉树树中中全全部部结结点点(ji(ji din)din)数数n nB+1 B+1(总总分分支支数数根根结结点点(ji din)(ji din)（除除根根结结点点(ji(ji din)din)外外，每每个个结结点点(ji(ji din)din)必必有有一一个个直直接接前前趋，即一个分支）趋，即一个分支）而而 总总分分支支数数B=B=n1+2n2 n1+2n2 (1(1度度结结点点(ji(ji din)din)必必有有1 1个个直直接接后后继继，2 2度度结点结点(ji din)(ji din)必有必有2 2个个)三式联立可得：三式联立可得：n0+n1+n2=n1+2n2+1,n

18、0+n1+n2=n1+2n2+1,即即n0=n2+1n0=n2+1实际意义：叶子数实际意义：叶子数2 2度结点度结点(ji din)(ji din)数数1 1ABCGEIDHFJ第18页/共81页第十九页，共81页。20满二叉树：一棵深度为满二叉树：一棵深度为满二叉树：一棵深度为满二叉树：一棵深度为k k k k 且有且有且有且有2k-12k-12k-12k-1个结点个结点个结点个结点(ji(ji(ji(ji din)din)din)din)的二叉树。的二叉树。的二叉树。的二叉树。（特点：每层都（特点：每层都（特点：每层都（特点：每层都“充满充满充满充满”了结点了结点了结点了结点(ji din

19、)(ji din)(ji din)(ji din)）完全(wnqun)二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树深度为4的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为(yn wi)它们在顺序存储方式下可以复原！完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。这其实是顺序顺序二叉树二叉树的含义。在图论概念图论概念中中的“完全二叉树”是指n1=0的情况。第19页/共81页第二十页，共81页。21对于两种特殊形式的二叉树（满二叉树和完全对于两种特殊形

20、式的二叉树（满二叉树和完全对于两种特殊形式的二叉树（满二叉树和完全对于两种特殊形式的二叉树（满二叉树和完全(wnqun)(wnqun)(wnqun)(wnqun)二叉树），还特别具备以下二叉树），还特别具备以下二叉树），还特别具备以下二叉树），还特别具备以下2 2 2 2个性质：个性质：个性质：个性质：性质4:具有n个结点的完全二叉树的深度必为性质5:对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子(hi zi)编号必为2i，其右孩子(hi zi)编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。证明：当i=1时，由完全二叉树的定义，其左孩子是结点2，右孩子是结

21、点3，成立(chngl)。当i1时，分两种情况，此时只证最简单的一种情况，即设第j层的第一个结点的编号为i，（由性质2知，前j-1层共有2j-1-1个结点，所以第j层的第一个结点的编号为2j-1，即i=2j-1），则其左孩子必为第j+1层上的第一个结点，其编号为2j。(因为第j层上有2j-1个结点)，而2j=2(2j-1)=2i，所以，编号为i的结点的左孩子的编号为2i。证明：根据性质2，深度为k的二叉树最多只有2k-1个结点，且完全二叉树的定义是与同深度的满二叉树前面编号相同，即它的总结点数n位于k层和k-1层满二叉树容量之间，即 2k-1-1n2k-1 或2k-1n2k三边同时取对数，于是

22、有：k-1log2n1)f=n*fact(n-1);else f=1;return(f);第32页/共81页第三十三页，共81页。34先序遍历算法先序遍历算法先序遍历算法先序遍历算法(sun f(sun f)DLR(liuyu*root)DLR(liuyu*root)if(root!=NULL)/if(root!=NULL)/非空二叉树非空二叉树非空二叉树非空二叉树 printf(“%d”,root-data);/printf(“%d”,root-data);/访问访问访问访问DDDLR(root-lchild);DLR(root-lchild);/递递递递归归归归遍遍遍遍历历历历左左左左子树

23、子树子树子树DLR(root-rchild);DLR(root-rchild);/递递递递归归归归遍遍遍遍历历历历右右右右子树子树子树子树 return(0);return(0);中序遍历(bin l)算法LDR(x*root)if(root!=NULL)LDR(root-lchild);printf(“%d”,root-data);LDR(root-rchild);return(0);后序遍历(bin l)算法LRD(x*root)if(root!=NULL)LRD(root-lchild);LRD(root-rchild);printf(“%d”,root-data);return(0);

24、结点数据类型自定义typedef struct liuyuint data;struct liuyu*lchild,*rchild；liuyu;liuyu*root;第33页/共81页第三十四页，共81页。35对遍历对遍历对遍历对遍历(bin l)(bin l)的分析：的分析：的分析：的分析：1.从前面的三种遍历算法可以(ky)知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点(zhngdin)的路径上，每个结点经过3次。AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次

25、经过时访问后序遍历2.二叉树遍历的时间效率和空间效率时间效率:O(n)O(n)/每个结点只访问一次空间效率:O(n)O(n)/栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）第34页/共81页第三十五页，共81页。36例：编写递归算法，计算二叉树中叶子结点例：编写递归算法，计算二叉树中叶子结点例：编写递归算法，计算二叉树中叶子结点例：编写递归算法，计算二叉树中叶子结点(ji di(ji di n)n)的数的数的数的数目。目。目。目。思路：输出叶子结点比较简单，用任何一种遍历(bin l)算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。DLR(liuyu*root

26、)/采用中序遍历的递归算法 if(root!=NULL)/非空二叉树条件(tiojin)，还可写成if(root)if(!root-lchild&!root-rchild)/是叶子结点则统计并打印 sum+;printf(%dn,root-data);DLR(root-lchild);/递归遍历左子树，直到叶子处；DLR(root-rchild);/递归遍历右子树，直到叶子处；return(0);第35页/共81页第三十六页，共81页。37注：要实现遍历运算注：要实现遍历运算注：要实现遍历运算注：要实现遍历运算(yn sun)(yn sun)必须先把二叉树存入必须先把二叉树存入必须先把二叉树存

27、入必须先把二叉树存入机内。机内。机内。机内。思路：利用前序遍历来(lli)建树（结点值陆续从键盘输入，用DLR为宜）Bintree createBTpre()Bintree T;char ch;scanf(“%c”,&ch);if(ch=)T=NULL;elseT=(Bintree)malloc(sizeof(BinTNode);T-data=ch;T-lchild=createBTpre();T-rchild=createBTpre();return T;怎样建树？见教材(jioci)P131程序。第36页/共81页第三十七页，共81页。38习题习题习题习题(xt)(xt)讨论：讨论：讨论：

28、讨论：1.1.求二叉树深度，或从求二叉树深度，或从x x结点开始的子树深度。结点开始的子树深度。算法思路：只查各结点后继链表指针，若左算法思路：只查各结点后继链表指针，若左(右右)孩子的左孩子的左(右右)指针非空，则层次数加指针非空，则层次数加1 1；否则；否则(fuz)(fuz)函数返回。函数返回。左子树右子树根hlhrHeight=max(hr,hr)+1AFEDCBG第37页/共81页第三十八页，共81页。39后序遍历(bin l)求二叉树的高度递归算法：Int PostTreeDepth(BiTree bt)int hl,hr,max;if(bt!=NULL)hl=PostTreeDe

29、pth（bt-Lchild);/求左子树的深度 hr=PostTreeDepth(bt-Rchild);/求右子树的深度 max=hlhr?hl:hr;/*得到左、右子树深度较大者*/return(max+1);/*返回树的深度*/else return 0;第38页/共81页第三十九页，共81页。402.2.按层次输出二叉树中所有结点。按层次输出二叉树中所有结点。算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结算法思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法，而不必拘泥于递归算法。点的指针是个好办法，而不必拘泥于递归算法。技巧：当根结点入队技巧：当根

30、结点入队(r du)(r du)后，令其左、右孩子结点入队后，令其左、右孩子结点入队(r du)(r du)，而，而左孩子出队时又令它的左右孩子结点入队左孩子出队时又令它的左右孩子结点入队(r du)(r du)，由此便可产生由此便可产生按层次输出的效果。按层次输出的效果。ADFCGEHBVoid Layout(BiTree root)EnQueue(s,root);While(!QueueEmpty(s)DeQueue(s,p);printf(“%c”,root-data);EnQueue(s,p-lchild);EnQueue(s,p-rchild);第39页/共81页第四十页，共81页。

31、41遍历的非递归遍历的非递归遍历的非递归遍历的非递归(迭代迭代迭代迭代(di di)(di di)(di di)(di di)算法算法算法算法以中序遍历以中序遍历以中序遍历以中序遍历算法思路：若不用递归，则要实现(shxin)二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。在中序遍历中，我们是通过顺着左子树的根直走到最左端，然后访问最左端元素，遍历右，再返回上一层，访问结点，遍历右，然后再访问上一层，这样又顺着左子树的根回到A。在递归调用中，返回上一层的操作是通过调用函数执行结束自然返回上一层的。如果不用递归，如何返回上一层。先从

32、A走到F，在从F返回到A，最后走到的先访问，所以可以用栈。把根和左子树的根全部(qunb)入栈然后判断是否有右子树，如果有，则遍历右子树，HIAFEDCBG第40页/共81页第四十一页，共81页。42特别讨论：若已知先序特别讨论：若已知先序特别讨论：若已知先序特别讨论：若已知先序/后序遍历结果后序遍历结果后序遍历结果后序遍历结果(ji gu(ji gu)和中序遍历结果和中序遍历结果和中序遍历结果和中序遍历结果(ji gu(ji gu)，能否，能否，能否，能否“恢复恢复恢复恢复”出二叉出二叉出二叉出二叉树？树？树？树？证明：由一棵二叉树的先序序列和中序序列可唯一证明：由一棵二叉树的先序序列和中序

33、序列可唯一证明：由一棵二叉树的先序序列和中序序列可唯一证明：由一棵二叉树的先序序列和中序序列可唯一(wi y)(wi y)确定确定确定确定这棵二叉树。这棵二叉树。这棵二叉树。这棵二叉树。例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部(wi b)（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必全部是右子树子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。第41页/共81页第四十二页，共

34、81页。43中序遍历中序遍历中序遍历中序遍历(bin l)(bin l)：B D C E A F H GB D C E A F H G后序遍历后序遍历后序遍历后序遍历(bin l)(bin l)：D E C B H G F AD E C B H G F A（B D C E）（F H G）ABF （D C E）（H G）CD EGHABBFF第42页/共81页第四十三页，共81页。446.4 6.4 树和森林树和森林(snln)(snln)1.树和森林与二叉树的转换(zhunhun)2.树和森林的存储方式3.树和森林的遍历第43页/共81页第四十四页，共81页。4512345879618第44页

35、/共81页第四十五页，共81页。46 利用除根结点外每个结点只有(zhyu)唯一的双亲的性质，以一组连续的空间存储树的结点，同时在每个结点中附设一个指示域指示其双亲结点在存储空间中的位置。6.4 树的存储(cn ch)结构一、双亲表示法#define MAX_TREE_SIZE 100结点(ji din)结构：Typedef struct PTNode Elem data;int parent;PTNode;Data parentTypedef struct PTNode nodesMAX_TRee_size;int r,n;第45页/共81页第四十六页，共81页。476.4 6.4 树的存储

36、树的存储树的存储树的存储(cn ch(cn ch)结构结构结构结构EDABRCFGHk6H6G3F1E1D0C0B0A-1RK60123456789R=0N=10第46页/共81页第四十七页，共81页。48特点：1）求结点的双亲(shungqn)操作可以在常量时间内实现；2）求结点的孩子时需要遍历整个向量。第47页/共81页第四十八页，共81页。49二、孩子(hi zi)表示法孩子(hi zi)结点：Typedef struct CTNode int child;struct CTNode*next;*childPtr;双亲(shungqn)结点:Typedef struct Elem dat

37、a;childPtr firstchild;CTBox;第48页/共81页第四十九页，共81页。50树结构：Typedef struct CTBox nodesMAX_TREE_SIZE;int n,r;Ctree;第49页/共81页第五十页，共81页。51FEBCADGR=0N=70123456ABCDEFG123456 -1000225 第50页/共81页第五十一页，共81页。52三、树的二叉链表 （孩子-兄弟(xingd)）存储表示法 typedef struct CSNode Elem data;struct CSNode *firstchild,*nextsibling;CSNode

38、,*CSTree;第51页/共81页第五十二页，共81页。53FEBCADGABCEDFG ABCEDFG第52页/共81页第五十三页，共81页。541.1.树和森林树和森林树和森林树和森林(snln)(snln)与二叉树的转换与二叉树的转换与二叉树的转换与二叉树的转换转换步骤：step1:将树中同一结点(ji din)的兄弟相连;step2:保留结点(ji din)的最左孩子连线，删除其它孩子连线；step3:将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转(xunzhun)讨论1：树如何转为二叉树？第53页/共81页第五十四页，共81页。55方法(fngf)：加线抹线旋转 abeidfh

39、gc树转二叉树举例树转二叉树举例树转二叉树举例树转二叉树举例(j(j(j(j l)l)l)l)：abeidfhgc兄弟(xingd)相连长兄为父孩子靠左根结点肯定没根结点肯定没有右孩子！有右孩子！第54页/共81页第五十五页，共81页。56讨论讨论讨论讨论2 2 2 2：二叉树怎样：二叉树怎样：二叉树怎样：二叉树怎样(znyng)(znyng)(znyng)(znyng)还原为树还原为树还原为树还原为树？abeidfhgc要点：把所有(suyu)右孩子变为兄弟！abeidfhgc第55页/共81页第五十六页，共81页。57法一：各森林(snln)先各自转为二叉树；依次连到前一个二叉树的右子树上

40、。讨论3：森林(snln)如何转为二叉树？法二：森林(snln)直接变兄弟，再转为二叉树（参见教材P138图6.17，两种方法都有转换示意图）即F=T1,T2,Tm B=root,LB,RB第56页/共81页第五十七页，共81页。58ABCDEFGHJIABCDEFGHJIAABCDEFGHJI森林森林森林森林(snln)(snln)(snln)(snln)转二叉树举例：（法二）转二叉树举例：（法二）转二叉树举例：（法二）转二叉树举例：（法二）兄弟相连(xin lin)长兄为父孩子靠左 头根为根 A A第57页/共81页第五十八页，共81页。59讨论讨论讨论讨论4 4 4 4：二叉树如何：二叉

41、树如何：二叉树如何：二叉树如何(rh)(rh)(rh)(rh)还原为森还原为森还原为森还原为森林？林？林？林？要点：把最右边的子树变为森林(snln)，其余右子树变为兄弟 ABCDEFGHJIABCDEFGHJIEFABCDGHJI即B=root,LB,RB F=T1,T2,Tm第58页/共81页第五十九页，共81页。60树的遍历可有三条搜索(su su)路径：先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。第59页/共81页第六十页，共81页

42、。61CFEBADGHIJK先根遍历时(l sh)顶点的访问次序：A B E F C D G H I J K后根遍历时(l sh)顶点的访问次序：E F B C I J K H G D A层序遍历时(l sh)顶点的访问次序：A B C D E F G H I J K第60页/共81页第六十一页，共81页。62先序遍历若森林(snln)为空，返回；访问森林(snln)中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林(snln)；先序遍历除去第一棵树之后剩余的树构成的森林(snln)。中序遍历若森林(snln)为空，返回；中序遍历森林(snln)中第一棵树的根结点的子树森林(snln)；访

43、问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林(snln)。森林森林森林森林(snln)(snln)(snln)(snln)的遍历的遍历的遍历的遍历ABCDEFGHJI第61页/共81页第六十二页，共81页。63ABCDEFGHKIABCDEFGLJ第62页/共81页第六十三页，共81页。64路 径：路径(ljng)长度：树的路径(ljng)长度：带权路径(ljng)长度：树的带权路径(ljng)长度：霍 夫 曼 树：6.5 Huffman6.5 Huffman6.5 Huffman6.5 Huffman树及其应用树及其应用树及其应用树及其应用(yngyng)(yngyng)(

44、yngyng)(yngyng)一、最优二叉树（霍夫曼树）由一结点到另一结点间的分支(fnzh)所构成路径上的分支数目从树根到每一结点的路径长度之和。结点到根的路径长度与结点上权的乘积预备知识：若干术语debacf g树中所有叶子结点的带权路径长度之和带权路径长度最小的树。ae的路径长度树长度210第63页/共81页第六十四页，共81页。65HuffmanHuffmanHuffmanHuffman树简介树简介树简介树简介(jin ji)(jin ji)(jin ji)(jin ji)：树的带权路径(ljng)长度如何计算？WPL=wklk k=1nabdc7524(a)cdab2457(b)bd

45、ac7524(c)经典经典(jngdin)(jngdin)之例：之例：WPL=36WPL=46WPL=35哈夫曼树则是：WPL 最小的树。Huffman树Weighted Path Length第64页/共81页第六十五页，共81页。66(1)(1)由给定的由给定的 n n 个权值个权值w0,w1,w2,wn-1w0,w1,w2,wn-1，构造具有，构造具有(jyu)(jyu)n n 棵扩充二叉树的森林棵扩充二叉树的森林F=T0,T1,T2,Tn-1 F=T0,T1,T2,Tn-1，其中每一棵，其中每一棵扩充二叉树扩充二叉树 Ti Ti 只有一个带有权值只有一个带有权值 wi wi 的根结点，

46、其左、右子树均的根结点，其左、右子树均为空。为空。(2)(2)重复以下步骤重复以下步骤,直到直到 F F 中仅剩下一棵树为止：中仅剩下一棵树为止：在在 F F 中选取两棵根结点的权值最小的扩充二叉树中选取两棵根结点的权值最小的扩充二叉树,做为左、做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。其左、右子树上根结点的权值之和。在在 F F 中删去这两棵二叉树。中删去这两棵二叉树。把新的二叉树加入把新的二叉树加入 F F。构造霍夫曼树的基本构造霍夫曼树的基本构造霍夫曼树的基本构造霍夫曼树的基本(jb

47、n)(jbn)(jbn)(jbn)思想：思想：思想：思想：构造(guzo)Huffman树的步骤（即Huffman算法）：权值大的结点用短路径，权值小的结点用长路径权值大的结点用短路径，权值小的结点用长路径。先举例！第65页/共81页第六十六页，共81页。67操作要点：对权值的合并、删除与替换(t hun)在权值集合7,5,2,4中，总是合并当前值最小的两个权构造构造构造构造(guzo)Huffman(guzo)Huffman(guzo)Huffman(guzo)Huffman树的步树的步树的步树的步骤：骤：骤：骤：注：方框表示外结点(ji din)（叶子，字符对应的权值），圆框表示内结点(j

48、i din)（合并后的权值）。赫夫曼编码第66页/共81页第六十七页，共81页。68例例2 2：设有：设有4 4个字符个字符d,i,a,nd,i,a,n，出现的频度分别，出现的频度分别(fnbi)(fnbi)为为7,5,2,47,5,2,4，怎样编码才能使它们组成的报文在网络中传得，怎样编码才能使它们组成的报文在网络中传得最快？最快？法1：等长编码(bin m)。例如用二进制编码(bin m)来实现。取 d=00，i=01，a=10，n=11法2：不等长编码(bin m)，例如用前缀编码(bin m)来实现。取 d=0;i=10,a=110,n=111adin000111用二叉树来设计前缀编码

49、最快的编码是哪个？是非等长的前缀编码！任一个字符的编码都不是另一个字符编码的前缀约定：左分支表示0右分支表示1则从根结点到叶子结点的路径上分支字符组成的字符串作为该叶子的编码。第67页/共81页第六十八页，共81页。69ACBDEKFGHIJ第68页/共81页第六十九页，共81页。70如何得到电文长度(chngd)最短的二进制前缀编码？若按各个字符出现的概率不同(b tn)而给予不等长编码，可望减少总编码长度。d,i,a,n，出现(chxin)的频度分别为7,5,2,4 假设每种字符在电文中出现的次数为wi,，其编码长度为Li,电文中只有n种字符，则电文总长度为=niiLiW1=niiLiW1

50、 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。对应到二叉树上，若置wi为叶子结点的权，Li恰为从根到叶子的路径长度。则：恰为二叉树上带权路径长度。第69页/共81页第七十页，共81页。71操作要点：按左操作要点：按左操作要点：按左操作要点：按左0 0 0 0右右右右1 1 1 1对对对对HuffmanHuffmanHuffmanHuffman树的所有分支树的所有分支树的所有分支树的所有分支(fnzh)(fnzh)(fnzh)(fnzh)编号！编号！编号！编号！dain111000Huffman编码(b