第五章二叉树及应用.ppt

《第五章二叉树及应用.ppt》由会员分享，可在线阅读，更多相关《第五章二叉树及应用.ppt（82页珍藏版）》请在三一文库上搜索。

1、第五章 二叉树及应用,一种重要的非线性结构,学习要点：,二叉树的递归概念，这与二叉树各种基本运算具有密切关联。 满二叉树和完全二叉树概念，二叉树和完全二叉树基本性质。 二叉树的顺序存储与二叉链表存储结构。 二叉树遍历的基本思想和基于递归与非递归实现算法。 线索二叉树概念，二叉树的线索化和遍历。 Huffman树概念与基本算法；Huffman编码和实现算法。,2,5.1 二叉树及其基本性质,5.1.1 二叉树基本概念 “二叉树”是一个满足下述条件的由结点组成的有限集合E： 当E为空集时，定义其为空二叉树； 当E非空时，分为两种情形。 如果E为单元素集合，定义其为一棵根二叉树； 如果E为多于一个结

2、点的集合，则E中应当具有唯一一个结点r称其为根结点，而集合E=E r也是一棵二叉树，称为r的子二叉树。此时，结点r至多只能有两棵不相交的子二叉树，并且相应子二叉树有左右之分，分别称为r的左子树和右子树。,3,其它一些相关概念：,结点的度：结点拥有的子树棵数 结点的深度（层次）：根结点看做第0层，其余结点的层次值为其父结点所在层值加1 树的度：树中所有结点度的最大值 树的深度：树中最大层次数,4,根结点、叶结点、内部结点,子结点、父结点、兄弟结点、堂兄弟结点、 子孙结点、祖先结点；,5.1.1 二叉树基本概念2,1、二叉树的特征 二叉树可以没有任何结点，即是一个空二叉树。 二叉树中每个结点至多只

3、有两棵子树，而这两棵子树作为结点集合互不相交； 二叉树中结点的两棵子树有左、右之分，次序不能颠倒。 2、二叉树基本类型,5,5.1.2 满二叉树和完全二叉树,1、满二叉树 如果一棵二叉树满足下述条件，就称其为满二叉树（full binary tree）： 每个结点或是度数为2（具有两个非空子树）的结点，或是度数为0的（叶）结点； 所有叶结点都在同一层。,6,5.1.2 满二叉树和完全二叉树2,2、完全二叉树 若一棵二叉树满足下述条件，就称其为完全二叉树（complete binary tree）： 至多只有最下两层中结点的度数小于2； 最下一层的叶结点都依次排列在该层最左边位置。,7,5.1.

4、2 满二叉树和完全二叉树2,2、完全二叉树2 重点理解： 满二叉树是完全二叉树，但完全二叉树却不一定是满二叉树。 空二叉树和根二叉树既是满二叉树，也是完全二叉树。 完全二叉树可以看作是在满二叉树的最下一层，从右向左连续去掉若干个结点后得到二叉树。 完全二叉树中的一个结点如果没有左子结点，就一定没有右子结点。,8,练习：,1、完全二叉树某结点若无右子树则定无左子树。 2、完全二叉树某结点若无左子树则定无右子树。,9,5.1.3 二叉树基本性质,性质5-1 一棵二叉树第i（i0）层上至多只能有 个结点。,10,2i,证明：应用数学归纳法。 二叉树第0层有一个结点，即当i=0时，2i=20=1成立。

5、 假设结论对第i层成立，即第i层至多只能有2i个结点。注意到二叉树每个结点的度最多为2，第i+1层结点个数至多只能是第i层结点个数的2倍，即2*2i = 2i+1，归纳完成，命题得证。,5.1.3 二叉树基本性质2,11,性质5-2 树高为k（k0）的二叉树，最多有 个结点。,2k+1-1,证明： 由性质5-1可知在树高为k的二叉树当中，第0层有20个结点，第1层有21个结点，第2层有22个结点，第k层有2k个结点。由此可知，树高为k的二叉树结点个数总数为20 + 21 + 22 + 2k。这是一个公比为p=2的等比数列，前k+1项和Sk+1为： Sk+1 =（a0 akp）/（1p）= (2

6、02k2)/(12) = (12k+1)/(12) = 2k+11,5.1.3 二叉树基本性质3,性质5-3 如果二叉树中度为0结点数为n0，度为2结点数为n2， 则 成立。,12,n0=n2+1,证明：设结点总数 n = n0+ n1+ n2 又因为：结点数n = 边数+1 边数 = n1+ 2*n2 即n0 + n1 + n2 = n1 + 2n2 + 1 所以：n0 = n2 + 1,结点数n = 边数+1,练习：,一棵树的度为4，n4=2， n3=3， n2=4，求n0？,13,解： 结点数 = 边数 + 1 n0+ n1+n2 +n3+n4 = n1+ 2*n2 + 3*n3 + 4

