数据结构第6章_树PPT课件

1、2021-11-1316.1 6.1 树的概念 树的定义(递归定义)：树（Tree）是n（n0）个结点的有限集合T，满足两个条件：（1）有且仅有一个特定的称为根（Root）的结点，它没有前趋；（2）其余的结点可分成m个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为根的子树。当n=0时的空集合定义为空树。第1页/共85页2021-11-132使用圆圈表示结点，连线表示结点之间的关系，结点的名字可写在圆圈内或圆圈旁。学校一系二系十系一室八室一室七室n树的直观表示法第2页/共85页2021-11-133n树的基本术语l 结点：指树中的一个元素，包含数据项及若干指向其子树的分支。l

2、 结点的度：指结点拥有的子树个数。l 树的度：指树中结点的度的最大值。第3页/共85页2021-11-134l 叶子：指度为零的结点，又称为终端结点。l 孩子：一个结点的子树的根称为该结点的孩子。l 双亲：一个结点的直接上层结点称为该结点的双亲。l 兄弟：同一双亲的孩子互称为兄弟。l 结点的层次：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的孩子为第三层，依次类推。l 树的深度：树中结点的最大层次数。l 堂兄弟：双亲在同一层上的结点互称为堂兄弟。第4页/共85页2021-11-135l 路径：若存在一个结点序列k1,k2,kj, 可使k1到达kj, 则称这个结点序列是k1到达kj的

3、一条路径。l 子孙和祖先：若存在k1到kj的一条路径k1,k2,kj，则k1,kj-1为kj的祖先，而k2,kj为k1的子孙。l 森林：m(m0)棵互不相交的树的集合构成森林。l 有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。第5页/共85页2021-11-136顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存由于树的分支数不固定，很难给出一种固定的存储结构，

4、通常采用二叉树的形式存储树。储结构，通常采用二叉树的形式存储树。树的存储结构第6页/共85页2021-11-1376.2 6.2 二叉树 定义（二叉树的递归定义）：二叉树是n（n0）个结点的有限集，它或为空树（n=0），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。 二叉树的五种基本形态： 二叉树与度为2的树的区别：二叉树的子树有左右之分，而树的子树不分左右；第7页/共85页2021-11-138u满二叉树和完全二叉树l 一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。l 如果一个深度为k的二叉树，它

5、的结点按照从根结点开始，自上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。完全二叉树的1k-1层上共有2k-1-1个结点，第k层的结点集中在左边。l 满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。 1 3 7 5 6 4 2 k=3 的满二叉树 1 3 5 6 4 2 完全二叉树 1 3 6 5 4 2 非完全二叉树 第8页/共85页2021-11-139二叉树的性质-1 性质1：在二叉树的第i层上至多有2i-1个结点(i1)。 证明：可用数学归纳法予以证明。当i=1时，有2i-1=20=1，同时第一层上只有一个根结点，故命题成立

6、。设当i=k时成立，即第k层上至多有2k-1个结点。当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层上至多有22k-1=2k个结点，故命题成立。第9页/共85页2021-11-1310二叉树的性质-2 性质2：深度为k的二叉树至多有2k-1个结点(k1)。 证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为故命题成立。k1ik1- i1-22第10页/共85页2021-11-1311二叉树的性质-3 性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 证明：设度为1的结点数为n1，则一棵二叉树的结点总数为

7、： n=n0+n1+n2 因为除根结点外，其余结点都有一个进入的分支(边)，设B为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有 B=2n2+n1，即 n=2n2+n1+1 比较两式可得n0=n2+1，证毕。第11页/共85页2021-11-1312二叉树的性质-4 性质4：具有n个结点的完全二叉树的深度为log2n+1或log2(n+1)。 (其中x表示不大于x的最大整数，x表示不小于x的最小整数。) 证明：设完全二叉树的深度为k，则有 2k-1 - 1 n 2k 1 (1) (1)式变形为 2k-1 n+1 2k，两边取对数 k-1log2（n1） k 取整得 klo

8、g2(n+1) 2k-1 n 2k （第k层至少有一个结点） （2） 两边取对数 k-1 log2n 1, 则 i 的双亲为i /2若2*i n, 则 i 的左孩子为2*i，否则无左孩子若2*i+1 n, 则 i 的右孩子为2*i+1，否则无右孩子若i为偶数, 且i != n, 则其右兄弟为i+1若i为奇数, 且i != 1, 则其左兄弟为i-1结点i 所在层次为 log2i +1第13页/共85页2021-11-13146.3 6.3 二叉树的存储结构6.3.1 顺序存储结构 完全二叉树 根据二叉树性质5，在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对结点进行顺序编号，便可得

