第6章 树.ppt

1、第六章 树和二叉树,树的概念和基本术语 二叉树 及其性质 二叉树的存储 二叉树遍历 二叉树的算法 树与森林 霍夫曼树,6.1 树的定义和基本术语,树(Tree)是n(n0)个结点的有限集。在任意一棵非空树中： 如果n = 0，称为空树； 当n=1时，T是一棵只有一个结点的树; 如果n 1，则 (1) 有且仅有一个特定的称为根(Root)的结点； (2) 当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。,非树结构的示例：,A,C,B,E,D,F,A,只有根结点的树,有13个结点的树,其中：A是根；其余结点分成

2、三个互不相交的子集， T1=B ,E ,F ,K ,L ； T2= C, G ； T3=D, H, I, J, M T1,T2,T3都是根A的子树,树的基本术语,1层,2层,4层,3层,A,C,G,B,D,E,F,K,L,H,M,I,J,结点 结点的度 叶结点 分支结点,孩子 双亲 兄弟 堂兄弟,祖先 子孙 结点层次,树的深度 树的度 有序树 无序树 森林,结点：一个数据元素及指向其子树的分支。 结点的度：结点拥有的子树个数。 叶结点：度为零的结点。 子女：结点子树的根。 兄弟：同一结点子女。 祖先：根到该结点路径上的所有结点。 子孙：某结点为根的子树上的任意结点。 结点层次：从根开始，根为第