7、*n4 + 1 n0 + 2 + 3 + 4 = 8 + 9 + 8 + 1 n0=17,练习：,设完全二叉树有1000个结点，求叶子结点个数？有多少个度为1的结点？度为2的结点呢？,14,解：设二叉树中叶子结点、度为1、度为2的结点数目 分别n0、 n1、n2 ， 其中完全二叉树中n1只能为1或0，则：,n0+ n1+ n2 = 1000 n0 = n2+ 1 n1= 0 或 n1=1,复习两个概念：,（1）满二叉树：深度为k的满二叉树有 个结点。,15,2k+1-1,对满二叉树按层次从上到下，从左到右，不留一个空位进行编号，号码1n。,（2）完全二叉树：结点数为n的完全二叉树上各个结点与同

8、深度的满二叉树前n个相应位置结点编号一一对应。,5.1.3 二叉树基本性质4,16,性质5-4 设BT为具n个结点的完全二叉树，将BT所有结点按照从上到下、从左到右的顺序（二叉树的层序）进行编号。则BT中任意结点N的序号i（1in）具有下述性质。 （1）若i=1，则N为BT根结点，N无父结点； （2）若i1，则N父结点序号为 （即i除以2后向下取整）； （3）若2in，则N无左子树，否则其左子结点（即左子树的根结点）序号为2i； （4）若2i+1n，则N无右子树，否则其右子结点（即右子树的根结点）序号为2i+1。,练习：,1、1000个结点的完全二叉树最大的分支结点编号为 。 2、n个结点的完

9、全二叉树深度为 。,17,500,int（log2n）,5.2 二叉树存储,5.2.1 二叉树顺序存储 预留最大空间 深度为k的二叉树预留2k+1-1个存储单元，按编号顺序存储，遇空结点留空位。,18,5.2.1 二叉树顺序存储2,适合满（完全）二叉树，求双亲、孩子方便 不适合深度较大、结点不多的二叉树,19,5.2.2 二叉树链式存储,1、二叉链表存储 让一个存储结点只包含与其子树的邻接关系，那么就是二叉树的二叉链表存储结构。,20,5.2.2 二叉树链式存储,1、二叉链表存储2,21,用C语言定义二叉链表的结构类型如下： struct node DataType data; /* 定义数据

10、域，DataType代表实际需要的类型 */ struct node *lch; /* 定义左孩子域，指向左孩子地址 */ struct node *rch; /* 定义右孩子域，指向右孩子地址 */ ; typedef struct node bitree; /* 定义二叉树结点类型为bitree */,1、二叉链表存储3,算法5-1 创建一棵只有根结点的二叉树算法。 创建只有以x为根结点的二叉树Bt，x的数据类型为DataType，相应结点的Lchild和Rchild域均取值NULL，返回指向根结点的指针。,22,00 Create_Bt(DataType x) 01 02 bitree