9、到一个反映结点之间关系的线性序列。 下图的完全二叉树的顺序存储结构如下表： 左左图图的的完完全全二二叉叉树树的的顺顺序序存存储储 数组 下标 0 1 2 3 4 5 6 7 8 9 10 结点值 A B C D E F G H I J 1 5 4 2 9 8 10 A D B J I H E 3 7 6 C G F 完完全全二二叉叉树树的的结结点点编编号号 第14页/共85页2021-11-1315一般二叉树将二叉树映射为完全二叉树（通过虚结点）用完全二叉树的方式存储。根据性质2，采用顺序存储结构存储一棵深度为k的完全二叉树或一般二叉树，向量的长度是2k-1。第15页/共85页2021-11-

10、1316由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。存储上述单支二叉树，所需的向量长度为25-1=31第16页/共85页2021-11-13176.3.2 链式存储结构二叉树的链式存储结构每个结点含有数据域和两个指针域，左、右指针域分别用来指向左孩子和右孩子。二叉树的链式存储结构也称为二叉链表。二叉链表结点的C语言逻辑描述为：typedef int datatype；typedef struct node datatype data； struct node *lchild，*rchild；bitree；bitree *root;注：其中root是

11、指向根结点的指针，当二叉树为空时，则root=NULL。若结点的某个孩子不存在时，则相应的指针域为空。第17页/共85页2021-11-1318三叉链表为了能够寻找双亲结点，在结点中增加一个指向双亲结点的指针域parent。 A D B C (a) 二叉树 A ? ? B ? C ? D A ? B ? C ? D ? (b)二叉链表 (c)三叉链表 ? ? ? 第18页/共85页2021-11-13196.3.3 二叉树建立（二叉链表的建立）第19页/共85页2021-11-13206.3.3 6.3.3 二叉树建立（二叉链表的建立）u二叉树的建立 指在内存中如何建立二叉树的存储结构。u基本

12、思想 对顺序存储结构而言，只需将二叉树各个结点的值按原有的逻辑关系送入相应的向量单元中。对链式存储结构而言，其建立算法有多种，它们依赖于按照何种形式来输入二叉树的逻辑结构信息。常用的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，则必须通过先添加若干个虚结点使其成为完全二叉树。第20页/共85页2021-11-1321u 基本步骤问题：如何将新结点正确地链接到它的双亲结点上？第21页/共85页2021-11-1322 算法具体实现依据先建立的结点，其孩子结点也一定先建立的特点先建立的结点，其孩子结点也一定先建立的特点，所以可以第22页/共85页2021-11-1

