数据结构第6章-树课件

1、第6章 树6.1 树的概念6.2 二叉树6.3 二叉树的存储结构6.4 二叉树的遍历6.5 树和森林6.6 线索二叉树6.7 二叉树的应用习题10/12/20221第6章 树6.1 树的概念10/10/202216.1 树的概念树的定义(递归定义)：树（Tree）是n（n0）个结点的有限集合T，满足两个条件：（1）有且仅有一个特定的称为根（Root）的结点，它没有前趋；（2）其余的结点可分成m个互不相交的有限集合T1,T2,Tm，其中每个集合又是一棵树，并称为根的子树。当n=0时的空集合定义为空树。10/12/202226.1 树的概念树的定义(递归定义)：树（Tree）是n（n使用圆圈表示结

2、点，连线表示结点之间的关系，结点的名字可写在圆圈内或圆圈旁。树的直观表示法10/12/20223使用圆圈表示结点，连线表示结点之间的关系，结点的名字可写在圆树的基本术语结点：指树中的一个元素，包含数据项及若干指向其子树的分支。结点的度：指结点拥有的子树个数。树的度：指树中结点的度的最大值。10/12/20224树的基本术语结点：指树中的一个元素，包含数据项及若干指向其子叶子：指度为零的结点，又称为终端结点。孩子：一个结点的子树的根称为该结点的孩子。双亲：一个结点的直接上层结点称为该结点的双亲。兄弟：同一双亲的孩子互称为兄弟。结点的层次：从根结点开始，根结点为第一层，根的孩子为第二层，根的孩子的

3、孩子为第三层，依次类推。树的深度：树中结点的最大层次数。堂兄弟：双亲在同一层上的结点互称为堂兄弟。10/12/20225叶子：指度为零的结点，又称为终端结点。10/10/20225路径：若存在一个结点序列k1,k2,kj, 可使k1到达kj, 则称这个结点序列是k1到达kj的一条路径。子孙和祖先：若存在k1到kj的一条路径k1,k2,kj，则k1,kj-1为kj的祖先，而k2,kj为k1的子孙。森林：m(m0)棵互不相交的树的集合构成森林。有序树和无序树：若将树中每个结点的各个子树都看成是从左到右有次序的（即不能互换），则称该树为有序树，否则为无序树。10/12/20226路径：若存在一个结点

4、序列k1,k2,kj, 可使k1到达顺序存储顺序存储时，首先必须对树形结构的结点进行某种方式的线性化，使之成为一个线性序列，然后存储。链式存储链式存储时，使用多指针域的结点形式，每一个指针域指向一棵子树的根结点。由于树的分支数不固定，很难给出一种固定的存储结构，通常采用二叉树的形式存储树。树的存储结构10/12/20227顺序存储树的存储结构10/10/202276.2 二叉树定义（二叉树的递归定义）：二叉树是n（n0）个结点的有限集，它或为空树（n=0），或由一个根结点及两棵互不相交的、分别称作这个根的左子树和右子树的二叉树构成。二叉树的五种基本形态：二叉树与度为2的树的区别：二叉树的子树有

5、左右之分，而树的子树不分左右；10/12/202286.2 二叉树定义（二叉树的递归定义）：二叉树是n（n满二叉树和完全二叉树一棵深度为k且有2k-1个结点的二叉树称为满二叉树。满二叉树的特点是每一层的结点数都达到该层可具有的最大结点数。如果一个深度为k的二叉树，它的结点按照从根结点开始，自上而下，从左至右进行连续编号后，得到的顺序与满二叉树相应结点编号顺序一致，则称这个二叉树为完全二叉树。完全二叉树的1k-1层上共有2k-1-1个结点，第k层的结点集中在左边。满二叉树一定是完全二叉树，而完全二叉树不一定是满二叉树。10/12/20229满二叉树和完全二叉树一棵深度为k且有2k-1个结点的二叉

6、树称二叉树的性质-1性质1：在二叉树的第i层上至多有2i-1个结点(i1)。证明：可用数学归纳法予以证明。当i=1时，有2i-1=20=1，同时第一层上只有一个根结点，故命题成立。设当i=k时成立，即第k层上至多有2k-1个结点。当i=k+1时，由于二叉树的每个结点至多有两个孩子，所以第k+1层上至多有22k-1=2k个结点，故命题成立。10/12/202210二叉树的性质-1性质1：在二叉树的第i层上至多有2i-1个结二叉树的性质-2性质2：深度为k的二叉树至多有2k-1个结点(k1)。证明：性质1给出了二叉树每一层中含有的最大结点数，深度为k的二叉树的结点总数至多为故命题成立。10/12/