11、*Bt,*ptr; 03 ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点 */ 04 Bt=ptr; 05 ptr-data = x; 06 ptr-lch = NULL; 07 ptr-rch = NULL; 08 return (Bt); 09 ,1、二叉链表存储4,算法5-2 在指定左子结点处插入一个新结点。 已知二叉链表Bt，在指针Parent所指结点左子结点处插入一个数据元素值为x的新结点，使之成为Parnet所指结点新的左子树根结点。,23,bitree *Inl_Bt(bitree *Bt, bitree *Parent, D

12、ataType x) if (Parent = NULL) printf (“位置错！“); return (NULL); ptr = (bitree *) malloc (sizeof(bitree); /* 申请存储结点空间 */ ptr-data = x; ptr-lch = NULL; ptr-rch = NULL; if (Parent-lch = NULL) /* Parent所指结点左子树为空 */ Parent-lch = ptr; else /* Parent所指结点左子树非空 */ ptr-lch = Parent-lch; Parent-lch = ptr; return

13、(Bt) ,5.2.2 二叉树链式存储2,2、三叉链表存储 同时反映当前结点与其左子树的根结点、右子树的根结点和与其父结点关联。,24,5.2.2 二叉树链式存储2,2、三叉链表存储2,25,5.3 二叉树的遍历,按照某种确定方式对二叉树进行访问，但要求二叉树中每个结点被访问一次且只被访问一次。 1、先序、中序和后序遍历 对左、右子树，限定“先访左后访右”，那么访问结点的顺序有三种不同的组合形式：TLR、LTR、LRT。 通常，称TLR为二叉树的先序（先根）遍历， LTR为中序（中根）遍历， LRT为后序（后根）遍历。,26,例子：,以三种遍历方式访问如图所示的二叉树。,27,解：先序遍历序列

14、 A-B-D-H-E-C-F-I-G-J-K 中序遍历序列 D-H-B-E-A-I-F-C-J-G-K 后序遍历序列 H-D-E-B-I-F-J-K-G-C-A,例子：,已知二叉树先序遍历序列是A-B-C-D-E-F-G，中序遍历序列是C-B-D-A-E-G-F。由这两个序列可唯一确定一棵二叉树。,28,解：从先序遍历序列第一个结点可知二叉树根结点是A。由结点A在中序遍历序列里位置可知该根结点左子树包含结点C-B-D，右子树包含结点E-G-F，如图5-22所示。由中序序列片段C-B-D可知，B是A左子树根结点，再结合先序序列片段B-C-D可知，C和D分别是B的左右子结点。由先序序列片段E-F-

15、G可知，E是A的右子结点，再由先序序列片段F-G和中序序列片段G-F可知，F不能是E的左子结点，故只能是E的右子结点，并且G是F的左子结点。,29,练习：,1、已知二叉树先序遍历序列为ABCDEFGH，中序遍历序列为CDBAFEHG，试画出此二叉树。 2、已知二叉树后序遍历序列为DCBFHGEA，中序遍历序列为CDBAFEHG，求先序遍历序列。,30,5.3 二叉树的遍历2,2、基于递归遍历算法 递归步骤（先序遍历）： 访问根结点； 先序遍历访问左子二叉树； 先序遍历访问右子二叉树。,31,2、基于递归遍历算法2,算法5-4 二叉树先序遍历递归算法。 已知二叉树Bt，对其进行先序遍历，若二叉树

16、为空，则为空操作；否则进行如下操作：访问二叉树根结点；先序遍历二叉树的左子树；先序遍历二叉树的右子树。,32,00 Pret_Bt(bitree *Bt) 01 02 if (Bt != NULL) 03 04 printf (“%c“, Bt-data); /* 访问根结点 */ 05 Pret_Bt(Bt-lch); /* 先序遍历左子树 */ 06 Pret_Bt(Bt-rch); /* 先序遍历右子树 */ 07 08 ,2、基于递归遍历算法2,基于递归调用先序遍历:,33,2、基于递归遍历算法2,先序递归算法应用实例:先序建立二叉树 bitree *creat() bitree *t

17、; int x; scanf(“%d”, ,2、基于递归遍历算法2,先序递归算法应用实例:先序建立二叉树(续) 主程序调用: main() bitree *root; root=creat(); 例：建立如图二叉树应该如何输入？ 练习： 测试用例：1 2 3 0 0 4 0 5 0 0 6 0 0 问：画出建立的二叉树？,2、基于递归遍历算法3,算法5-5 二叉树中序遍历递归算法。 已知二叉树Bt，对其进行中序遍历，若二叉树为空，则为空操作；否则进行如下操作：中序遍历二叉树的左子树；访问二叉树根结点；中序遍历二叉树的右子树。,36,00 Indt_Bt(bitree *Bt) 01 02 if

18、 (Bt != NULL) 03 04 Indt_Bt(Bt-lch); /* 中序遍历左子树 */ 05 printf (“%c“, Bt-data); /* 访问根结点 */ 06 Indt_Bt(Bt-rch); /* 中序遍历右子树 */ 07 08 ,2、基于递归遍历算法3,基于递归调用中序遍历:,37,2、基于递归遍历算法4,算法5-6 二叉树后序遍历递归算法。 已知二叉树Bt，对其进行后序遍历，若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树的左子树；后序遍历二叉树的右子树；访问二叉树根结点。,38,00 Postv_Bt(bitree *Bt) 01 02 if (B

19、t != NULL) 03 04 Postv_Bt(Bt-lch); /* 后序遍历左子树 */ 05 Postv_Bt(Bt-rch); /* 后序遍历右子树 */ 06 printf (“%c“, Bt-data); /* 访问根结点 */ 07 08 ,2、基于递归遍历算法4,基于递归调用后序遍历:,39,5.3 二叉树的遍历3,3、基于非递归遍历算法 非递归遍历算法中，需要做出三条假设： 设置一个一维数组Ss作为顺序栈以临时保存遍历时遇到的结点信息，其栈顶指针为Ss-top，初始时为0。 采用二叉链表结构保存需要遍历的二叉树，起始指针为Bt，每个结点包含Data、Lchild和Rchi

20、ld等三个域。 对结点进行的“访问”理解为将该结点的Data域的值打印出来。,40,3、基于非递归遍历算法2,算法5-7 先序遍历二叉树的非递归算法。 已知二叉树Bt，顺序栈Ss，要求打印出该二叉树的先序遍历序列。,41,00 Pre_Bt(bitree *Bt) 01 02 bitree *p; 03 bitree *stack10; /* 定义栈数组 */ 04 int top=-1; /* 定义栈顶下标top并赋初值-1 */ 05 printf(“nOutput preorder:“); 06 p= Bt; 07 while(p!=NULL | top!=-1) 08 if (p!=N

21、ULL) 09 10 printf(“%d “,p-data); /* 访问该结点 */ 11 top=top+1;stacktop=p; /* 访问后入栈 */ 12 p=p-lch; /* 继续深入左孩子 */ 13 14 else 15 16 p=stacktop;top=top-1; /* 遇空出栈，栈顶给p */ 17 p=p-rch; /* 转向右孩子 */ 18 19 ,3、基于非递归遍历算法2,基于非递归二叉树先序遍历：,42,3、基于非递归遍历算法3,中序非递归遍历算法流程: bitree *p; 定义及初始化栈; p=root; while(p!=NULL | 栈不空) i

22、f (p!=NULL) p进栈；p=p-lch; else 栈顶给p并出栈；输出p；p=p-rch;,3、基于非递归遍历算法3,算法5-8 中序遍历二叉树的非递归算法。 已知二叉树Bt，顺序栈Ss，要求打印出该二叉树的中序遍历序列。,44,00 In_Bt(bitree *Bt) 01 02 bitree *stack10; /* 定义栈数组 */ 03 int top=-1; /* 定义栈顶下标top并赋初值-1 */ 04 bitree *ptr; 05 ptr = Bt; /* ptr是工作指针 */ 06 do 07 08 while (ptr != NULL) /* 一直朝左子树深入

23、下去 */ 09 10 top+; /* 调整栈顶指针 */ 11 stacktop = ptr; /* ptr所指结点进栈 */ 12 ptr = ptr-lch; 13 14 if (Ss_top !=-1 ) 15 16 ptr = stacktop ; /* 栈顶元素赋值给ptr */ 17 top - ; /* 出栈 */ 18 printf (“%d “, ptr-data); /* 访问该结点 */ 19 ptr = ptr-rch; /* 进入右子树访问 */ 20 21 while(ptr !=NULL)|(top!=-1); 22 ,3、基于非递归遍历算法3,基于非递归二叉

24、树中序遍历（1-4趟）：,45,3、基于非递归遍历算法3,基于非递归二叉树中序遍历（1-4趟）：,46,3、基于非递归遍历算法4,算法5-9 后序遍历二叉树的非递归算法（略）。 已知二叉树Bt，顺序栈Ss，要求打印出该二叉树的后序遍历序列。,47,算法要点： 由于后序遍历是“左、右、根”，因此在后序遍历过程中搜索到某个结点时，不是马上访问它，而是将其作为相应子树根结点保存在工作栈中，然后沿着其左子树继续深入直到“最左下”结点。完成对其左子树访问后，从工作栈顶元素中获得相应根结点信息，但仍然不能马上进行访问，而是在工作栈中对其进行第二次保存，同时对其右子树进行遍历。在访问完右子树后，从工作栈中得

25、到根结点信息，由此实现对相应根结点访问。,3、基于非递归遍历算法4,基于非递归二叉树后序遍历第1-3趟运算变化：,48,3、基于非递归遍历算法4,基于非递归二叉树后序遍历第4趟运算变化：,49,3、基于非递归遍历算法4,基于非递归二叉树后序遍历第5-7趟运算变化：,50,上机：,1、用先序递归方法建立一棵二叉树； 2、用中序非递归方法遍历该二叉树。,51,5.4 线索二叉树,5.4.1 线索与线索二叉树 结合遍历方式特点使用这些空链域来存放相应前驱或后继信息即前驱或后继的地址。 当前结点左孩子域非空时，保留原指针不变；当左孩子域为空时，添加该结点在相应历序列中前驱结点地址。 当前结点右孩子域非

26、空时，保留原指针不变；当右孩子域为空时，添加该结点在相应遍历序列中后继结点地址。,52,5.4.1 线索与线索二叉树2,一个中序线索二叉树的例子：,53,5.4.2 创建线索二叉树,1、创建线索二叉树结点,54,算法5-10（线索二叉树结点结构） 01 struct ThreadNode /* 线索二叉树结点的定义 */ 02 03 DataType info; 04 struct ThreadNode llink, rlink; 05 int ltag, rtag; 06 ; 07 typedef struct ThreadNode ThreadTree; /* 线索二叉树类型的定义 */,

27、5.4.2 创建线索二叉树2,2、二叉树的线索化,55,在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre，并始终保持指针pre指向当前访问的、指针p所指结点的前驱。将给定二叉树扩充为线索二叉树的过程称为二叉树的线索化，也就是线索二叉树的创建。 线索化实际上就是在遍历过程中在当前结点的空链域中添加前驱或后继指针。为了保留遍历过程中访问结点的前驱与后继关系，需要设置一个工作指针pre始终指向刚访问过的结点，也就是说，当指针p指向当前访问结点时，pre就指向p的前驱结点。,5.4.2 创建线索二叉树3,3、线索二叉树遍历,56,以下以对中

28、序线索化链表为例讨论基于线索的二叉树中序遍历算法。此时，算法关键点有二： 怎样获取中序遍历的首结点？ 从根结点沿着左指针不断向左下搜寻，直到给定二叉树左子树的处于“最左下”的结点，结点是“最左下”的含义是该结点再无左子结点，亦即该结点的左指针域为空。 怎样获取在中序线索化链表中当前结点的后继结点？ 如果当前结点没有无右子树，则其后继结点即为其右指针域中后继线索所指结点；如果当前结点存在右子树，则从该右子树根结点开始沿左指针行进，直到右子树“最左下”结点，此即为当前结点的后继。,5.4.2 创建线索二叉树3,3、线索二叉树遍历2,57,算法5-12基于中序线索二叉树中序遍历算法 00 void

29、thrInOrder(ThreadTree *root ) 01 02 ThreadTree *p; 03 p = root-llink; 04 if (p=NULL) 05 return ; 06 while ( p-llink!=NULL 19 20 ,5.5 Huffman编码,5.5.1 等长与非等长编码 所谓编码（code），就是用一组不同的代码表示一个数据对象集合中的每个元素的过程。 1、两种基本编码类型 编码三要素： 唯一性：发送方传输编码字段，接收方解码后必须具有唯一性，解码结果与发送原文保持相同； 简洁性：发送的编码应该尽可能做到简洁短小，减少存储代价和提高传输效率。 前缀性

30、：两个编码字节不使用特殊标记如标点符号进行分隔，一个编码字节不能是另一个编码字节的前缀，应具有“前缀性”（Prefix Property）；,58,5.5.1 等长与非等长编码2,2、最优二叉树与Huffman树 二叉树路径长度：一棵二叉树的所有从根结点到每个叶结点路径长度之和称为该二叉树的“路径长度”。 叶结点的权：赋给二叉树叶结点一个具有某种意义的实数，则称此数为该叶结点的“权”。 二叉树带权路径长度：设二叉树具有n个带权的叶结点，则从根结点到各叶结点的路径长度与相应结点权值乘积之和称为该二叉树的“带权路径长度”，记为：,59,WPL= wklk,（wk是第k个叶结点权值， lk是第k个叶

31、结点路径长度）,“Huffman树”：由带有权值的一组相同叶结点所构成二叉树当中，称其中带权路径长度最小的二叉树为是“最优二叉树”。,5.5.2 Huffman树构建思想,设有n个权值w1、w2、w3、wn，则可按照下述步骤构造Huffman树： Step 1. 构造n棵只有一个根结点的二叉树森林 HT = T1，T2，T3，Tn，它们分别以w1、w2、w3、wn作为权值。 Step 2. 在HT集合中，选取权值最小和次小的两个根结点作为一棵新二叉树的左子树和右子树。新二叉树根结点权值是其左、右子树根结点权值之和； Step 3. 在HT集合中，删除已经取为左、右子树的原两棵二叉（根）树，并将

32、新构成二叉树添加到HT中； Step 4. 重复Step 2和Step 2至HT只剩下一棵二叉树，此即是所求Huffman树。,60,5.5.2 Huffman树构建思想2,构造具有四个分别带有权值1、3、5、7的Huffman树如下图所示：,61,练习：,已知有6个叶子，值分别为A、B、C、D、E、F，它们的权值分别为4，9，1，3，2，1，试构造哈夫曼树（左权右权）。,62,5.5.3基于顺序存储Huffman树构造,1、Huffman树结点结构 问题：若哈夫曼树有n0个叶子结点，则所有结点 个。,63,2n0-1,解：因为树中无度为1的结点， 由二叉树的性质3知：n0=n2+1 所以：n

33、=n0+n2=n0+n0-1 =2n0-1 由于最终结果中结点个数已经确定，因此可采用顺序结构存储存放所建Huffman树,5.5.3基于顺序存储Huffman树构造,1、Huffman树结点结构2 问题：结点结构如何构造？,64,00 struct node 01 02 int weight; 03 int parent,lch,rch; 04 ; 05 struct node HtreeMAX;,5.5.3基于顺序存储Huffman树构造2,2、Huffman树构造算法 问题：算法如何构造Huffman树？,65,原理： 找两无双亲且权值最小结点合并，生成新结点，填写相关信息（两结点双亲，

34、新结点权值，新结点左、右孩子）。,算法5-13 基于顺序存储Huffman树构造算法,00 creat_huff(struct node Htree) 01 02 int i,j,min1,min11,min2,min22; 03 printf(“nInput the count of leaves(10):“); 04 scanf(“%d“,66,算法5-13 基于顺序存储Huffman树构造算法2,14 for (i=n;i2*n-1;i+) /* 控制n-1次二叉树的合并 */ 15 16 min2=min1=MAX; /* min1、min2记录当前最小、次小权值 */ 17 min1

35、1=min22=0; /* min11、min22记录当前最小、次小权值结点位置 */ 18 for (j=0;ji;j+) /* 在j的范围内，找最小、次小结点 */ 19 20 if (Htreej.parent=-1) 21 if (Htreej.weightmin1) /* 如当前权值比最小结点还小 */ 22 23 min22=min11; 24 min2=min1; /* 最小结点信息赋给次小 */ 25 min11=j; 26 min1=Htreej.weight; /* 当前权值信息赋给最小 */ 27 28 else,67,算法5-13 基于顺序存储Huffman树构造算法3

36、,29 if (Htreej.weightmin2) /* 如当前权值比次小结点小 */ 30 31 min22=j; 32 min2=Htreej.weight; /* 当前权值信息赋给次小 */ 33 34 35 Htreemin11.parent=i; /* 设置最小权值结点的parent域 */ 36 Htreemin22.parent=i; /* 设置次小权值结点的parent域 */ 37 Htreei.weight=Htreemin11.weight+Htreemin22.weight; /* 设置新结点的权值域 */ 38 Htreei.lch=min11; /* 设置新结点的

37、lch域为最小结点 */ 39 Htreei.rch=min22; /* 设置新结点的rch域为次小结点 */ 40 41 Htree2*n-2.parent=-1; /* 最后一个结点为根结点，parent域为-1 */ 42 ;,68,5.5.3基于顺序存储Huffman树构造3,3、Huffman树算法分析,69,设有叶结点相应权值分别为1，3，5，7。按照算法构建Huffman树过程如下图所示：,5.5.3基于顺序存储Huffman树构造3,3、Huffman树算法分析,70,设有叶结点相应权值分别为1，3，5，7。按照算法构建Huffman树过程如下图所示（续）：,5.5.4 Huf

38、fman编码,1、Huffman编码概念 基于具体Huffman树的不等长编码就称为Huffman编码。 首先得到需要编码的字符c1、c2、cn在相应数据信息中出现的频率为p1、p2、pn；再以c1、c2、cn作为叶结点，p1、p2、pn作为相应权值，按照Huffman算法构造一棵Huffman树。 其次，由构造的Huffman树的根结点开始，在每个左分支上标注0，右分支上标注1。这样，从根结点到每个叶结点的路径上由0、1组成的序列，就是该结点对应字符的编码。,71,5.5.4 Huffman编码,1、Huffman编码概念2 编码步骤1：先建Huffman树,72,5.5.4 Huffman

39、编码,1、Huffman编码概念2 编码步骤1：先建Huffman树（续）,73,5.5.4 Huffman编码,1、Huffman编码概念2 编码步骤2：再编码,74,5.5.4 Huffman编码2,2、Huffman编码算法 问题：如何编码？ 原理： 从叶子结点到根结点顺着路径分支为其编码。,75,算法5-14 Huffman编码算法,00 code_huff(struct node Htree) 01 02 int i,j,k,pr,start; 03 for (i=0;in;i+) 04 05 j=n-2; 06 k=i; /* k记录当前编码结点，初始为叶结点位置 */ 07 wh

40、ile(Htreek.parent!=-1) 08 09 pr=Htreek.parent; /* 记录k的父结点 */ 10 if(k=Htreepr.lch) 11 codeij=0; /* 左分支编码为0 */ 12 else 13 codeij=1; /* 右分支编码为1 */ 14 j=j-1; 15 k=pr; /* 进到路径的上一个结点，直至根结点 */ 16 17 codein-1=j+1; /* 存放编码的起始位置是j+1 */ 18 ,76,算法5-14 Huffman编码算法2,19 printf(“n The code are:n“); 20 for (i=0;in;i

41、+) 21 22 start=codein-1; /* 取出编码的起始位置 */ 23 for (j=start;jn-1;j+) /* 逐个输出编码 */ 24 printf(“ %-3d“,codeij); 25 printf(“n“); 26 27 ,77,5.5.4 Huffman编码3,3、Huffman编码算法分析 Huffman编码过程如下图所示：,78,练习：,设有7个带权结点A，B，C，D，E，F，G，其权值分别为3，7，8，2，5，8，4，试以这7带权结点为叶子结点，构造一棵哈夫曼树（左权右权）。,79,练习：,在一份报文中有五种字符，A，B，C，D，E，它们在报文中出现的频率比例为4，7，5，2，9，试通过构造最优二叉树来确定每种字符的哈夫曼编码（左权右权）。,80,上 机：,81,理解建立huffman树的过程及编码过程。 1. 结点定义（需要至少4个域：weight，parent，lch，rch） 2. 定义数组 3. 输入叶子的个数n 4. 数组初始化 5. 输入叶子的权值 6. 循环n1次做： （1）找两个最小权值及其下标 （2）合并，填写相关信息 7. 输出数组 8. 编码并输出,本章小结,本章基本内容,