13、323二叉树的建立算法bitree *CREATREE( ) /* 建立二叉树函数，函数返回指向根结点的指针 */char ch； /* 结点信息变量 */ bitree *Q maxsize； /* 设置指针类型数组来构成队列 * intfront, rear； /* 队头和队尾指针变量 */ bitree *root, *s； /* 根结点指针和中间指针变量 */ root=NULL； /* 二叉树置空 */ front=1; rear=0; /* 设置队列指针变量初值 */*以上为初始化*/第23页/共85页2021-11-1324while(ch=getchar()!=#) /* 输入

14、一个字符，当不是结束符时执行以下操作 */ s=NULL; if(ch!=) /* 表示虚结点，当不是虚结点则建立新结点 */ s=malloc(sizeof (bitree); sdata=ch; slchild=NULL; srchild=NULL; rear+; /* 队尾指针增1，指向新结点地址应存放的单元 */ Qrear=s; /* 将新结点地址入队或虚结点指针NULL入队 */ if (rear= =1) root=s; /* 输入的第一个结点作为根结点 */ else if (s & Qfront) /* 孩子和双亲结点都不是虚结点 */ if (rear % 2= =

15、0) Qfrontlchild=s;/*rear为偶数，新结点是左孩子*/ else Qfrontrchild=s; /* rear为奇数且不等于1，新结点是右孩子 */ if (rear % 2= =1) front+; /* 结点* Qfront的两个孩子处理完毕，出队列 */ return root; /* 返回根指针 */ /* CREATREE */第24页/共85页2021-11-13256.4 6.4 二叉树的遍历 所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。 遍历的结果：产生一个关于结点的线性序列。6.4.1 深度优先递归遍历 访问根结点记作

16、D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有： 先序 DLR 逆先序 DRL 中序 LDR 逆中序 RDL 后序 LRD 逆后序 RLD第25页/共85页2021-11-13261. 先序遍历DLR先序遍历算法的遍历过程 遍历结果： abdefc第26页/共85页2021-11-13272. 中序遍历LDR中序遍历算法的遍历过程点 */ inorder (p-rchild); /* 中序遍历右子树 */ 遍历结果：dbefac第27页/共85页2021-11-13283. 后序遍历LRD后序遍历算法的遍历过程遍历结果：dfebca第28页/共85页2021-11-13

17、296.4.2 二叉树的广度优先遍历（按层次遍历二叉树）从根开始逐层访问。先遍历二叉树的第一层结点，然后遍历第二层结点，最后遍历最下层的结点。而对每一层的遍历是按从左至右的方式进行。在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。广度优先遍历算法第29页/共85页2021-11-1330Bitree *Qmaxsize;void layer(BiT

18、ree *p) BiTree *s; if (p!=NULL) rear=1; front=0; Qrear=p; while (frontdata); if (s-lchild!=NULL) /左子树非空 rear+; Qrear=s-lchild; /左子树根结点入队 二叉树的广度优先遍历实例第30页/共85页2021-11-1331 if (s-rchild !=NULL) /右子树非空 rear+; Qrear=s-lchild; /右子树根结点入队 第31页/共85页2021-11-1332ABCDEFG第32页/共85页2021-11-13336.4.3 深度优先的非递归算法 分析

19、：二叉树的深度优先遍历算法是以递归形式给出的，运行效率低，可读性不强。因递归调用过程要用到栈来保存每次调用的参数，所以，我们可以用栈来实现二叉树的深度优先遍历，将递归算法转化为非递归算法。 以中序遍历为例，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出并访问根结点，再遍历右子树。算法执行过程第33页/共85页2021-11-1334void inorder(BiTree *T) SqStack *S; BiTree *P=T;/P为工作指针InitStack(S); /*顺序栈初始化*/while( P!=NULL | !Empty(S) if (P!=NULL) Push(

20、S,P); /*根结点入栈*/ P=P-lchild; /* 遍历左子树*/ else Pop(S,P); /*左子树遍历结束，出栈 */ printf(%c,P-data); P=P-rchild; /*遍历右子树*/ 第34页/共85页2021-11-1335&a&b&d&c栈的变化情况输出序列为：dbac第35页/共85页2021-11-13366.4.4 从遍历序列恢复二叉树可以由DLR和LDR的遍历序列可以唯一地确定一棵二叉树，或者由LRD和LDR的遍历序列可以唯一地确定一棵二叉树。通过DLR或者LRD的遍历序列确定二叉树或子树的根结点；通过LDR确定

21、左、右子树的序列。第36页/共85页2021-11-1337例： 由先序序列 ABHFDECKG 和中序序列 HBDFAEKCG 恢复二叉树的过程。第37页/共85页2021-11-13386.4.5 遍历算法的应用1.统计二叉树的叶子结点数int count =0; int countleaf(bitree *p) if ( p != NULL ) count = countleaf( plchild ); /* 对左子树上的叶子结点计数*/ if ( (plchild= =NULL)&(prchild= =NULL) count=count+1;count = countleaf(

22、prchild); /* 对右子树上的叶子结点计数*/ return count; 请考虑如何统计度为1的结点数，度为2的结点数。第38页/共85页2021-11-13392.利用二叉树先序遍历计算二叉树的深度int l=h=0; int treedepth(bitree * p, int l )if ( p!= NULL) l+; if ( lh ) h=l; h=treedepth( plchild, l ); / 计算左子树的深度 h=treedepth( prchild, l ); /计算右子树的深度 return h; 第39页/共85页2021-11-13403.求二叉树结点个数i

23、nt Size(BiTree *T) if (T=NULL) return (0); else return (1 + Size (T-lchild ) + Size ( T-rchild); /二叉树的结点个数是根结点、左右子树结点个数之和4.交换左右子树void Exchange(BiTree *T)BiTree *S;if (T!=NULL) S=T-lchild; T-lchild=T-rchild;T-rchild=S;Exchange(T-lchild);Exchange(T-rchild);第40页/共85页2021-11-13415.利用先序遍历方法，以嵌套括号的形式输出二叉树

24、的层次结构void OutBT(BiTree *p) if (p!=NULL) printf(“%c”,p-data); if(p-lchild!=NULL|p-rchild!=NULL) /有左子树或右子树 printf( “(” ); OutBT(p-lchild); /遍历左子树 if(p-rchild!=NULL) printf( “,” ); /有右子树输出逗号 OutBT(p-rchild); /遍历右子树 printf( “)” ); 输出的结果第41页/共85页2021-11-1342输出的结果：A（B（D（，G），E），C（F）ABCDEFG第42页/共85页2021-11-

25、13436.5 6.5 树和森林任何一棵树(T)都可以转换为一棵二叉树(T)，同样一棵二叉树也可转换成一棵树，而且这种转换是具有惟一性的。1.树转为二叉树 在兄弟之间增加一条连线； 对每个结点，除了保留与其左孩子的连线外，除去与其他孩子之间的连线。 以树的根结点为轴心，将整个树顺时针旋转45。2.二叉树转为树 若结点X是双亲Y的左孩子，则将X的右孩子，右孩子的右孩子，都与X的双亲结点Y用线相连； 去掉原有的双亲到右孩子的连线。第43页/共85页2021-11-1344 (c) A D I G H E B C F (d) A D I G H E B C F (a) T AFDGBECIH ( b

26、 ) T (c) (c) (c)第44页/共85页2021-11-13456.6 6.6 线索二叉树遍历二叉树是将一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前趋和直接后继。当以二叉链表作为存储结构时，如果希望能直接得到结点在任一序列(先序、中序或后序)中的前驱和后继信息，而不需要每次对二叉树进行遍历，有必要引入线索二叉树。线索是指向结点前趋和后继的指针，若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前趋结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针。按照不

27、同的遍历序列，可以得到先序、中序和后序线索二叉树。第45页/共85页2021-11-1346 有n个结点的二叉链表中必然存在n1个空的指针域，利用空的指针域来存放结点的前趋和后继信息是可行的。线索二叉树的结点结构实质上利用二叉链表中的空指针域作为线索。 二叉树的线索化的实质是将二叉链表中的空指针改为指向前趋或后继的线索。因为前趋或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。第46页/共85页2021-11-1347中序线索二叉树及线索链表中序遍历序列：BDAEC第47页/共85页2021-11-13486.7 6.7 二叉树的应用6.7.1 哈夫曼树及应用

28、1.基本概念路径长度 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。(a)PL=0+1(a)PL=0+1* *2+22+2* *4+3=134+3=13(b)PL=0+1(b)PL=0+1* *2+22+2* *3+33+3* *2=142=14第48页/共85页2021-11-1349带权路径长度 树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和。 其中n为树中叶子结点的数目，wi为叶子结点i的权值，li为叶子结点i到根结点之间的路径长度。niiilwWPL1第49页/共85页2021-11-1350叶子结点的权值相

29、同，具有不同带权路径长度的二叉树哈夫曼树 带权路径长度最小的二叉树称为哈夫曼树（最优二叉树）。在哈夫曼树中，权值越大的结点离根越近。第50页/共85页2021-11-1351哈夫曼树的不唯一性 权值为w1,w2, ,wn 的n个叶子结点形成的二叉树，可以具有多种形态，其中能被称为哈夫曼树的二叉树并不是唯一的。如下图。 b d c a 3 4 5 7 (a) (b) b a c d 3 4 5 7 不不同同形形态态的的哈哈夫夫曼曼树树 (a) WPL =3242527238；(b) WPL =334352738。第51页/共85页2021-11-1352完全二叉树不一定是哈夫曼树 在叶子数和权值

30、相同的二叉树中，完全二叉树不一定是哈夫曼树（最优二叉树）。如下图。 (a) (b) 5 a d c b 4 2 7 b d c a 2 4 5 7 完完全全二二叉叉树树与与哈哈夫夫曼曼树树 (a) WPL2242527236；(b) WPL2343527135。第52页/共85页2021-11-13532.哈夫曼树的构造哈夫曼树的构造 哈夫曼算法：哈夫曼算法：(1) 由给定的由给定的n个权值个权值w0, w1, w2, , wn-1，构成具有，构成具有n棵棵二叉树的集合二叉树的集合F = T0, T1, T2, , Tn-1，其中每一棵二叉，其中每一棵二叉树树Ti只有一个带有权值只有一个带有权

31、值wi的根结点，其左、右子树均为的根结点，其左、右子树均为空。空。 (2) 重复以下步骤重复以下步骤, 直到直到F中仅剩下一棵树为止：中仅剩下一棵树为止：第53页/共85页2021-11-1354 又一权值集合0.1,0.02,0.1,0.08,0.1,0.3,0.4，试构造一颗huffman树第54页/共85页2021-11-1355第55页/共85页2021-11-13563. 哈夫曼树的应用最佳判定算法例：编制一个将百分制转换成五级制的程序，使比较次数最少。各分数段分布情况如下：百分制05960697079808990100五级制不及格（E）及格（D）中（C）良（B）优（A）比例数0.0

32、50.150.40.30.1第56页/共85页2021-11-13571 10.40.40.60.60.30.30.30.30.150.150.150.150.050.050.10.1AEDBCs80s70s90s60EDCBAFTTFFTTF？第57页/共85页2021-11-1358哈夫曼编码主要用途是实现数据压缩。 设给出一段报文： abaccda 字符集合是 a, b, c, d ，各个字符出现的频度(次数)是 W 3, 1, 2, 1。 若给每个字符以等长编码 a : 00 b : 01 c : 10 d : 11则总编码为00010010101100长度为 ( 3+1+2+1 )

33、* 2 = 14 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。 因各字符出现的概率为 3/7, 1/7, 2/7, 1/7。第58页/共85页2021-11-1359第59页/共85页2021-11-1360构造哈夫曼树算法中的数据结构 存储结构define n 叶子数目define m 2*n-1 /* 结点总数 */ typedef char datatype; typedef struct float weight; datatype data; int lchild, rchild, parent; hufmtree;hufmtree treem; 采用顺序存储结构

34、，每个结点为一个结构体。第60页/共85页2021-11-1361构造哈夫曼树算法实现 HUFFMAN(hufmtree tree )int i, j, p; char ch; float small1, small2, f; for( i=0; im; i+) /* 初始化 */ treei.parent=0; treei.lchild=0; treei.rchild=0; treei.weight=0.0; treei.data= 0; for( i=0; in; i+) /输入n个结点的权值和结点值 scanf(“ %f ”, &f); treei.weight=f; scanf

35、(“ %c ”,&ch); treei.data=ch; 第61页/共85页2021-11-1362 for( i=n; im ;i+ ) / 进行n-1次合并，产生n-1个新结点 p1=p2=0; / 记录权值最小、次最小的结点下标 small1=small2=Maxval; /Maxval是float类型的最大值 / 从下标0扫描到已生成的结点下标 for ( j=0; j=i-1; j+ ) if ( treej.parent= =0) if ( treej.weightsmall1 ) small2=small1; /改变最小权，次最小权及对应位置 small1=treej.w

36、eight; p2=p1; p1=j; else if( treej.weightsmall2 ) /改变次小权及位置 small2=treej.weight; p2=j; treep1.parent=i; /给合并的两个结点的双亲域赋值 treep2.parent=i; treei.lchild=p1;/ 给新生成的结点的左右孩子域赋值 treei.rchild=p2; treei.weight =treep1.weight+treep2.weight;/给新生成的结点的权值域赋值 /* HUFFMAN */第62页/共85页2021-11-1363构造哈夫曼树算法的基本思想：对m=2n-1

37、个结点初始化，将双亲域，左、右孩子域，权值，结点值置0；输入n个叶子结点的权值和结点值；循环体执行n-1次，进行n-1次合并，产生n-1个新结点： 在i个结点中找出两个双亲域为0（即没有被合并的结点）且权值最小的结点，p1指示权值最小的结点，p2指示权值次最小的结点； 将两棵根结点权值最小的二叉树进行合并： treep1.parent=i; /i为新结点，即新产生的双亲结点treep2.parent=i; treei.lchild=p1; /新产生的双亲结点指向左、右子树的根结点 treei.rchild=p2; treei.weight = treep1.weight+treep2.weig

38、ht; /新结点的权值是左、右子树根结点权值之和。第63页/共85页2021-11-1364哈夫曼编码的数据结构编码数组结构描述如下：typedef char datatype;typedef struct char bitsn; /编码数组位串，其中n为叶子结 点数目 int start; /编码在位串的起始位置 datatype data; /结点值 codetype;codetype coden; 一个字符的哈夫曼编码在数组bits中从高位到低位顺序存储。第64页/共85页2021-11-1365哈夫曼编码的算法的基本思想 从叶子到根逆向求哈夫曼编码 从叶子treei出发，利用双亲地址找

39、到双亲结点treep，再利用treep的lchild和rchild指针域判断treei是treep的左孩子还是右孩子，然后决定分配代码的 0 还是代码 1 , 然后以treep为出发点继续向上回溯，直到根结点为止。第65页/共85页2021-11-1366哈夫曼编码算法实现void HUFFMANCODE(codetype code ，hufmtree tree )/code 存放求出的哈夫曼编码的数组， tree已知的哈夫曼树 int i, c, p; codetype cd; / 缓冲变量 for ( i=0; in; i+ ) /n为叶子结点数目 ，循环产生n个字符的哈夫曼编码 cd.

40、start=n; /从叶子结点出发向上回溯 ，在bits中， 从高位开始存储 c=i; /c指示第i个叶子结点 p=treec.parent; /p指示结点c的双亲结点 cd.data=treec.data; /对结点数据域赋值 第66页/共85页2021-11-1367 while( p!=0 ) /c指示到根结点时，p为0 cd.start - ; if( treep. lchild = = c) cd.bitscd.start= 0; else cd.bits cd.start=1; /若结点c是双亲结点p的左孩子，置0；否则就是右孩子，置1 c=p; /双亲结点p作为孩子结点，用c指示

41、 p=treec.parent; /p指示结点c的双亲结点 codei=cd; /一个字符的编码存入codei /for_end / HUFFMANCODE第67页/共85页2021-11-1368哈夫曼编码结果 对下图所示的哈夫曼树进行编码，可得到下表所示的编码表。code下标bitsstartdata0123003a11101b2102c31111d第68页/共85页2021-11-1369哈夫曼树译码 定义：哈夫曼树译码是指由给定的代码求出代码所表示的结点值。 译码的过程是：从根结点出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所

42、对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。第69页/共85页2021-11-1370哈夫曼树译码算法void HUFFMANDECODE(codetype code ，hufmtree tree )int i, c, p, b; int endflag=-1; /* 电文结束标志取-1 */ i=m-1; /* 从根结点开始向下搜索 */ scanf ( “%d”, &b); /* 读入一个二进制代码 */ while ( b != endflag) if( b= =0) i=treei.lchild; /* 走向左孩子 */ else i=treei.rchil

43、d; /* 走向右孩子 */ if ( treei.lchild= =0 ) /* treei是叶子结点 */ putchar( codei.data); i=m-1; /* 回到根结点 */ scanf(“%d”, &b); /* 读入下一个二进制代码 */ if (treei.lchild!=0)&(i!=m-1) ) /* 电文读完尚未到叶子结点 */ printf( “n ERRORn”); /* 输入电文有错 */ /* HUFFMANDECODE */ 说明：treei.lchild为0，treei.rchild也必然为0，因为哈夫曼树没有度为1的结点，所以tree

44、i是叶子结点。第70页/共85页2021-11-13716.7.2 二叉排序树二叉排序树的概念： 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 每个结点都有一个关键字(key)，所有结点的关键字互不相同。 左子树(若非空)上所有结点的关键字都小于根结点的关键字。 右子树(若非空)上所有结点的关键字都大于根结点的关键字。 左子树和右子树也是二叉排序树。第71页/共85页2021-11-1372几个二叉排序树的例子几个二叉排序树的例子第72页/共85页2021-11-1373二叉排序树的数据结构 二叉排序树的二叉链表存储结构结点结构描述如下：typedef int keytype;typ

45、edef struct keytype key; /关键字项 datatype other; / 其它数据项 struct node *lchild, *rchild; /左、右指针域 bstnode;第73页/共85页2021-11-1374二叉排序树的构造 构造一棵二叉排序树，就是从空的二叉排序树开始，逐个结点插入到二叉排序树中。 对于一组数据元素 R1, R2, , Rn , 可按以下方法来构造二叉排序树：说明：每次插入的新结点都是当前二叉树的叶子结点 给定的关键字序列不同，二叉排序树的形态则不同 二叉排序树中不存在两个结点的关键字相同的结点第74页/共85页2021-11-1375例：给定关键字序列10、18、3