数据结构第六章学习教案

1、会计学1数据结构数据结构(sh j ji u)课件第六章课件第六章第一页，共81页。26.1 树的基本概念6.2 二叉树6.3 遍历二叉树和线索(xin su)二叉树6.4 树和森林6.5 赫夫曼树及其应用特点：非线性结构，一个直接(zhji)前驱，但可能有多个直接(zhji)后继（1：n）第1页/共81页第二页，共81页。31. 树的定义2 若干术语3. 逻辑结构4.存储(cn ch)结构5. 树的运算第2页/共81页第三页，共81页。4注1：过去(guq)许多书籍中都定义树为n1，曾经有“空树不是树”的说法，但现在树的定义已修改。注2：树的定义具有递归性，即树中还有树。由一个或多个(n0)

2、结点组成的有限集合T，有且仅有一个结点称为(chn wi)根（root），当n1时，其余的结点分为m(m0)个互不相交的有限集合T1,T2，Tm。每个集合本身又是棵树，被称作这个根的子树 。第3页/共81页第四页，共81页。5图形表示法嵌套集合表示法广义表表示法目录(ml)表示法左孩子右兄弟表示法这些表示法的示意图参见(cnjin)教材P120树的抽象数据类型定义参见教材P118-119第4页/共81页第五页，共81页。6教师学生其他人员2003级 2004级 2005级2006级河南大学物理系计算机系化学系叶子(y zi)根子树第5页/共81页第六页，共81页。7( A ( B ( E (

3、K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) 根作为由子树森林组成(z chn)的表的名字写在表的左边datalink 1 link 2.link n麻烦问题：应当(yngdng)开设多少个链域?第6页/共81页第七页，共81页。8数据左孩子 右兄弟( A ( B ( E ( K, L ), F ), C ( G ), D ( H ( M ), I, J ) ) )第7页/共81页第八页，共81页。9（见教材(jioci)P118-119）ADT Tree数据对象(duxing)D:数据关系R:基本操作 P：ADT Tree若D为空集，则称为空树；/允

4、许n=0若D中仅含一个数据元素，则R为空集；其他情况下的R存在二元关系： root 唯一 /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明D是具有相同特性的数据元素的集合。/至少有15个第8页/共81页第九页，共81页。10即上层的那个结点(直接前驱)即下层结点的子树的根(直接后继)同一双亲下的同层结点（孩子之间互称兄弟）即双亲位于同一层的结点（但并非同一双亲）即从根到该结点所经分支(fnzh)的所有结点即该结点下层子树中的任一结点ABCGEIDHFJMLK 根 叶子(y zi) 森林有序树无序树即根结点(没有前驱)即终端结点(没有后继)指m棵不相交的树的集合(例如删除

5、A后的子树个数)双亲孩子兄弟堂兄弟祖先子孙结点各子树从左至右有序，不能互换（左为第一）结点各子树可互换位置。第9页/共81页第十页，共81页。11即树的数据元素结点挂接的子树数（有几个直接后继就是(jish)几度，亦称“次数”）结点(ji din)结点(ji din)的度结点(ji din)的层次终端结点(ji din)分支结点(ji din)树的度树的深度(或高度)ABCGEIDHFJMLK从根到该结点的层数（根结点算第一层）即度为0的结点，即叶子即度不为0的结点（也称为内部结点）所有结点度中的最大值（Max各结点的度）指所有结点中最大的层数（Max各结点的层次）问：右上图中的结点数 ；树的

6、度 ；树的深度1334第10页/共81页第十一页，共81页。124. 树的存储(cn ch)结构 讨论1：树是非线性结构，该怎样存储？仍然有顺序存储、链式存储等方式。 第11页/共81页第十二页，共81页。13讨论2：树的顺序存储方案(fng n)应该怎样制定？可用多重链表：一个前趋指针，n个后继指针。细节问题：树中结点的结构类型样式该如何设计？ 即应该设计成“等长”还是“不等长”？缺点：等长结构太浪费（每个结点的度不一定相同）； 不等长结构太复杂（要定义好多种结构类型）。解决思路：先研究最简单、最有规律的树，然后设法把一般的树转化为简单树。第12页/共81页第十三页，共81页。14本章重点：

7、二叉树的表示(biosh)和实现第13页/共81页第十四页，共81页。151. 二叉树的定义(dngy)2. 二叉树的性质3. 二叉树的存储结构（二叉树的运算(yn sun)见6.3节）第14页/共81页第十五页，共81页。16定义：是n（n0）个结点的有限集合，由一个根结点以及两棵互不相交的、分别称为(chn wi)左子树和右子树的二叉树组成 。逻辑结构： 一对二（1：2） 基本特征: 每个结点最多只有两棵子树（不存在度大于2的结点）； 左子树和右子树次序不能颠倒（有序树）。基本形态： 5种/2种第15页/共81页第十六页，共81页。17ADT BinaryTree数据对象(duxing)D

8、:数据关系R:基本操作 P：ADT BinaryTree若D=，则R= ；若D，则R= H；存在二元关系： root 唯一(wi y) /关于根的说明 DjDk= /关于子树不相交的说明 /关于数据元素的说明 /关于左子树和右子树的说明D是具有相同特性的数据元素的集合。/至少有20个第16页/共81页第十七页，共81页。18讨论1：第i层的结点(ji din)数至多是多少？ （利用二进制性质可轻松求出） 性质1: 在二叉树的第i层上至多(zhdu)有2i-1个结点（i0）。性质2: 深度为k的二叉树至多有个结点（k0）。2i-1个提问：第i层上至少有 个结点？1讨论2：深度为k的二叉树，至多有

9、多少个结点？ （利用二进制性质可轻松求出）2k-1提问：深度为k时至少有 个结点？k第17页/共81页第十八页，共81页。19性质(xngzh)3: 对于任何一棵二叉树，若2度的结点数有n2个，则叶子数（n0）必定为n21 （即n0=n2+1）ABCGEIDHFJ第18页/共81页第十九页，共81页。20完全(wnqun)二叉树：深度为k 的，有n个结点的二叉树，当且仅当其每一个结点都与深度为k 的满二叉树中编号从1至n的结点一一对应。AOBCGEKDJFIHNML深度为4的满二叉树深度为4的完全二叉树ABCGEIDHFJ为何要研究这两种特殊形式？因为(yn wi)它们在顺序存储方式下可以复原

10、！ 完全二叉树的特点就是，只有最后一层叶子不满，且全部集中在左边。 这其实是的含义。在的“完全二叉树”是指n1=0的情况。第19页/共81页第二十页，共81页。212log1n 性质4: 具有n个结点的完全二叉树的深度必为性质5: 对完全二叉树，若从上至下、从左至右编号，则编号为i 的结点，其左孩子(hi zi)编号必为2i，其右孩子(hi zi)编号必为2i1；其双亲的编号必为i/2（i1 时为根,除外）。 证明：当i=1时，由完全二叉树的定义，其左孩子是结点2，右孩子是结点3，成立(chngl)。当i1时，分两种情况，此时只证最简单的一种情况，即设第j层的第一个结点的编号为i，（由性质2知

11、，前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三边同时取对数，于是有：k-1log2n1)f=n*fact(n-1); else f=1; return(f); 第32页/共81页第三

12、十三页，共81页。34中序遍历(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);结点数据类型自定义typedef struct liuyuint data; struct liuyu *lchild,*rchild；

13、 liuyu;liuyu *root; 第33页/共81页第三十四页，共81页。351. 从前面的三种遍历算法可以(ky)知道：如果将print语句抹去，从递归的角度看，这三种算法是完全相同的，或者说这三种遍历算法的访问路径是相同的，只是访问结点的时机不同。从虚线的出发点到终点(zhngdin)的路径上，每个结点经过3次。AFEDCBG第1次经过时访问先序遍历第2次经过时访问中序遍历第3次经过时访问后序遍历2. 二叉树遍历的时间效率和空间效率时间效率: /每个结点只访问一次空间效率: /栈占用的最大辅助空间（精确值：树深为k的递归遍历需要k+1个辅助单元！）第34页/共81页第三十五页，共81

14、页。36思路：输出叶子结点比较简单，用任何一种遍历(bin l)算法，凡是左右指针均空者，则为叶子，将其统计并打印出来。 DLR(liuyu *root) /采用中序遍历的递归算法 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页/共

15、81页第三十六页，共81页。37思路：利用前序遍历来(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左子树右子树根hlhrHeight=m

16、ax(hr,hr)+1AFEDCBG第37页/共81页第三十八页，共81页。39后序遍历(bin l)求二叉树的高度递归算法：Int PostTreeDepth(BiTree bt) int hl,hr,max; if(bt!=NULL) hl=PostTreeDepth（bt-Lchild); /求左子树的深度 hr=PostTreeDepth(bt-Rchild); /求右子树的深度 max=hlhr?hl:hr; /*得到左、右子树深度较大者*/ return (max+1); /*返回树的深度*/ else return 0;第38页/共81页第三十九页，共81页。40ADFCGEHB

17、Void 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页。41算法思路：若不用递归，则要实现(shxin)二叉树遍历的“嵌套”规则，必用堆栈。可直接用while语句和push/pop操作。参见教材P130-131程序。在中序遍历中，我们是通过顺着左子树的根直走到最左端，然后访问最左端元素，遍历右，再返回上一层，访问结点，遍历右，然后

18、再访问上一层，这样又顺着左子树的根回到A。在递归调用中，返回上一层的操作是通过调用函数执行结束自然返回上一层的。如果不用递归，如何返回上一层。先从A走到F，在从F返回到A，最后走到的先访问，所以可以用栈。把根和左子树的根全部(qunb)入栈然后判断是否有右子树，如果有，则遍历右子树，HIAFEDCBG第40页/共81页第四十一页，共81页。42例：已知一棵二叉树的中序序列和后序序列分别是BDCEAFHG 和 DECBHGFA，请画出这棵二叉树。分析：由后序遍历特征，根结点必在后序序列尾部(wi b)（即A）；由中序遍历特征，根结点必在其中间，而且其左部必全部是左子树子孙（即BDCE），其右部必

19、全部是右子树子孙（即FHG）；继而，根据后序中的DECB子树可确定B为A的左孩子，根据HGF子串可确定F为A的右孩子；以此类推。第41页/共81页第四十二页，共81页。43（B D C E）（ F H G）ABF （D C E） （ H G）CD EGHABBFF第42页/共81页第四十三页，共81页。441. 树和森林与二叉树的转换(zhunhun)2. 树和森林的存储方式3. 树和森林的遍历第43页/共81页第四十四页，共81页。4512345879618第44页/共81页第四十五页，共81页。46 利用除根结点外每个结点只有(zhyu)唯一的双亲的性质，以一组连续的空间存储树的结点，同时

20、在每个结点中附设一个指示域指示其双亲结点在存储空间中的位置。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页。47EDABRCFGHk6H6G3F1E1D0C0B0A-1RK60123456789R=0N=10第46页/共81页第四十七页，共81页。48特点：

21、1）求结点的双亲(shungqn)操作可以在常量时间内实现；2）求结点的孩子时需要遍历整个向量。第47页/共81页第四十八页，共81页。49二、孩子(hi zi)表示法孩子(hi zi)结点： Typedef struct CTNode int child; struct CTNode *next; *childPtr;双亲(shungqn)结点: Typedef struct Elem data; childPtr firstchild; CTBox;第48页/共81页第四十九页，共81页。50树结构： Typedef struct CTBox nodesMAX_TREE_SIZE; int

22、 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,*CSTree;第51页/共81页第五十二页，共81页。53FEBCADGABCEDFGABCEDFG第52页/共81页第五十三页，共81页。54转换步骤：step1: 将树中同一结点(j

23、i din)的兄弟相连;step2: 保留结点(ji din)的最左孩子连线，删除其它孩子连线；step3: 将同一孩子的连线绕左孩子旋转45度角。加线抹线旋转(xunzhun)讨论1：树如何转为二叉树？第53页/共81页第五十四页，共81页。55方法(fngf)：加线抹线旋转 abeidfhgcabeidfhgc兄弟(xingd)相连长兄为父孩子靠左第54页/共81页第五十五页，共81页。56abeidfhgc要点：把所有(suyu)右孩子变为兄弟！ abeidfhgc第55页/共81页第五十六页，共81页。57法一： 各森林(snln)先各自转为二叉树； 依次连到前一个二叉树的右子树上。讨

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

25、十九页，共81页。60树的遍历可有三条搜索(su su)路径：先根序（次序）遍历 若树不空，则先访问根结点，然后依次先根遍历各棵子树。后根（次序）遍历 若树不空，则先依次后根遍历各棵子树，然后访问根结点。按层次遍历 若树不空，则自上而下自左至右访问树中每个结点。第59页/共81页第六十页，共81页。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页第六十一页，共8

26、1页。62先序遍历若森林(snln)为空，返回；访问森林(snln)中第一棵树的根结点；先序遍历第一棵树中根结点的子树森林(snln)；先序遍历除去第一棵树之后剩余的树构成的森林(snln)。中序遍历若森林(snln)为空，返回；中序遍历森林(snln)中第一棵树的根结点的子树森林(snln)；访问第一棵树的根结点；中序遍历除去第一棵树之后剩余的树构成的森林(snln)。ABCDEFGHJI第61页/共81页第六十二页，共81页。63ABCDEFGHKIABCDEFGLJ第62页/共81页第六十三页，共81页。64路 径：路径(ljng)长度：树的路径(ljng)长度：带权路径(ljng)长度

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

28、ath Length第64页/共81页第六十五页，共81页。66构造(guzo)Huffman树的步骤（即Huffman算法）：第65页/共81页第六十六页，共81页。67操作要点：对权值的合并、删除与替换(t hun)在权值集合7,5,2,4中，总是合并当前值最小的两个权注：方框表示外结点(ji din)（叶子，字符对应的权值）， 圆框表示内结点(ji din)（合并后的权值）。赫夫曼编码第66页/共81页第六十七页，共81页。68法1：等长编码(bin m)。例如用二进制编码(bin m)来实现。 取 d=00，i=01，a=10，n=11法2：不等长编码(bin m)，例如用前缀编码(b

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

30、符在电文中出现的次数为wi,，其编码长度为Li,电文中只有n种字符，则电文总长度为=niiLiW1=niiLiW1 由此可见，设计电文总长最短的二进制前缀编码即为以n种字符出现的频率作权，设计一颗赫夫曼树的问题，由此得到的二进制前缀编码便称为赫夫曼编码。 对应到二叉树上，若置wi为叶子结点的权， Li恰为从根到叶子的路径长度。则： 恰为二叉树上带权路径长度。第69页/共81页第七十页，共81页。71dain111000Huffman编码(bin m)结果：d=0, i=10, a=110, n=111WPL=1bit72bit5+3bit(2+4)=35特点：每一码都不是另一码的前缀(qinz

31、hu)，绝不会错译! 称为前缀(qinzhu)码Huffman树 与 Huffman编码 挂钩第70页/共81页第七十一页，共81页。72霍夫曼编码的基本思想是：概率大的字符用短码，概率小的用长码。由于霍夫曼树的WPL最小，说明编码所需要(xyo)的比特数最少。这种编码已广泛应用于网络通信中。解：先将概率放大100倍，以方便构造哈夫曼树。权值集合 w=7, 19, 2, 6, 32, 3, 21, 10，按哈夫曼树构造规则（合并(hbng)、删除、替换），可得到哈夫曼树。第71页/共81页第七十二页，共81页。73w4=19, 21, 28, 322356w1=5, 6, 7, 10, 19,

32、 21, 32w2=7, 10, 11, 19, 21, 32w3=11, 17, 19, 21, 32111071728211940w5=28,32,403260w6=40,60w7=100100bcadegfh哈夫曼树第72页/共81页第七十三页，共81页。7423561110732172821194060100bcadegfh00000111111100符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10符符编码编码频率频率a0.07b0.19c0.02d0.06e0.32f0.03g0.21h0.10Huffman码的WPL2(0.19+

33、0.32+0.21) + 4(0.07+0.06+0.10) +5(0.02+0.03) =1.44+0.92+0.25=2.61 000001010011100101110111第73页/共81页第七十四页，共81页。75另一种(y zhn)结果表示：第74页/共81页第七十五页，共81页。76Void HuffmanCoding(HuffmanTree &HT,HuffmanCode &HC,int *w,int n)if(n=1) return;n个权值构造一颗赫夫曼树需要(xyo)的结点个数是：2n-1这 2n-1 个结点的存储(cn ch)方式：链式，顺序(shnx)AWPLR1234