7、202211二叉树的性质-2性质2：深度为k的二叉树至多有2k-1个结点二叉树的性质-3性质3：对任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。证明：设度为1的结点数为n1，则一棵二叉树的结点总数为： n=n0+n1+n2 因为除根结点外，其余结点都有一个进入的分支(边)，设B为分支总数，则n=B+1。又考虑到分支是由度为1和2的结点发出的，故有 B=2n2+n1，即 n=2n2+n1+1 比较两式可得n0=n2+1，证毕。10/12/202212二叉树的性质-3性质3：对任何一棵二叉树，如果其终端结点数为二叉树的性质-4性质4：具有n个结点的完全二叉树的深度

8、为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 取整得 klog2(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,

9、则其左兄弟为i-1结点i 所在层次为 log2i +110/12/202214二叉树的性质-5性质5：如果将一棵有n个结点的完全二叉树的结6.3 二叉树的存储结构6.3.1 顺序存储结构完全二叉树根据二叉树性质5，在一棵完全二叉树中，按照从根结点起，自上而下，从左至右的方式对结点进行顺序编号，便可得到一个反映结点之间关系的线性序列。下图的完全二叉树的顺序存储结构如下表：10/12/2022156.3 二叉树的存储结构6.3.1 顺序存储结构10/1一般二叉树将二叉树映射为完全二叉树（通过虚结点）用完全二叉树的方式存储。根据性质2，采用顺序存储结构存储一棵深度为k的完全二叉树或一般二叉树，向量的

10、长度是2k-1。10/12/202216一般二叉树10/10/202216由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储空间，单支树就是一个极端情况。存储上述单支二叉树，所需的向量长度为25-1=3110/12/202217由于一般二叉树必须仿照完全二叉树那样存储，可能会浪费很多存储6.3.2 链式存储结构二叉树的链式存储结构每个结点含有数据域和两个指针域，左、右指针域分别用来指向左孩子和右孩子。二叉树的链式存储结构也称为二叉链表。二叉链表结点的C语言逻辑描述为：typedef int datatype；typedef struct node datatype data； str

11、uct node *lchild，*rchild；bitree；bitree *root;注：其中root是指向根结点的指针，当二叉树为空时，则root=NULL。若结点的某个孩子不存在时，则相应的指针域为空。10/12/2022186.3.2 链式存储结构10/10/202218三叉链表为了能够寻找双亲结点，在结点中增加一个指向双亲结点的指针域parent。10/12/202219三叉链表为了能够寻找双亲结点，在结点中增加一个指向双亲结6.3.3 二叉树建立（二叉链表的建立）10/12/2022206.3.3 二叉树建立（二叉链表的建立）10/10/2026.3.3 二叉树建立（二叉链表的建

12、立）二叉树的建立 指在内存中如何建立二叉树的存储结构。基本思想 对顺序存储结构而言，只需将二叉树各个结点的值按原有的逻辑关系送入相应的向量单元中。对链式存储结构而言，其建立算法有多种，它们依赖于按照何种形式来输入二叉树的逻辑结构信息。常用的算法是按照完全二叉树的层次顺序，依次输入结点信息来建立二叉链表。对于一般二叉树，则必须通过先添加若干个虚结点使其成为完全二叉树。10/12/2022216.3.3 二叉树建立（二叉链表的建立）二叉树的建立10/ 基本步骤按照结点的序号，依次输入结点信息，若输入的结点不是虚结点，则建立一个新结点。若新结点是第1个结点，则令其为根结点，否则将新结点作为孩子链接到

13、它的双亲结点上。如此反复进行，直到输入结束标志“”为止。问题：如何将新结点正确地链接到它的双亲结点上？10/12/202222 基本步骤10/10/202222 算法具体实现依据先建立的结点，其孩子结点也一定先建立的特点，所以可以设置一个指针数组构成的队列来保存已输入结点的地址（虚结点的地址为空），并使队尾(rear)指向当前输入的结点；队头(front)指向这个结点的双亲结点。由于根结点的地址放在（顺序）队列的（指针）数组下标为1的数组单元里，所以当rear为偶数时，则rear所指的结点应作为左孩子与其双亲链接，否则rear所指的结点应作为右孩子与其双亲链接。若双亲结点或孩子结点为虚结点，则

14、不需链接。当一个双亲结点与两个孩子链接完毕，则进行出队操作，使队头指针指向下一个待链接的双亲结点。10/12/202223 算法具体实现10/10/202223二叉树的建立算法bitree *CREATREE( ) /* 建立二叉树函数，函数返回指向根结点的指针 */char ch； /* 结点信息变量 */ bitree *Q maxsize； /* 设置指针类型数组来构成队列 * intfront, rear； /* 队头和队尾指针变量 */ bitree *root, *s； /* 根结点指针和中间指针变量 */ root=NULL； /* 二叉树置空 */ front=1; rear=

15、0; /* 设置队列指针变量初值 */*以上为初始化*/10/12/202224二叉树的建立算法10/10/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)

