1、6.1 树的概念6.2 二叉树6.3 二叉树的存储结构6.4 二叉树的遍历6.5 树和森林6.6 线索二叉树6.7 二叉树的应用习题11/11/202216.1 6.1 树的概念树的概念n树的定义树的定义(递归定义)：树（Tree）是n（n0）个结点的有限集合T，满足两个条件：（1）有且仅有一个特定的称为根（）有且仅有一个特定的称为根（Root）的结点，的结点，它没有前趋；它没有前趋；（2）其余的结点可分成）其余的结点可分成m个互不相交的有限集合个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为根其中每个集合又是一棵树，并称为根的子树。的子树。当当n=0时的空集合定义为空树。
2、时的空集合定义为空树。11/11/20222n使用圆圈表示结点，连线表示结点之间的关系，结点的名字可写在圆圈内或圆圈旁。学校一系二系十系一室八室一室七室n树的直观表示法树的直观表示法11/11/20223n树的基本术语树的基本术语l结点：指树中的一个元素，包含数据项及若干指向其子树的分支。l结点的度：指结点拥有的子树个数。l树的度：指树中结点的度的最大值。11/11/20224l叶子：指度为零的结点，又称为终端结点。l孩子：一个结点的子树的根称为该结点的孩子。l双亲：一个结点的直接上层结点称为该结点的双亲。l兄弟：同一双亲的孩子互称为兄弟。l结点的层次：从根结点开始，根结点为第一层，根的孩子为
3、第二层，根的孩子的孩子为第三层，依次类推。l树的深度：树中结点的最大层次数。l堂兄弟：双亲在同一层上的结点互称为堂兄弟。11/11/20225l路径：若存在一个结点序列k1,k2,kj,可使k1到达kj,则称这个结点序列是k1到达kj的一条路径。l子孙和祖先：若存在k1到kj的一条路径k1,k2,kj，则k1,kj-1为kj的祖先，而k2,kj为k1的子孙。l森林：m(m0)棵互不相交的树的集合构成森林。l有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。11/11/20226n顺序存储q顺序存储时，首先必须对树形结构的结点进行某
4、种顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。方式的线性化，使之成为一个线性序列，然后存储。n链式存储q链式存储时，使用多指针域的结点形式，每一个指链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。结构，通常采用二叉树的形式存储树。树的存储结构树的存储结构11/11/202276.2 6.2 二叉树二叉树n定义（二叉树的递归定义）：二叉树是n（n0）个结点的有限集，它或为空树（n=0
5、），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。n二叉树的五种基本形态：n二叉树与度为2的树的区别：二叉树的子树有左右之分，而树的子树不分左右；11/11/20228u满二叉树和完全二叉树满二叉树和完全二叉树l一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。l如果一个深度为k的二叉树，它的结点按照从根结点开始，自上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。完全二叉树的1k-1层上共有2k-1-1个结点，第k层的结点集中在左边。l满二叉树一定是
6、完全二叉树，而完全二叉树不一定是满二叉树。1 3 7 5 6 4 2 k=3 的满二叉树 1 3 5 6 4 2 完全二叉树 1 3 6 5 4 2 非完全二叉树 11/11/20229二叉树的性质二叉树的性质-1n性质1：在二叉树的第i层上至多有2i-1个结点(i1)。n证明：可用数学归纳法予以证明。当i=1时，有2i-1=20=1，同时第一层上只有一个根结点，故命题成立。设当i=k时成立，即第k层上至多有2k-1个结点。当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层上至多有22k-1=2k个结点，故命题成立。11/11/202210二叉树的性质二叉树的性质-2n性质2：
7、深度为k的二叉树至多有2k-1个结点(k1)。n证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为故命题成立。k1ik1-i1-2211/11/202211二叉树的性质二叉树的性质-3n性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。n证明：设度为1的结点数为n1，则一棵二叉树的结点总数为：n=n0+n1+n2 n 因为除根结点外，其余结点都有一个进入的分支(边)，设B为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有 B=2n2+n1，即 n=2n2+n1+1 比较两式可得n0=n2+1，证毕。11
8、/11/202212二叉树的性质二叉树的性质-4n性质4：具有n个结点的完全二叉树的深度为log2n+1或log2(n+1)。(其中x表示不大于x的最大整数，x表示不小于x的最小整数。)n证明：设完全二叉树的深度为k，则有 2k-1-1 n 2k 1 (1)(1)式变形为 2k-1 n+1 2k，两边取对数 k-1log2（n1）k 取整得 klog2(n+1)2k-1 n 2k（第k层至少有一个结点）（2）两边取对数 k-1 log2n 1,则 i 的双亲为i/2n若2*i n,则 i 的左孩子为2*i，否则无左孩子n若2*i+1 n,则 i 的右孩子为2*i+1，否则无右孩子n若i为偶数,
9、且i!=n,则其右兄弟为i+1n若i为奇数,且i!=1,则其左兄弟为i-1n结点i 所在层次为 log2i+111/11/2022146.3 6.3 二叉树的存储结构二叉树的存储结构6.3.1 顺序存储结构n完全二叉树n根据二叉树性质5，在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对结点进行顺序编号，便可得到一个反映结点之间关系的线性序列。n下图的完全二叉树的顺序存储结构如下表：左左图图的的完完全全二二叉叉树树的的顺顺序序存存储储 数组 下标 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
10、J I H E 3 7 6 C G F 完完全全二二叉叉树树的的结结点点编编号号 11/11/202215n一般二叉树n将二叉树映射为完全二叉树（通过虚结点）n用完全二叉树的方式存储。n根据性质2，采用顺序存储结构存储一棵深度为k的完全二叉树或一般二叉树，向量的长度是2k-1。11/11/202216n由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。n存储上述单支二叉树，所需的向量长度为25-1=3111/11/2022176.3.2 链式存储结构n二叉树的链式存储结构每个结点含有数据域和两个指针域，左、右指针域分别用来指向左孩子和右孩子。二叉树的链式
11、存储结构也称为二叉链表。n二叉链表结点的C语言逻辑描述为：typedef int datatype；typedef struct node datatype data；struct node*lchild，*rchild；bitree；bitree *root;注：n其中root是指向根结点的指针，当二叉树为空时，则root=NULL。n若结点的某个孩子不存在时，则相应的指针域为空。11/11/202218n三叉链表为了能够寻找双亲结点，在结点中增加一个指向双亲结点的指针域parent。A D B C(a)二叉树 A?B?C?D A?B?C?D?(b)二叉链表 (c)三叉链表?11/11/20
12、22196.3.3 二叉树建立（二叉链表的建立）11/11/2022206.3.3 6.3.3 二叉树建立（二叉链表的建立）二叉树建立（二叉链表的建立）u二叉树的建立 指在内存中如何建立二叉树的存储结构。u基本思想 对顺序存储结构而言，只需将二叉树各个结点的值按原有的逻辑关系送入相应的向量单元中。对链式存储结构而言，其建立算法有多种，它们依赖于按照何种形它们依赖于按照何种形式来输入二叉树的逻辑结构信息。式来输入二叉树的逻辑结构信息。常用的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，则必须通过先添加若干个虚结点使其成为完全二叉树。11/11/202221u 基
13、本步骤问题：如何将新结点正确地链接到它的双亲结点上？问题：如何将新结点正确地链接到它的双亲结点上？11/11/202222 算法具体实现q依据依据先建立的结点，其孩子结点也一定先建立的特点先建立的结点，其孩子结点也一定先建立的特点，所，所以可以以可以11/11/202223n二叉树的建立算法bitree*CREATREE()/*建立二叉树函数，函数返回指向根结点的指针*/char ch；/*结点信息变量*/bitree*Q maxsize；/*设置指针类型数组来构成队列*intfront,rear；/*队头和队尾指针变量*/bitree *root,*s；/*根结点指针和中间指针变量*/roo
14、t=NULL；/*二叉树置空*/front=1;rear=0;/*设置队列指针变量初值*/*以上为初始化*/11/11/202224while(ch=getchar()!=#)/*输入一个字符，当不是结束符时执行以下操作*/s=NULL;if(ch!=)/*表示虚结点，当不是虚结点则建立新结点*/s=malloc(sizeof(bitree);sdata=ch;slchild=NULL;srchild=NULL;rear+;/*队尾指针增1，指向新结点地址应存放的单元*/Qrear=s;/*将新结点地址入队或虚结点指针NULL入队*/if(rear=1)root=s;/*输入的第一个结点作为根
15、结点*/else if(s&Qfront)/*孩子和双亲结点都不是虚结点*/if(rear%2=0)Qfrontlchild=s;/*rear为偶数，新结点是左孩子*/else Qfrontrchild=s;/*rear为奇数且不等于1，新结点是右孩子*/if(rear%2=1)front+;/*结点*Qfront的两个孩子处理完毕，出队列*/return root;/*返回根指针*/*CREATREE */11/11/2022256.4 6.4 二叉树的遍历二叉树的遍历n所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。n遍历的结果：产生一个关于结点的线性序列。6
16、.4.1 深度优先递归遍历 访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有：先序 DLR 逆先序 DRL 中序 LDR 逆中序 RDL 后序 LRD 逆后序 RLD11/11/2022261.先序遍历DLRn先序遍历算法的遍历过程遍历结果：遍历结果：abdefc11/11/2022272.中序遍历LDRn中序遍历算法的遍历过程遍历结果：遍历结果：dbefac11/11/2022283.后序遍历LRDn后序遍历算法的遍历过程遍历结果：遍历结果：dfebca11/11/2022296.4.2 二叉树的广度优先遍历（按层次遍历二叉树）n从根开始逐层访问。先遍历
17、二叉树的第一层结点，然后遍历第二层结点，最后遍历最下层的结点。而对每一层的遍历是按从左至右的方式进行。n在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。广度优先遍历算法11/11/202230Bitree*Qmaxsize;void layer(BiTree*p)BiTree*s;if(p!=NULL)rear=1;front=0;Qrear=p;
18、while(frontdata);if(s-lchild!=NULL)/左子树非空 rear+;Qrear=s-lchild;/左子树根结点入队 二叉树的广度优先遍历实例二叉树的广度优先遍历实例11/11/202231 if(s-rchild!=NULL)/右子树非空 rear+;Qrear=s-lchild;/右子树根结点入队 11/11/202232ABCDEFG11/11/2022336.4.3 深度优先的非递归算法 分析：二叉树的深度优先遍历算法是以递归形式给出的，运行效率低，可读性不强。因递归调用过程要用到栈来保存每次调用的参数，所以，我们可以用栈来实现二叉树的深度优先遍历，将递归算
19、法转化为非递归算法。以中序遍历为例，在遍历左子树之前，先把根结点入栈，当左子树遍历结束后，从栈中弹出并访问根结点，再遍历右子树。算法执行过程11/11/202234void inorder(BiTree*T)SqStack*S;BiTree*P=T;/P为工作指针InitStack(S);/*顺序栈初始化*/while(P!=NULL|!Empty(S)if(P!=NULL)Push(S,P);/*根结点入栈*/P=P-lchild;/*遍历左子树*/else Pop(S,P);/*左子树遍历结束，出栈*/printf(%c,P-data);P=P-rchild;/*遍历右子树*/11/11/
20、202235&a&b&d&c栈的变化情况栈的变化情况输出序列为：输出序列为：dbac11/11/2022366.4.4 从遍历序列恢复二叉树n可以由DLR和LDR的遍历序列可以唯一地确定一棵二叉树，或者由LRD和LDR的遍历序列可以唯一地确定一棵二叉树。n通过DLR或者LRD的遍历序列确定二叉树或子树的根结点；通过LDR确定左、右子树的序列。11/11/202237例：由先序序列 ABHFDECKG 和中序序列 HBDFAEKCG 恢复二叉树的过程。11/11/2022386.4.5 遍历算法的应用1.统计二叉树的叶子结点数int count=0;int countleaf(bitree*p)
21、if(p!=NULL)count=countleaf(plchild);/*对左子树上的叶子结点计数*/if(plchild=NULL)&(prchild=NULL)count=count+1;count=countleaf(prchild);/*对右子树上的叶子结点计数*/return count;n请考虑如何统计度为1的结点数，度为2的结点数。11/11/2022392.利用二叉树先序遍历计算二叉树的深度int l=h=0;int treedepth(bitree*p,int l)if(p!=NULL)l+;if (lh)h=l;h=treedepth(plchild,l);/计算左子树的
22、深度 h=treedepth(prchild,l);/计算右子树的深度 return h;11/11/2022401.3.求二叉树结点个数求二叉树结点个数int 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
23、=S;Exchange(T-lchild);Exchange(T-rchild);11/11/2022415.利用先序遍历方法，以嵌套括号的形式输出二叉树的层次结构利用先序遍历方法，以嵌套括号的形式输出二叉树的层次结构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(“,”);/有右子树输出逗号有右子树输出逗号 O
24、utBT(p-rchild);/遍历右子树遍历右子树 printf(“)”);输出的结果输出的结果11/11/202242输出的结果：A（B（D（，G），E），C（F）ABCDEFG11/11/2022436.5 6.5 树和森林树和森林n任何一棵树(T)都可以转换为一棵二叉树(T)，同样一棵二叉树也可转换成一棵树，而且这种转换是具有惟一性的。1.树转为二叉树 在兄弟之间增加一条连线；对每个结点，除了保留与其左孩子的连线外，除去与其他孩子之间的连线。以树的根结点为轴心，将整个树顺时针旋转45。2.二叉树转为树 若结点X是双亲Y的左孩子，则将X的右孩子，右孩子的右孩子，都与X的双亲结点Y用线相连
25、；去掉原有的双亲到右孩子的连线。11/11/202244 (c)A D I G H E B C F (d)A D I G H E B C F (a)T AFDGBECIH (b)T(c)(c)(c)11/11/2022456.6 6.6 线索二叉树线索二叉树n遍历二叉树是将一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前趋和直接后继。n当以二叉链表作为存储结构时，如果希望能直接得到结点在任一序列(先序、中序或后序)中的前驱和后继信息，而不需要每次对二叉树进行遍历，有必要引入线索二叉树。n线索是指向结点前趋和后继的指针，若结点有左孩子，则lchi
26、ld指示其左孩子，否则lchild中存储该结点的前趋结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针。n按照不同的遍历序列，可以得到先序、中序和后序线索二叉树。11/11/202246n有n个结点的二叉链表中必然存在n1个空的指针域，利用空的指针域来存放结点的前趋和后继信息是可行的。线索二叉树的结点结构实质上利用二叉链表中的空指针域作为线索。n二叉树的线索化的实质是将二叉链表中的空指针改为指向前趋或后继的线索。因为前趋或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。11/11/202247中序线索二叉树
27、及线索链中序线索二叉树及线索链表表中序遍历序列：中序遍历序列：BDAEC11/11/2022486.7 6.7 二叉树的应用二叉树的应用6.7.1 哈夫曼树及应用1.基本概念n路径长度 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。(a)PLa)PL=0+1=0+1*2+22+2*4+3=134+3=13(b)PLb)PL=0+1=0+1*2+22+2*3+33+3*2=142=1411/11/202249n带权路径长度 树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和。其中n为树中叶子结点的数目，wi为叶子结点i的权
28、值，li为叶子结点i到根结点之间的路径长度。niiilwWPL111/11/202250n 叶子结点的权值相同，具有不同带权路径长度的二叉树n哈夫曼树 带权路径长度最小的二叉树称为哈夫曼树（最优二叉树）。n在哈夫曼树中，权值越大的结点离根越近。11/11/202251n哈夫曼树的不唯一性 权值为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。11/11
29、/202252n完全二叉树不一定是哈夫曼树 在叶子数和权值相同的二叉树中，完全二叉树不一定是哈夫曼树（最优二叉树）。如下图。(a)(b)5 a d c b 4 2 7 b d c a 2 4 5 7 完完全全二二叉叉树树与与哈哈夫夫曼曼树树 (a)WPL2242527236；(b)WPL2343527135。11/11/2022532.哈夫曼树的构造哈夫曼树的构造 哈夫曼算法：哈夫曼算法：(1)由给定的由给定的n个权值个权值w0,w1,w2,wn-1，构成具有，构成具有n棵棵二叉树的集合二叉树的集合F=T0,T1,T2,Tn-1，其中每一棵二叉其中每一棵二叉树树Ti只有一个带有权值只有一个带有
30、权值wi的根结点，其左、右子树均为的根结点，其左、右子树均为空。空。(2)重复以下步骤重复以下步骤,直到直到F中仅剩下一棵树为止：中仅剩下一棵树为止：11/11/202254 又一权值集合0.1,0.02,0.1,0.08,0.1,0.3,0.4，试构造一颗huffman树11/11/20225511/11/2022563.哈夫曼树的应用 最佳判定算法 例：编制一个将百分制转换成五级制的程序，使比较次数最少。各分数段分布情况如下：百分制05960697079808990100五级制不及格（E）及格（D）中（C）良（B）优（A）比例数0.050.150.40.30.111/11/2022571
31、10.40.40.60.60.30.30.30.30.150.150.150.150.050.050.10.1AEDBCs80s70s90s60EDCBAFTTFFTTF？11/11/202258 哈夫曼编码主要用途是实现数据压缩。设给出一段报文：abaccda 字符集合是 a,b,c,d，各个字符出现的频度(次数)是 W 3,1,2,1。若给每个字符以等长编码 a:00 b:01 c:10 d:11则总编码为00010010101100长度为(3+1+2+1)*2=14 若按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。因各字符出现的概率为 3/7,1/7,2/7,1/7。11
32、/11/20225911/11/202260构造哈夫曼树算法中的数据结构构造哈夫曼树算法中的数据结构n存储结构define n 叶子数目define m 2*n-1 /*结点总数*/typedef char datatype;typedef struct float weight;datatype data;int lchild,rchild,parent;hufmtree;hufmtree treem;n采用顺序存储结构，每个结点为一个结构体。11/11/202261构造哈夫曼树算法实现构造哈夫曼树算法实现 HUFFMAN(hufmtree tree )int i,j,p;char ch;f
33、loat 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(“%c”,&ch);treei.data=ch;11/11/202262 for(i=n;im;i+)/进行n-1次合并，产生n-1个新结点 p1=p2=0;/记录权值最小、次最小的结点下标 small1=small2=Maxval;/
34、Maxval是float类型的最大值 /从下标0扫描到已生成的结点下标 for(j=0;j=i-1;j+)if(treej.parent=0)if(treej.weightsmall1)small2=small1;/改变最小权，次最小权及对应位置 small1=treej.weight;p2=p1;p1=j;else if(treej.weightsmall2)/改变次小权及位置 small2=treej.weight;p2=j;treep1.parent=i;/给合并的两个结点的双亲域赋值 treep2.parent=i;treei.lchild=p1;/给新生成的结点的左右孩子域赋值 tr
35、eei.rchild=p2;treei.weight=treep1.weight+treep2.weight;/给新生成的结点的权值域赋值 /*HUFFMAN*/11/11/202263构造哈夫曼树算法的基本思想：n对m=2n-1个结点初始化，将双亲域，左、右孩子域，权值，结点值置0；n输入n个叶子结点的权值和结点值；n循环体执行n-1次，进行n-1次合并，产生n-1个新结点：在i个结点中找出两个双亲域为0（即没有被合并的结点）且权值最小的结点，p1指示权值最小的结点，p2指示权值次最小的结点；将两棵根结点权值最小的二叉树进行合并：treep1.parent=i;/i为新结点，即新产生的双亲结
36、点treep2.parent=i;treei.lchild=p1;/新产生的双亲结点指向左、右子树的根结点 treei.rchild=p2;treei.weight=treep1.weight+treep2.weight;/新结点的权值是左、右子树根结点权值之和。11/11/202264哈夫曼编码的数据结构哈夫曼编码的数据结构n编码数组结构描述如下：typedef char datatype;typedef struct char bitsn;/编码数组位串，其中n为叶子结 点数目 int start;/编码在位串的起始位置 datatype data;/结点值 codetype;codety
37、pe coden;n一个字符的哈夫曼编码在数组bits中从高位到低位顺序存储。11/11/202265哈夫曼编码的算法的基本思想哈夫曼编码的算法的基本思想 从叶子到根逆向求哈夫曼编码 从叶子treei出发，利用双亲地址找到双亲结点treep，再利用treep的lchild和rchild指针域判断treei是treep的左孩子还是右孩子，然后决定分配代码的 0 还是代码 1,然后以treep为出发点继续向上回溯，直到根结点为止。11/11/202266哈夫曼编码算法实现哈夫曼编码算法实现void HUFFMANCODE(codetype code，hufmtree tree )/code 存放求
38、出的哈夫曼编码的数组，tree已知的哈夫曼树 int i,c,p;codetype cd;/缓冲变量 for(i=0;in;i+)/n为叶子结点数目，循环产生n个字符的哈夫曼编码 cd.start=n;/从叶子结点出发向上回溯，在bits中，从高位开始存储 c=i;/c指示第i个叶子结点 p=treec.parent;/p指示结点c的双亲结点 cd.data=treec.data;/对结点数据域赋值 11/11/202267 while(p!=0)/c指示到根结点时，p为0 cd.start-;if(treep.lchild=c)cd.bitscd.start=0;else cd.bits c
39、d.start=1;/若结点c是双亲结点p的左孩子，置0；否则就是右孩子，置1 c=p;/双亲结点p作为孩子结点，用c指示 p=treec.parent;/p指示结点c的双亲结点 codei=cd;/一个字符的编码存入codei /for_end /HUFFMANCODE11/11/202268哈夫曼编码结果哈夫曼编码结果n对下图所示的哈夫曼树进行编码，可得到下表所示的编码表。code下标bitsstartdata0123003a11101b2102c31111d11/11/202269哈夫曼树译码哈夫曼树译码n定义：哈夫曼树译码是指由给定的代码求出代码所表示的结点值。n译码的过程是：从根结点
40、出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结点开始继续译码，直到二进制电文结束。11/11/202270哈夫曼树译码算法哈夫曼树译码算法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
41、 i=treei.rchild;/*走向右孩子*/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 */n 说明：treei.lchild为0，treei.rchild也必然为0，因为哈夫曼树没有度为1的结点，所以treei是叶子结点。11/11/2022716.7.2 二叉排序树二
42、叉排序树的概念：二叉排序树或者是一棵空树，或者是具有下列性质的二叉树：每个结点都有一个关键字(key)，所有结点的关键字互不相同。左子树(若非空)上所有结点的关键字都小于根结点的关键字。右子树(若非空)上所有结点的关键字都大于根结点的关键字。左子树和右子树也是二叉排序树。11/11/202272几个二叉排序树的例子几个二叉排序树的例子11/11/202273二叉排序树的数据结构二叉排序树的数据结构n二叉排序树的二叉链表存储结构结点结构描述如下：typedef int keytype;typedef struct keytype key;/关键字项 datatype other;/其它数据项 s
43、truct node*lchild,*rchild;/左、右指针域 bstnode;11/11/202274二叉排序树的构造二叉排序树的构造n构造一棵二叉排序树，就是从空的二叉排序树开始，逐个结点插入到二叉排序树中。n对于一组数据元素 R1,R2,Rn ,可按以下方法来构造二叉排序树：说明：每次插入的新结点都是当前二叉树的叶子结点 给定的关键字序列不同，二叉排序树的形态则不同 二叉排序树中不存在两个结点的关键字相同的结点11/11/202275例：给定关键字序列例：给定关键字序列10、18、3、8、12、2、7、3，建立二叉排序树。，建立二叉排序树。11/11/202276将指针将指针s所指的
44、结点插入到根结点指针为所指的结点插入到根结点指针为t二叉排序树中的算法二叉排序树中的算法bstnode*INSERTBST(bstnode*t,bstnode*s)/t为二叉排序树的根指针，s为插入的结点指针*/bstnode*f,*p;p=t;while(p!=NULL)/寻找*s的合适插入位置，新插入的结点作为二叉排序树的叶子结点 f=p;/f指向*p结点双亲 if(skey=pkey)return t;/树中已有结点*s；无须插入 if(skey pkey)p=plchild;/在左子树中查找插入位置 else p=prchild;/在右子树中查找插入位置 if(t=NULL)retur
45、n s;/原树为空,返回s作为根指针 if(skeyfkey)flchild=s;/将*s插入为*f的左孩子 else frchild=s;/将*s插入为*f的右孩子 return t;/*INSERTBST*/11/11/202277输入一组数据元素的序列，构造二叉排序树的算法输入一组数据元素的序列，构造二叉排序树的算法bstnode*CREATBST()/生成二叉排序树 bstnode *t,*s;keytype key,endflag=0;/endflag为结点结束标志 datatype data;t=NULL;/设置二叉排序树的初态为空树 scanf(“%d”,&key);/读入一个结
46、点的关键字 while(key!=endflag)/输入非结束标志，执行以下操作 s=malloc(sizeof(bstnode);/申请新结点 slchild=srchild=NULL;/赋初值 skey=key;scanf(“%d”,&data);/读入结点的其它数据项 sother=data;t=INSERTBST(t,s)/将新结点插入树t中 scanf(“%d”,&key)/读入下一个结点的关键字 return t;/CREATBST11/11/202278二叉排序树中的结点删除二叉排序树中的结点删除u要求删除一个结点后，仍然保持二叉排序树的有要求删除一个结点后，仍然保持二叉排序树的
47、有序性。序性。u由由p指向待删除的结点，由指向待删除的结点，由q指向其双亲结点，则指向其双亲结点，则二叉排序树中结点删除分四种情况考虑：二叉排序树中结点删除分四种情况考虑：（1）若p指向叶子结点，只需将其双亲结点指向它的指针清零，再释放它即可；11/11/20227911/11/202280(a)(a)用用LDRLDR中的中的*p p的直接前趋的直接前趋*s s代替代替*p p(b)(b)用用LDRLDR中的中的*p p的直接后继的直接后继*s s代替代替*p p11/11/202281 若pL和pR均非空，删除*p结点，保持二叉排序树特性不变的另一做法是：令pL直接链接到*q的左（或右）孩子链域上，pR链接到*p结点中序前驱结点上。11/11/202282习题习题习题六（P152）一 二 三 四：4 5 6(上机题)11 12 13 1411/11/20228311/11/20228411/11/202285