3、一层，根的子女为第二层，以此类推。 树的深度（高度）：树中结点的最大层次数。 有序树：树中结点的子树由左向右有序。 森林：m(m 0)棵互不相交的树。,1有一棵树如图示，回答下面问题：,(1)这棵树的根结点是( )； (2)这棵树的叶子结点是( )； (3)结点 C 的度是( )； (4)这棵树的度是( )；,(5)这棵树的深度是( )； (6)结点 C 的孩子是( ),子孙是( ); (7)结点 F 的父亲是( )，祖先是( )。,2. 图示方法： 表示方法的多样化，说明了树结构在日常生活中及计算机程序设计中的重要性。,（1）结点-分支 方式,B,E,F,K,L,（2）文氏图（嵌套集合）,(

4、3)是以广义表的形式表示的，根作为由子树组成的表的名字写在表的最左边； (A(B(E(K , L) , F) , C(G) ,D(H(M) , I , J) 一般说来，分等级的分类方案都可 用层次结构来表示，也就是说，都可导 致一个树结构。,A,C,G,B,D,I,F,E,J,H,L,K,M,树型结构与线性结构的比较,6.2 二叉树,1. 定义,2. 五种形态,树的度不大于2的有序树.,特点,每个结点至多只有两棵子树（二叉树中 不存在度大于2的结点） 子树有左右之分 二叉树可以为空,二叉树是有序树，这些树，是不同的二叉树。,A,B,C,D,F,E,G,H,A,B,A,B,A,B,C,D,F,E

5、,G,H,具有三个结点的二叉树,height=3,height=2,具有四个结点的二叉树,height=3,height=4,一般二叉树可视为： D:根结点 L:左子树 R:右子树 其所有子树的结构也是如此。,在一棵树T中，若所有结点的L均不存在，则此树为右歪斜树right skewed binary tree或右单支树，反之，所有结点的R均不存在，则此树为左歪斜树left skewed binary tree或左单支树。,D,L,R,eg.设高为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( ? )，至多为( ? ) H=1 1 H=2 2 H=3 2*2 H=4

6、 2*2*2 ,2h-1,20+21+2i-1+2h-1,第1层,第2层,第3层,第4层,20,21,22,23,第i层,2i-1,性质1 在二叉树的第 i 层上至多有 2i 1个结点。(i 1) 证明用归纳法,3.性质,证明：当i=1时，只有根结点，2 i-1=2 0=1。 假设对所有j，ij1，命题成立，即第j层上至多有2 j-1 个结点。 由归纳假设第i-1 层上至多有 2i 2个结点。 由于二叉树的每个结点的度至多为2，故在第i层上的最大结点数为第i-1层上的最大结点数的2倍，即2* 2i 2= 2 i-1。,性质2 深度为 k 的二叉树至多有 2k -1个结点(k 1)。 证明：由性

7、质1可见，深度为k的二叉树的最大结点数为,k k (第i层上的最大结点数) =(2的(i-1)次方) i=1 i=1 20 + 21 + + 2k-1 = 2k -1,性质3 对任何一棵二叉树T, 如果其叶结点数为 n0, 度为2的结点数为 n2,则n0n21.,1,2,3,4,5,6,7,9,11,13,14,总分支数 : 前驱:n0+n1+n2-1 后继:0*n0+1*n1+2*n2,定义1 满二叉树 一棵深度为k且有2k -1个结点的二叉树称为满二叉树。,两种特殊形态的二叉树,满二叉树,非完全二叉树,定义2 完全二叉树 若设二叉树的高度为h，则共有h层。除第 h 层外，其它各层 (1 h

8、-1 ) 的结点数都达到最大个数，第 h 层 从右向左 连续缺若干结点，这就是完全二叉树。,完全二叉树,完全二叉树的特点是： (1)叶子结点只可能出现在层次最大的两层上； (2)对任意结点，若其右分支下的子孙最大层次为L，则其左分支下的子孙的最大层次必为L或L+1。,性质4 具有 n (n 0) 个结点的完全二叉树的深度为 log2(n) 1 证明： 设完全二叉树的深度为 h，则根据性质2和完全二叉树的定义有 2h1 - 1 n 2h - 1或 2h1 n 2h 取对数 h1 log2n h，又h是整数， 因此有 h = log2(n) 1,性质5 如将一棵有n个结点的完全二叉树自顶向下，同一

9、层自左向右连续给结点编号1, 2, 3, , n，则有以下关系： 若i = 1, 则 i 无双亲 若i 1, 则 i 的双亲为 i /2 当2*i n 则i 必是叶子 当2*i = n 则左孩子序号必是 2i 若2*i = n, 则 i 的左子女为 2*i，若2*i+1 =n, 则i 的 右子女为2*i+1 若结点编号i为奇数，且i!=1,则左兄弟结点i-1. 若结点编号i为偶数，且i!=n,则右兄弟结点为i+1. 结点i 所在层次为log2(i+1) ,1,8,2,3,4,5,6,7,9,10,i,2i+1,2i,第h-1层,第h层,2h-1-1,2h-1,2h-1+1,2h-1, ,2h-

10、2,2h-2-1,2h-2,i=2h-2,2h-3,完全二叉树 的顺序表示,4. 二叉树的存储结构,(1)顺序表示,一般二叉树 的顺序表示,31,23,12,66,05,17,62,70,1,2,4,11,6,7,8,9,10,12,5,88,13,14,55,15,1,2,3,4,5,6,7,8,31,23,12,66,05,17,70,9,10,11,12,62,3,13,14,15,88,55,练习:,将此二叉树进行顺序存储, 写出存储区 ?,35,右单支树,在最坏的情况下，一个深度为k且只有k个结点的单支树(树中不存在度为2 的结点)却需要长度为2k-1的一维数组。,31,12,17,

11、88,1,3,7,15,1,2,3,4,5,6,7,8,31,12,17,9,10,11,12,13,14,15,88,31,12,17,1,2,4,11,6,7,8,9,10,12,5,13,14,88,15,3,/二叉树的顺序存储表示 const int MAXSIZE 100 /二叉树的最大结点数 typedef ElemType SqBiTree MAXSIZE ; /0号单元存储根结点 SqBiTree tree；,(2) 链式表示,二叉链表,含两个指针域的结点结构,含三个指针域的结点结构,三叉链表,二叉树链表表示的示例,A,A,B,B,C,C,D,D,F,F,E,E,root,ro

12、ot,二叉树 二叉链表,三叉链表,typedef struct node char data; struct node * lChild ; struct node * rchild; * BiTree ; /指向根的指针,二叉链表的定义,性质： 含有n个结点的二叉链表中有n+1个空链域。,三叉链表的空域数呢?,40,在含有n个结点的二叉链表中有 个空链域。 在含有n个结点的二叉链表中有 个链域。 在含有n个结点的二叉链表中有 个非空链域。 空链域个数：2n0+n1 n0=n2+1 n-1=2n2+n1 n0+n1+n2=n,在6.3节中，利用这些空链与存储其它有用信息，从而得到另一种链式存储

13、结构线索链表。,2n0+n1=n+1,n+1,2n,n-1,2n2+n1,6.3 二叉树遍历,树的遍历就是按某种次序访问树中的结点，要求每个结点访问一次且仅访问一次。,设访问根结点记作 D 遍历根的左子树记作 L 遍历根的右子树记作 R 则可能的遍历次序有 前序 DLR 中序 LDR 后序 LRD,先序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 (1)访问根结点； (2)先序遍历左子树； (3)先序遍历右子树。,中序遍历二叉树的操作定义为： 若二叉树为空，则空操作；否则 (1)中序遍历左子树； (2)访问根结点； (3)中序遍历右子树。 后序遍历二叉树的操作定义为： 若二叉树为空，

14、则空操作；否则 (1)后序遍历左子树； (2)后序遍历右子树； (3)访问根结点。,前序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 访问根结点 (D)； 前序遍历左子树 (L)； 前序遍历右子树 (R)。 遍历结果 A B D E F G C,1.前序遍历 (Preorder Traversal),遍历结果 - + a * b - c d / e f,1.前序遍历 (Preorder Traversal),求出:下面二叉树经过前序遍历得到的相应序列,A,B,C,D,E,F,H,G,前序遍历二叉树的递归算法,void PreOrder ( BiTree T ) if ( T != N

15、ULL ) coutdata ; PreOrder ( T-lChild ); PreOrder ( T-rChild ); ,中序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 中序遍历左子树 (L)； 访问根结点 (D)； 中序遍历右子树 (R)。 遍历结果 D B F E G A C,2. 中序遍历 (Inorder Traversal),遍历结果 a + b * c - d - e / f,2. 中序遍历 (Inorder Traversal),对一棵二叉树中序遍历时，若我们将二叉树严格地按左子树的所有结点位于根结点的左侧，右子树的所有结点位于根右侧的形式绘制，就可以对每个结点

16、做一条垂线，映射到下面的水平线上，由此得到的顺序就是该二叉树的中序遍历序列。,A,B,C,D,G,E,F,H,D G B A E C H G,求出:下面二叉树经过中序遍历得到的相应序列,A,B,C,D,E,F,H,G,void InOrder ( BiTree T ) if ( T != NULL ) InOrder ( T-lChild ); coutdata ; InOrder ( T-rChild ); ,中序遍历二叉树的递归算法,后序遍历二叉树算法的定义： 若二叉树为空，则空操作； 否则 后序遍历左子树 (L)； 后序遍历右子树 (R)； 访问根结点 (D)。 遍历结果 D F G E

17、 B C A,3 后序遍历 (Postorder Traversal),遍历结果 a b c d - * + e f / -,3 后序遍历 (Postorder Traversal),后序遍历二叉树的递归算法：,void PostOrder ( BiTree T ) if ( T != NULL ) PostOrder ( T-lChild ); PostOrder ( T-rChild ); coutdata ; ,求出:下面二叉树经过后序遍历得到的相应序列,A,B,C,D,E,F,H,G,以先序遍历为例： void PreOrder (BiTree T) if (T) cout data

18、; PreOrder (T-lchild); PreOrder (T-rchild); ,A,B,C,D,E,F,H,G,A,B,C,D,E,F,H,G,B,D,G,NULL,D,NULL,G,C,E,F,H,F,H,NULL,G,NULL,NULL,NULL,NULL,H,E,NULL,NULL,HBDF,EKCG,A,(1)取A,EKCG,A,(2)取B,B,H,DF,EKCG,A,(3)取H,B,DF,H,由二叉树的前(后)序序列和中序序列可唯一地确定一棵二叉树。 例, 前序序列 ABHFDECKG 和中序序列 HBDFAEKCG , 构造二叉树过程如下：,二叉树的构造,EKCG,A,(

19、4)取F,B,D,H,F,EKCG,A,(5)取D,B,H,F,D,KCG,A,(6)取E,B,H,F,D,E,先序序列 ABH FDECKG 中序序列 HB DF AEKCG,K,A,(7)取C,B,H,F,D,E,C,G,A,(8)取K,B,H,F,D,E,C,G,A,(9)取G,B,H,F,D,E,C,K,K,G,先序序列 ABHFDECKG 中序序列 HBDFAEKCG,前序序列 ABHFDECKG 中序序列 HBDFAEKCG ,EKCG,A,B,H,DF,E,A,B,H,F,D,C,K,G,前序序列 ABHFDECKG ,后序序列 DFEBCA 中序序列 DBEFAC ,已经如下信

20、息，请构造唯一形态的二叉树：,如果前序序列固定不变，给出不同的中序序列，可得到不同的二叉树。,6,1,2,3,4,5,7,8,9,6,1,2,3,7,5,8,4,9,固定前序排列,选择所有可能的中序排列,可以构造多少种不同的二叉树？,例如, 有 3 个数据 1, 2, 3 ，可得 5 种不同的二叉树。它们的前序排列均为 123，中序序列可能是 321 ， 231， 213， 132，123.,有1个, 2个, 3个结点的不同二叉树如下,b1 =1,b2 =2,b3 =5,计算具有 n 个结点的不同二叉树的棵数,最终结果：,bi,bn-i-1,1,4 二叉树相关的操作,以递归方式建立二叉树。 输

21、入结点值的顺序必须对应二叉树结点前序遍历的顺序。并约定以输入序列中不可能出现的值作为空结点的值以结束递归, 例如用“”或用“0”表示字符序列或正整数序列空结点。,(1 ) 按前序建立二叉树(递归算法),如图所示的二叉树的前序遍历顺序为 A B C D E G F ,A,B,C,D,E,G,F,Status CreateBiTree ( BiTree ,int Count ( BiTree T ) if ( T = NULL ) return 0; else return 1 + Count ( T-lChild ) + Count ( T-rChild ) ; ,(2)计算二叉树结点个数 (递

22、归算法),int Height ( BiTree T ) if ( T = NULL ) return 0; else int m = Height ( T-lChild ); int n = Height ( T-rChild ) ); return (m n) ? m+1 : n+1; ,(3)求二叉树高度(递归算法),练习:交换二叉树各结点的左、右子树(递归算法),void exchange ( BiTree T ) BiTree temp, p = T, ; if ( p ! = NULL ) temp = p-lChild; p-lChild = p-rChild; p-rChild

23、 = temp; exchange ( p-lChild ); exchange ( p-rChild ); ,1 树的存储结构,6.5 树与森林,(1)双亲表示：以一组连续空间存储树的结点，同时在结点中附设一个指针，存放双亲结点在链表中的位置。该方法利用每个结点只有一个双亲的特点，可以很方便求结点的双亲，但不方便求结点的孩子。,80,A,C,B,D,F,E,I,H,J,G,L,K,M,下标 info parent,A,0,1 2 3 4 5 6 7 8 9 10 11 12 13,B,1,C,1,D,1,E,2,F,2,G,3,H,4,I,4,J,4,K,7,L,7,M,10,(a)树,(b

24、)双亲表示数组,(c)双亲表示图解,A,C,B,D,F,E,I,H,J,G,L,K,M,用双亲表示实现的树定义,#define MaxSize100 /最大结点个数 typedef char Elemtype ; /结点数据 typedef struct /树结点定义 Elemtype data; int parent; TreeNode ; TreeNode node MaxSize ; /树,82,算法实现举例： int Parent( TreeNode T， int i ) if( i MaxSize ) return ERROR; else return T.nodesi.parent

25、; ,83,如何找孩子结点,特点：找双亲容易，找孩子难 求结点的孩子要遍历整个结构。,(2)孩子表示法(多重链表 ),第一种解决方案 等数量的链域 (d为树的度),data,child1,child2,child3,childd,A,B,C,D,E,F,G, , , , , ,第二种解决方案 孩子链表,将每个结点的孩子链在该结点之后组成链表，再将所有头结点组成一个线性表,86,如何找双亲结点,87,这种存储结构的特点: 是寻找某个结点的孩子比较容易，但寻找双亲比较麻烦，所以，在必要的时候，可以将双亲表示法和孩子表示法结合起来，即将一维数组元素增加一个表示双亲结点的域parent，用来指示结点的

26、双亲在一维数组中的位置。,89,练习: 构造带双亲的孩子链表,结点结构,(3)孩子-兄弟表示,firstchild,data,nextsibling,右边树的孩子兄弟表示,typedef char Elemtype ; typedef struct node Elemtype data; struct node *firstChild, *firstBrother; *TreeNode; TreeNode Tree;,用左子女-右兄弟表示实现的树定义,93,A,C,B,D,F,E,I,H,J,G,L,K,M,94,树的左孩子-右兄弟表示,A,B,E,C,D,K,F,G,L,H,I,J,M,95

27、,t,（1）树 二叉树:,方法：保留与左子结点的链接 横向链接右兄弟断开与右子的链接将兄弟结点顺时针转 45 o,树、森林与二叉树的转换,树转换为二叉树的示例,A,C,D,I,B,F,E,J,H,G,A,C,D,I,B,F,E,J,H,G,对应,T1 T2 T3,T1 T2 T3,3 棵树的森林,各棵树的二叉树表示,森林的二叉树表示,（2）森林 二叉树:,树与二叉树对应,树根连接,课堂作业：,A,C,D,I,B,F,E,J,H,G,a,c,d,b,e,f,g,i,h,B,C,D,E,F,G,I,H,J,K,L,M,1.将下面这棵树转换成二叉树。,2.将下面的森林转换成二叉树。,3.下面这棵二叉

28、树还原。,树和森林的遍历,树 先根次序遍历 后根次序遍历,当树非空时 访问根结点； 依次先根遍历根的各棵 子树；,树的先根次序遍历,树先根遍历 ABEFCDG 对应二叉树前序遍历 ABEFCDG 树的先根遍历结果与其对应二叉树 表示的前序遍历结果相同 树的先根遍历可以借助对应二叉树的前序遍历算法实现,树的后根次序遍历:,当树非空时 依次后根遍历根的各棵 子树 访问根结点,树后根遍历 EFBCGDA 对应二叉树中序遍历 EFBCGDA 树的后根遍历结果与其对应二叉树 表示的中序遍历结果相同 树的后根遍历可以借助对应二叉树的中序遍历算法实现,106,A,B,C,D,E,F,G,I,H,J,K,L,

29、M,先根遍历:A BEF CGKL DHIJM,后根遍历:EFB KLGC HIMJD A,A,B,C,D,E,F,G,I,H,J,K,L,M,先序遍历:A BEF CGKL DHIJM,中序遍历:EFB KLGC HIMJD A,后根遍历:FEB LKG MJIHDC A,一、先序（先根）遍历森林 若森林非空，则可按下述规则遍历之： (1)访问森林中第一棵树的根结点； (2)先序遍历第一棵树中根结点的子树森林； (3)先序遍历除去第一棵树之后剩余的树构成的森林。 二、后序（后根）遍历森林 若森林非空，则可按下述规则遍历之： (1)后序遍历森林中第一棵树的根结点的子树森林； (2)访问第一棵树

30、的根结点； (3)后序遍历除去第一棵树之后剩余的树构成的森林。,森林 先序次序遍历 中序次序遍历,108,4. 广度优先遍历(层次序遍历) ： (1)若森林F为空，返回； (2)否则 a.依次遍历各棵树的根结点； b.依次遍历各棵树根结点的所有孩子； c.依次遍历这些孩子结点的孩子结点。,A,B,C,D,E,F,G,I,H,J,K,L,M,ACD BGHIJ EFKLM,109,A,B,C,D,E,F,G,I,H,J,K,L,M,层次遍历: A B EC FGD KH LI J M,森林对应的二叉树：,6.6 哈夫曼树及其应用,哈夫曼(Huffman)树，又称最优树，是一类带权路径长度最短的树

31、。,David Huffman 戴维 哈夫曼,对于学过数据结构的人来说，Huffman这个名字应该不会陌生吧。David Huffman教授1999年10月7日逝世。在他的一生中，他对于有限状态自动机，开关电路，异步过程和信号设计有杰出的贡献。但是我们只是通过数据结构中的Huffman编码才了解这位杰出的科学家的。他发明的Huffman编码能够使我们通常的数据传输数量减少到最小。这个编码的发明和这个算法一样十分引人入胜。1950年，Huffman在MIT的信息理论与编码研究生班学习。Robert Fano教授让学生们自己决定是参加期未考试还是做一个大作业。而Huffman选择了后者，原因很简单

32、，因为解决一个大作业可能比期未考试更容易通过。这个大作业促使了Huffman以后算法的诞生。离开MIT后，Huffman来到University of California的计算机系任教，并为此系的学术做出了许多杰出的工作。而他的算法也广泛应用于传真机，图象压缩和计算机安全领域。但是Huffman却从未为此算法申请过专利或其它相关能够为他带来经济利益的东西，他将他全部的精力放在教学上，以他自己的话来说，“我所要带来的就是我的学生。”,1 最佳判定树,考试成绩分布表,假设输入100个数,判定树,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.

33、15,比较次数 = 10*1+15*2+25*3+35*4+15*4 = 315 次,最佳判定树,不及格,及格,中,良,优,60?,70?,80?,90?,0.10,0.15,0.25,0.35,0.15,比较次数 = 10*3+15*3+ 25*2+ 35*2+ 15*2 = 3+ 45+ 5+ 7+ 3 = 225 次,C,B,A,E,D,if(socre80) if(score70) if(score60) cout “E” ; else cout “D” ; else cout “C” ; else if(socre90) cout “B” ;else cout “A” ;,2 哈夫曼

34、树 (Huffman Tree),路径长度: 两个结点之间的路径长度 L 是连接两 结点的路径上的分支数。 权: 树上结点所代表的一个有意义的实数值.,最优判定性能二叉树,带权路径长度 (Weighted Path Length, WPL) 二叉树的带权 路径长度是 树的各叶结点所带的权值 wi 该结点到根的路径长度 li 的乘积的和。,WPL = 2*2+ WPL = 2*1+ WPL = 7*1+ 4*2+5*2+ 4*2+5*3+ 5*2+2*3+ 7*2 = 36 7*3 = 46 4*3 = 35,带权路径WPL 长度达到最小,说明: 叶子上的权值均相同时，完全二叉树一定是最优二叉树

35、，否则完全二叉树不一定是最优二叉树。 最优二叉树中，权越大的叶子离根越近。 最优二叉树的形态不唯一，WPL最小, 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树上根结点的权值之和。 在 F 中删去这两棵二叉树。 把新的二叉树加入 F。,构造方法:,F : 7 5 2 4,F : 7 5 6,F : 7 11,7,5,2,4,初始,合并2 4,F : 18,11,7,5,2,4,6,合并5 6,5,合并7 11,2,7,4,6,11,18,哈夫曼树的构造过程,7，19，2，6，32，3，21，10,赫夫曼树的构造过程:

36、,8 个权值：,7,19,2,6,32,3,21,10,7,19,2,6,32,3,21,10,2,3,2,3,5,7,19,6,32,21,10,2,3,5,6,5,2,3,5,6,11,7,19,32,21,10,2,3,5,6,11,7,10,7,10,17,19,32,21,2,3,5,6,11,7,10,17,11,17,2,3,5,6,11,7,10,17,28,19,32,21,2,3,5,6,11,7,10,17,28,19,21,19,21,40,32,2,3,5,6,11,7,10,17,28,19,21,40,32,40,32,19,21,40,72,2,3,5,6,11

37、,7,10,17,28,32,19,21,40,72,28,72,100,a,b,c,d,e,3 7 5 9 6,小练习:,注意： 初始森林中的n棵二叉树，每棵树有一个孤立的结点，它们既是根，又是叶子。n个叶子的哈夫曼树要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树中共有2n-1个结点，结点的度要么为0，要么为2。,2n0-1=n,n0+n1+n2=n n0=n2+1 n1=0,131,哈夫曼树是严格的(strict，或正则的)二叉树，没有度数为1的分支结点。,6.7 霍夫曼编码,主要用途是实现数据压缩。,(1)等长编码方案 【例】设待压缩的数据文件共有100个字符，这些字符均取自

38、字符集C=a，b，c，d，e，f ，等长编码需要三位二进制数字来表示六个字符，因此，整个文件的编码长度为300位。,133,C =a，b，c，d，e，f 则字符串efbacd可译为 100101001000010011 对方接受时，可按三位一分进行译码，即 e f b a c d 100，101，001，000，010，011,134,当然，在进行电文传送时，希望电文总长尽可能短，即传送时间尽可能短。如果对每个字符设计长度不等的编码，且让电文中出现次数较多的字符采用尽可能短的编码，则传送长度便可减少。,(2)变长编码方案 变长编码方案将频度高的字符编码设置短，将频度低的字符编码设置较长。【例】

39、设待压缩的数据文件共有100个字符，这些字符均取自字符集C=a，b，c，d，e，f，其中每个字符在文件中出现的次数(简称频度)如下：,135,-字符a b c d e f频度 45 13 12 16 9 5定长编码000001010 011100 101变长编码0 110 100 111 1101 1100- 1X45+3X13+3X12+3X16+4X9+4X5=224,136,注意： 变长编码可能使解码(译码)产生二义性。产生该问题的原因是某些字符的编码可能与其他字符的编码开始部分(称为前缀)相同。【例】设a、b、f分别编码为 0 、110、1100 ，则解码时无法确定信息串1100是ba

40、还是f。,137,(3)前缀码方案 对字符集进行编码时，要求字符集中任一字符的编码都不是其它字符的编码的前缀，这种编码称为前缀(编)码。,利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。 具体做法： (1)用字符ci作为叶子，pi做为叶子ci的权，构造一棵哈夫曼树，并将树中左分支和右分支分别标记为0和1；(2)将从根到叶子的路径上的标号依次相连，作为该叶子所表示字符的编码。该编码即为最优前缀码(也称哈夫曼编码)。,138,假设有一个电文字符集中有8个字符a，b，c，d，e，f，g，h，每个字符的使用频率分别为0.05，0.29，0.07，0.08，0.14，0.23，0.0

41、3，0.11，现以此为例设计哈夫曼编码。哈夫曼编码设计过程为：(1)为方便计算，将所有字符的频度乘以100，使其转换成整型数值集合，得到5，29，7，8，14，23，3，11；(2)以此集合中的数值作为叶子结点的权值构造一棵哈夫曼树，如图所示；(3)由此哈夫曼树生成哈夫曼编码，如图所示。,139,字符,字符的使用频率,编码,a,b,c,d,e,f,g,h,0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,0111,10,1110,1111,110,00,0110,010,a,c,h,e,f,g,8,b,5,29,7,11,14,23,3,d,15,19,29,42

42、,58,100,00,010,011,10,110,1110,1111,0110,0111,8,0,1,01,11,111,140,比如，发送一段编码：0000011011010010 接收方可以准确地通过译码得到：ffgebh(00，00，0110，110，10，010)。,最后得出每个字符的编码为： a0111，b10，c1110，d1111， e110， f00，g0110，h010,141,假设一串待译码的字符串总长为100 电文总长为：5*4+29*2+7*4+8*4+14*3+23*2+3*4+11*3=,字符,字符的使用频率,编码,a,b,c,d,e,f,g,h,0.05,0.2

43、9,0.07,0.08,0.14,0.23,0.03,0.11,0111,10,1110,1111,110,00,0110,010,路径长度,权值,电文总长=对应的Huffman树的带权路径长度,142,例:设给出一段报文： CAST CAST SAT AT A TASA 字符集合是 C, A, S, T ，各个字符出现的频度(次数)是 W 2, 7, 4, 5 。,CAST CAST SAT AT A TASA A : 0 T : 10 C : 110 S : 111 它的总编码长度：7*1+5*2+( 2+4 )*3 = 35。比等长编码的情形要短。 总编码长度正好等于霍夫 曼树的带权路径

44、长度WPL。 霍夫曼编码是一种无前缀 编码(都由叶结点组成,路径 不会重复)。解码时不会混淆。 霍夫曼编码: A : 0 T : 10 C : 110 S : 111 110011110 11001111011101001001001110 等长编码: A : 00 T : 10 C : 01 S : 11 010011100100111011001000100010001100,霍夫曼编码树,144,学习提要 1.熟练掌握二叉树的结构特性，了解相应的证明方法。2.熟悉二叉树的各种存储结构的特点及适用范围。3.熟练掌握各种遍历策略的递归和非递归算法。4.熟练掌握二叉树的线索化过程以及在中序线索

45、化树上找给定结点的前驱和后继的方法。5.熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。6.了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。,复 习,本章是课程的重点内容之一。 1、知识点 1.1 二叉树的定义、性质和存储结构； 1.2 二叉树的遍历和线索化以及遍历算法算法的各种描述形式； 1.3 树和森林的定义、存储结构与二叉树的转换、遍历； 1.4 最优二叉树（哈夫曼树）的特性、构成和运用。,2、内容精要 2.1 树的概念和定义 树是以分支关系定义的层次结构。 树(Tree)是n(n0)个结点的有限集。在任意一棵非空树中： (1)有且仅有一个特定的称为根(Root)的结点

46、； (2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1，T2，Tm，其中每一个集合本身又是一棵树，并且称为根的子树(SubTree)。,2.2 树的特性及表示方式 树的结构定义是一个递归的定义，即在树的定义中又用到树的概念，它道出了树的固有特性。 树是以分支关系定义的层次结构。 树中除根结点外其它结点都由一个分支引入，而每个结点可有至多个分支，因此树中除根结点无前趋结点外，其它结点都只有一个直接前趋结点，但可有至多个直接后继结点。显然数是一种非线性的结构。 树有多种表示形式，如：树形表示法、嵌套集合表示法、凹入式表示法、广义表表示法。,.3 树的相关术语 结点结点的度树的度 叶子结

47、点双亲结点孩子结点兄弟结点 树的深度（高度）路径路径长度树的路径长度 祖先结点子孙结点 有序树森林,2.4 二叉树的定义和它的五种形态 二叉树(BinaryTree)是一种树型结构，它的特点是每个结点至多只有二棵子树(即二叉树中不存在度大于2的结点)，并且，二叉树的子树有左右之分，其次序不能任意颠倒。 五种形态为空二叉树、只有一个根结点的二叉树、右子树为空的二叉树、左子树为空的二叉树、左右子树非空的二叉树。,2.5 二叉树的性质 熟练掌握二叉树的结构特性，掌握完全二叉树和满二叉树的定义，了解相应的证明方法。 性质1 在二叉树的第i层上至多有2i-1个结点(i1)。 性质2 深度为k的二叉树至多

48、有2k-1个结点，(k1)。 性质3 对任何一棵二叉树T，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。 性质4 具有n个结点的完全二叉树的深度为 log2n +1。 性质5 如果对一棵有n个结点的完全二叉树(其深度为log2n+1)的结点按层序编号(从第1层到第log2n+1层，每层从左到右)，则对任一结点i(1in)，有 (1)如果i=1，则结点i是二叉树的根，无双亲；如果i1，则其双亲PARENT(i)是结点 i/2 。 (2)如果2in，则结点i无左孩子(结点i为叶子结点)；否则其左孩子LCHILD(i)是结点2i。 (3)如果2i+1n，则结点i无右孩子；否则其右孩

49、子RCHILD(i)是结点2i+1。,2.6 二叉树的存储结构 熟悉二叉树的各种存储结构的特点及适用范围。 1、顺序存储 按照顺序存储结构的定义，用一组地址连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为i的结点元素存储在如上定义的一维数组中下标为i-l的分量中。 优点：存储结构简单 缺点：深度为k的二叉树需2k-1个存储单元，空间利用率低。 2、二叉链表存储结构 设计不同的结点结构可构成不同形式的链式存储结构。 这种存储结构的优点是访问结点的孩子很方便。且空间利用率高。,2.7 遍历二叉树和线索二叉树 遍历二叉树是二叉树各种操作的基础。实现二叉树遍历的各种算法与所采用的存储结构有关