16、root=s; /* 输入的第一个结点作为根结点 */ 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 */10/12/202225while(ch=getchar()!=#)

17、/*6.4 二叉树的遍历所谓树的遍历，就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。遍历的结果：产生一个关于结点的线性序列。6.4.1 深度优先递归遍历 访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有： 先序 DLR 逆先序 DRL 中序 LDR 逆中序 RDL 后序 LRD 逆后序 RLD10/12/2022266.4 二叉树的遍历所谓树的遍历，就是按某种次序访问树中的先序遍历DLR先序遍历算法的遍历过程 若二叉树非空，执行以下操作：访问根结点；先序遍历左子树；先序遍历右子树。void preorder(bitree *p)/* 先序

18、遍历二叉树，p指向二叉树的根结点 */ if (p!=NULL) /* 二叉树p非空，则执行以下操作 */ printf (“ %c ”, p-data); /* 访问p所指结点 */ preorder (p-lchild); /* 先序遍历左子树 */ preorder (p-rchild); /* 先序遍历右子树 */ 遍历结果： abdefc10/12/202227先序遍历DLR遍历结果： abdefc10/10/20222中序遍历LDR中序遍历算法的遍历过程 若二叉树非空，执行以下操作：中序遍历左子树；访问根结点；中序遍历右子树。void inorder(bitree *p)/*中序遍

19、历二叉树，p指向二叉树的根结点 */ if (p!=NULL) /* 二叉树p非空，则执行以下操作 */ inorder (p-lchild); /* 中序遍历左子树 */ printf (“ %c ”, p-data); /* 访问p所指结点 */ inorder (p-rchild); /* 中序遍历右子树 */ 遍历结果：dbefac10/12/202228中序遍历LDR遍历结果：dbefac10/10/202228后序遍历LRD后序遍历算法的遍历过程 若二叉树非空，执行以下操作：后序遍历左子树；后序遍历右子树；访问根结点。void postorder(bitree *p)/* 后序遍历

20、二叉树，p指向二叉树的根结点 */ if (p!=NULL) /* 二叉树p非空，则执行以下操作 */ postorder (p-lchild); /* 后序遍历左子树 */ postorder (p-rchild); /* 后序遍历右子树 */ printf (“ %c ”, p-data); /* 访问p所指结点 */ 遍历结果：dfebca10/12/202229后序遍历LRD遍历结果：dfebca10/10/2022296.4.2 二叉树的广度优先遍历（按层次遍历二叉树）从根开始逐层访问。先遍历二叉树的第一层结点，然后遍历第二层结点，最后遍历最下层的结点。而对每一层的遍历是按从左至右的

21、方式进行。在上层中先被访问的结点，它的下层孩子也必然先被访问，因此在这种遍历算法的实现时，需要使用一个队列。在遍历进行之前先把二叉树的根结点的存储地址入队，然后依次从队列中出队结点的存储地址，每出队一个结点的存储地址则对该结点进行访问，然后依次将该结点的左孩子和右孩子的存储地址入队，如此反复，直到队空为止。广度优先遍历算法10/12/2022306.4.2 二叉树的广度优先遍历（按层次遍历二叉树）广度优Bitree *Qmaxsize;void layer(BiTree *p) BiTree *s; if (p!=NULL) rear=1; front=0; Qrear=p; while (f

22、rontdata); if (s-lchild!=NULL) /左子树非空 rear+; Qrear=s-lchild; /左子树根结点入队 二叉树的广度优先遍历实例10/12/202231Bitree *Qmaxsize;二叉树的广度优先遍历实 if (s-rchild !=NULL) /右子树非空 rear+; Qrear=s-lchild; /右子树根结点入队 10/12/202232 if (s-rchild !=NULL) ABCDEFG二叉树的广度优先遍历实例输出序列为：A,B,C,D,E,F,G10/12/202233ABCDEFG二叉树的广度优先遍历实例10/10/202236

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

24、P!=NULL | !Empty(S) if (P!=NULL) Push(S,P); /*根结点入栈*/ P=P-lchild; /* 遍历左子树*/ else Pop(S,P); /*左子树遍历结束，出栈 */ printf(%c,P-data); P=P-rchild; /*遍历右子树*/ 10/12/202235void inorder(BiTree *T)10/10/2&a&b&d&c栈的变化情况输出序列为：dbac10/12/202236&a&b&d&c栈的变化情况输出序列为：dbac10/10/6.4.4 从遍历序列恢复二叉树可以由DLR和LDR的遍历序列可以唯一地确定一棵二叉树

25、，或者由LRD和LDR的遍历序列可以唯一地确定一棵二叉树。通过DLR或者LRD的遍历序列确定二叉树或子树的根结点；通过LDR确定左、右子树的序列。10/12/2022376.4.4 从遍历序列恢复二叉树10/10/202237例： 由先序序列 ABHFDECKG 和中序序列 HBDFAEKCG 恢复二叉树的过程。10/12/202238例： 由先序序列 ABHFDECKG 和中序序列 6.4.5 遍历算法的应用统计二叉树的叶子结点数int count =0; int countleaf(bitree *p) if ( p != NULL ) count = countleaf( plchild

26、 ); /* 对左子树上的叶子结点计数*/ if ( (plchild= =NULL)&(prchild= =NULL) count=count+1;count = countleaf(prchild); /* 对右子树上的叶子结点计数*/ return count; 请考虑如何统计度为1的结点数，度为2的结点数。10/12/2022396.4.5 遍历算法的应用10/10/202239利用二叉树先序遍历计算二叉树的深度int l=h=0; int treedepth(bitree * p, int l )if ( p!= NULL) l+; if ( lh ) h=l; h=treedept

27、h( plchild, l ); / 计算左子树的深度 h=treedepth( prchild, l ); /计算右子树的深度 return h; 10/12/202240利用二叉树先序遍历计算二叉树的深度10/10/2022403.求二叉树结点个数int Size(BiTree *T) if (T=NULL) return (0); else return (1 + Size (T-lchild ) + Size ( T-rchild); /二叉树的结点个数是根结点、左右子树结点个数之和交换左右子树void Exchange(BiTree *T)BiTree *S;if (T!=NULL)

28、 S=T-lchild; T-lchild=T-rchild;T-rchild=S;Exchange(T-lchild);Exchange(T-rchild);10/12/2022413.求二叉树结点个数10/10/202241利用先序遍历方法，以嵌套括号的形式输出二叉树的层次结构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) p

29、rintf( “,” ); /有右子树输出逗号 OutBT(p-rchild); /遍历右子树 printf( “)” ); 输出的结果10/12/202242利用先序遍历方法，以嵌套括号的形式输出二叉树的层次结构输出的输出的结果：A（B（D（，G），E），C（F）ABCDEFG10/12/202243ABCDEFG10/10/2022436.5 树和森林任何一棵树(T)都可以转换为一棵二叉树(T)，同样一棵二叉树也可转换成一棵树，而且这种转换是具有惟一性的。树转为二叉树在兄弟之间增加一条连线；对每个结点，除了保留与其左孩子的连线外，除去与其他孩子之间的连线。以树的根结点为轴心，将整个树顺时针

30、旋转45。二叉树转为树若结点X是双亲Y的左孩子，则将X的右孩子，右孩子的右孩子，都与X的双亲结点Y用线相连；去掉原有的双亲到右孩子的连线。10/12/2022446.5 树和森林任何一棵树(T)都可以转换为一棵二叉树(T (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)10/12/202245 (c) A D I G H E B C6.6 线索二叉树遍历二叉树是将一个非线性结构进行线性化的操作，使每个结点（除第一个和最后一个）在这些线性序列中有且仅有一个直接前趋和直接后继。当以二叉链表作为

31、存储结构时，如果希望能直接得到结点在任一序列(先序、中序或后序)中的前驱和后继信息，而不需要每次对二叉树进行遍历，有必要引入线索二叉树。线索是指向结点前趋和后继的指针，若结点有左孩子，则lchild指示其左孩子，否则lchild中存储该结点的前趋结点的指针；若结点有右孩子，则rchild指示其右孩子，否则rchild中存储指向该结点的后继结点的指针。按照不同的遍历序列，可以得到先序、中序和后序线索二叉树。10/12/2022466.6 线索二叉树10/10/202246有n个结点的二叉链表中必然存在n1个空的指针域，利用空的指针域来存放结点的前趋和后继信息是可行的。线索二叉树的结点结构实质上利

32、用二叉链表中的空指针域作为线索。二叉树的线索化的实质是将二叉链表中的空指针改为指向前趋或后继的线索。因为前趋或后继的信息只有在遍历时才能得到，因此线索化的过程就是在遍历过程中修改空指针的过程。10/12/20224710/10/202247线索二叉树及其线索链表的表示标志域：ltag = 0, lchild为左孩子指针ltag = 1, lchild为前趋线索rtag = 0, rchild为右孩子指针rtag = 1, rchild为后继线索中序线索二叉树及线索链表中序遍历序列：BDAEC10/12/202248线索二叉树及其线索链表的表示标志域：中序线索二叉树及线索链表6.7 二叉树的应用

33、6.7.1 哈夫曼树及应用基本概念路径长度 两个结点之间的路径长度是连接两结点的路径上的分支数。树的路径长度是各结点到根结点的路径长度之和。具有不同路径长度的二叉树(a)PL=0+1*2+2*4+3=13(b)PL=0+1*2+2*3+3*2=1410/12/2022496.7 二叉树的应用6.7.1 哈夫曼树及应用具有不同路径带权路径长度 树的带权路径长度是树的各叶子结点所带的权值与该结点到根的路径长度的乘积的和。 其中n为树中叶子结点的数目，wi为叶子结点i的权值，li为叶子结点i到根结点之间的路径长度。10/12/202250带权路径长度10/10/202250叶子结点的权值相同，具有不

34、同带权路径长度的二叉树哈夫曼树 带权路径长度最小的二叉树称为哈夫曼树（最优二叉树）。在哈夫曼树中，权值越大的结点离根越近。10/12/202251叶子结点的权值相同，具有不同带权路径长度的二叉树10/10/哈夫曼树的不唯一性 权值为w1,w2, ,wn 的n个叶子结点形成的二叉树，可以具有多种形态，其中能被称为哈夫曼树的二叉树并不是唯一的。如下图。(a) WPL =3242527238；(b) WPL =334352738。10/12/202252哈夫曼树的不唯一性(a) WPL =324252完全二叉树不一定是哈夫曼树 在叶子数和权值相同的二叉树中，完全二叉树不一定是哈夫曼树（最优二叉树）。

35、如下图。(a) WPL2242527236；(b) WPL2343527135。10/12/202253完全二叉树不一定是哈夫曼树(a) WPL22425哈夫曼树的构造 哈夫曼算法： (1) 由给定的n个权值w0, w1, w2, , wn-1，构成具有n棵二叉树的集合F = T0, T1, T2, , Tn-1，其中每一棵二叉树Ti只有一个带有权值wi的根结点，其左、右子树均为空。 (2) 重复以下步骤, 直到F中仅剩下一棵树为止： 在F中选取两棵根结点的权值最小的二叉树, 作为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在F中删去这两棵二叉树

36、。 把新的二叉树加入F。10/12/202254哈夫曼树的构造10/10/202254哈夫曼树的构造过程 又一权值集合0.1,0.02,0.1,0.08,0.1,0.3,0.4，试构造一颗huffman树10/12/202255哈夫曼树的构造过程 又一权值集合0.1,0.0注：一个有n个叶子结点的初始集合，要生成哈夫曼树共要进行n-1次合并，产生n-1个新结点。最终求得的哈夫曼树共有n+n-1=2n-1个结点，并且哈夫曼树中没有度为1的分支结点。我们常称没有度为1的结点的二叉树为严格二叉树。10/12/202256注：10/10/202256哈夫曼树的应用在解决某些判定问题时，利用哈夫曼树可以

37、得到最佳判定算法用于通讯和数据传送时的哈夫曼编码最佳判定算法例：编制一个将百分制转换成五级制的程序，使比较次数最少。各分数段分布情况如下：百分制05960697079808990100五级制不及格（E）及格（D）中（C）良（B）优（A）比例数0.050.150.40.30.110/12/202257哈夫曼树的应用百分制059606970798089910.40.60.30.30.150.150.050.1AEDBCs80s70s90s60EDCBAFTTFFTTF？10/12/20225810.40.60.30.30.150.150.050.1AE哈夫曼编码主要用途是实现数据压缩。 设给出一段

38、报文： 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。10/12/202259哈夫曼编码10/10/202259化整为 3, 1, 2, 1 ，以它们作为各叶子结点上的权值，建立哈夫曼树。左分支赋 0，右分支赋 1，得到哈夫曼编码(不等长编码)

39、。 a : 0 b : 110 c : 10 d : 111电文的编码：0110010101110 （abaccda）它的总编码长度：1*3+3*1+2*2+3*1=13。比等长编码的情形要短。 n个叶子结点的最大编码长度不会超过n-1。 总编码长度正好等于哈夫曼树的带权路径长度WPL。 任一字符的编码都不是另一字符编码的前缀，称为前缀编码。哈夫曼编码是一种前缀编码。译码时不会混淆。哈夫曼编码树10/12/202260化整为 3, 1, 2, 1 ，以它们作为各叶子结点上构造哈夫曼树算法中的数据结构存储结构define n 叶子数目define m 2*n-1 /* 结点总数 */ typed

40、ef char datatype; typedef struct float weight; datatype data; int lchild, rchild, parent; hufmtree;hufmtree treem;采用顺序存储结构，每个结点为一个结构体。10/12/202261构造哈夫曼树算法中的数据结构存储结构define n 叶构造哈夫曼树算法实现 HUFFMAN(hufmtree tree )int i, j, p; char ch; float small1, small2, f; for( i=0; im; i+) /* 初始化 */ treei.parent=0; t

41、reei.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; 算法的基本思想10/12/202262构造哈夫曼树算法实现 HUFFMAN(hufmtree for( i=n; im ;i+ ) / 进行n-1次合并，产生n-1个新结点 p1=p2=0; / 记录权值最小、次最小的结点下标 small1=small2=Maxval

42、; /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

43、.lchild=p1;/ 给新生成的结点的左右孩子域赋值 treei.rchild=p2; treei.weight =treep1.weight+treep2.weight;/给新生成的结点的权值域赋值 /* HUFFMAN */算法的基本思想10/12/202263 for( i=n; im ;i+ ) / 进构造哈夫曼树算法的基本思想：对m=2n-1个结点初始化，将双亲域，左、右孩子域，权值，结点值置0；输入n个叶子结点的权值和结点值；循环体执行n-1次，进行n-1次合并，产生n-1个新结点：在i个结点中找出两个双亲域为0（即没有被合并的结点）且权值最小的结点，p1指示权值最小的结点，p

44、2指示权值次最小的结点；将两棵根结点权值最小的二叉树进行合并： treep1.parent=i; /i为新结点，即新产生的双亲结点treep2.parent=i; treei.lchild=p1; /新产生的双亲结点指向左、右子树的根结点 treei.rchild=p2; treei.weight = treep1.weight+treep2.weight; /新结点的权值是左、右子树根结点权值之和。10/12/202264构造哈夫曼树算法的基本思想：10/10/202264哈夫曼编码的数据结构编码数组结构描述如下：typedef char datatype;typedef struct ch

45、ar bitsn; /编码数组位串，其中n为叶子结 点数目 int start; /编码在位串的起始位置 datatype data; /结点值 codetype;codetype coden;一个字符的哈夫曼编码在数组bits中从高位到低位顺序存储。10/12/202265哈夫曼编码的数据结构编码数组结构描述如下：typedef 哈夫曼编码的算法的基本思想 从叶子到根逆向求哈夫曼编码 从叶子treei出发，利用双亲地址找到双亲结点treep，再利用treep的lchild和rchild指针域判断treei是treep的左孩子还是右孩子，然后决定分配代码的 0 还是代码 1 , 然后以tree

46、p为出发点继续向上回溯，直到根结点为止。10/12/202266哈夫曼编码的算法的基本思想 从叶子到根逆向求哈夫曼编码哈夫曼编码算法实现void HUFFMANCODE(codetype code ，hufmtree tree )/code 存放求出的哈夫曼编码的数组， tree已知的哈夫曼树 int i, c, p; codetype cd; / 缓冲变量 for ( i=0; in; i+ ) /n为叶子结点数目 ，循环产生n个字符的哈夫曼编码 cd. start=n; /从叶子结点出发向上回溯 ，在bits中， 从高位开始存储 c=i; /c指示第i个叶子结点 p=treec.paren

47、t; /p指示结点c的双亲结点 cd.data=treec.data; /对结点数据域赋值 10/12/202267哈夫曼编码算法实现void HUFFMANCODE(cod 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指示 p=treec.parent; /p指示结点c的双亲结点 codei=cd; /一个字符的编码存

48、入codei /for_end / HUFFMANCODE10/12/202268 while( p!=0 ) /c指示到根结点时，p哈夫曼编码结果对下图所示的哈夫曼树进行编码，可得到下表所示的编码表。code下标bitsstartdata0123003a11101b2102c31111d10/12/202269哈夫曼编码结果对下图所示的哈夫曼树进行编码，可得到下表所示的哈夫曼树译码定义：哈夫曼树译码是指由给定的代码求出代码所表示的结点值。译码的过程是：从根结点出发，逐个读入电文中的二进制代码；若代码为0则走向左孩子，否则走向右孩子；一旦到达叶子结点，便可译出代码所对应的字符。然后又重新从根结

49、点开始继续译码，直到二进制电文结束。10/12/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 i=treei.rc

50、hild; /* 走向右孩子 */ 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的结点，所以treei是叶子结

51、点。10/12/202271哈夫曼树译码算法void HUFFMANDECODE(co6.7.2 二叉排序树二叉排序树的概念： 二叉排序树或者是一棵空树，或者是具有下列性质的二叉树： 每个结点都有一个关键字(key)，所有结点的关键字互不相同。 左子树(若非空)上所有结点的关键字都小于根结点的关键字。 右子树(若非空)上所有结点的关键字都大于根结点的关键字。 左子树和右子树也是二叉排序树。10/12/2022726.7.2 二叉排序树10/10/202272 如果对一棵二叉排序树进行LDR遍历，可以按从小到大的顺序，将各结点关键字排列起来。如果对一棵二叉排序树进行RDL遍历，可以按从大到小的顺

52、序，将各结点关键字排列起来。几个二叉排序树的例子10/12/202273 几个二叉排序树的例子10/10/202273二叉排序树的数据结构二叉排序树的二叉链表存储结构结点结构描述如下：typedef int keytype;typedef struct keytype key; /关键字项 datatype other; / 其它数据项 struct node *lchild, *rchild; /左、右指针域 bstnode;10/12/202274二叉排序树的数据结构二叉排序树的二叉链表存储结构结点结构描述二叉排序树的构造构造一棵二叉排序树，就是从空的二叉排序树开始，逐个结点插入到二叉排序

53、树中。对于一组数据元素 R1, R2, , Rn , 可按以下方法来构造二叉排序树：(1) 令R1为二叉树的根;(2) 若R2R1, 令R2为R1左子树的根结点，否则R2为R1右子树的根结点；(3) 对R3, , Rn结点也是依次与前面生成的结点比较以确定结点的位置。说明：每次插入的新结点都是当前二叉树的叶子结点 给定的关键字序列不同，二叉排序树的形态则不同 二叉排序树中不存在两个结点的关键字相同的结点10/12/202275二叉排序树的构造构造一棵二叉排序树，就是从空的二叉排序树开始例：给定关键字序列10、18、3、8、12、2、7、3，建立二叉排序树。10/12/202276例：给定关键字序列10、18、3、8、12、2、7、3，建立（1）将指针