《数据结构六章节树和二叉树.ppt》由会员分享，可在线阅读，更多相关《数据结构六章节树和二叉树.ppt（48页珍藏版）》请在三一文库上搜索。
1、数据结构第六章树和二叉树,噶骑懒匡求丸敬晤刷兔屉氧夹涸费禽卧办逊然扶贴貉眠盖媚抗吧倪碰仇狮数据结构六章节树和二叉树数据结构六章节树和二叉树,本章内容 6.1 树的概念与基本术语 6.2 二叉树 6.3 遍历二叉树 6.4 线索二叉树 6.5 树与森林 6.6 赫夫曼树及其应用,华邦伏咨刻俄初申必介钡刮刨槐蹄妨痕石霓枚粒佐吵节辩酉敏抱已回熟歪数据结构六章节树和二叉树数据结构六章节树和二叉树,6-3,6.1 树的概念与基本术语,树的定义(Tree) 树是有n(n0)个结点的有限集合。 如果 n=0，称为空树； 如果 n0,称为非空树,对于非空树,有且仅有一个特定的称为根(Root)的节点(无直接前
2、驱) 如果 n1，则除根以外的其它结点划分为 m (m0)个互不相交的有限集 T1, T2 , Tm，其中每个集合本身又是一棵树，并且称为根的子树(SubTree)。 每个结点都有唯一的直接前驱，但可能有多个后继 树的举例 其中：A是根；其余结点分成三个互不相交的子集， T1=B,E,F,K,L； T2=C,G； T3=D,H,I,J,M, T1,T2,T3都是根A的子树，且本身也是一棵树,侯铺刮好传健菇坷横蝶砚衙秦箕爵欺唤使沈驹醚颗扭颜代浸赎抑撞愚泛椎数据结构六章节树和二叉树数据结构六章节树和二叉树,6-4,6.1 树的概念与基本术语,树的基本术语 结点：包含一个数据元素及若干指向其子树的分
3、支 结点的度：结点拥有的子树数,或者说后继结点数 叶结点：度为0的结点没有子树的结点 分支结点：度不为0 的结点包括根结点， 也称为非终端结点。 内部结点:除根外的结点 孩子：结点的子树的根 双亲：孩子的直接前驱,构媳散葛絮汾吁肤谚齿霄宣吗搏狼谍脓肖唯勇郸上喀绸百拴疯欣令剃知疗数据结构六章节树和二叉树数据结构六章节树和二叉树,6-5,6.1 树的概念与基本术语,兄弟：同一双亲的孩子 子孙：以某结点为根的 树中的所有结点 祖先：从根到该结点 所经分支上的所有结点 层次：根结点为第一层，其孩子为第二层，依此类推 深度：树中结点的最大层次 森林：互不相交的树的集合。对树中每个结点而言，其子树的集合即
4、为森林,其跳森膛假媒继延玩尤浦中联皇奏镜女秧锦正郭师荚貉玖运恐她未靡夜磊数据结构六章节树和二叉树数据结构六章节树和二叉树,6-6,6.2 二叉树,二叉树(Binary Tree) 每个结点最多有棵子树 二叉树的子树有左右之分,纬差朝磋义逆嚎魄纬挫踏详何鳃揩郡筛筒赘务明固骇铂菇辫棕舒兰瀑瓢胯数据结构六章节树和二叉树数据结构六章节树和二叉树,6-7,6.2 二叉树,二叉树性质：在二叉树的第i层上至多有2i-1个结点 证明： i=1, 只有一个根节点，因此2i-1=20=1 设第i-1层上，以上性质成立，即第i-1层至多有2(i-1)-1结点。 由二叉树的定义可知，任何结点的度小于2，因此，第i层上
5、的结点数最多为第i-1层上的两倍，即2*2i-2=2i-1 证毕,酵础桥牢栏检欣挪牢台耻炳渠香税痪盘店枝尿佑界简咋文阀陆殊莲临倾细数据结构六章节树和二叉树数据结构六章节树和二叉树,6-8,6.2 二叉树,二叉树性质：深度为k的二叉树至多有2k-1个结点 证明： 由性质，已知第i层上结点数最多为2i-1 k 2i-1 = 2k-1 i=1 证毕,铡豪告嘎诛吩换算插站状叶鲜抉渗罕通薪蓉尧额篡喘慨冷膨瓮哄丹砰棵亭数据结构六章节树和二叉树数据结构六章节树和二叉树,6-9,6.2 二叉树,二叉树性质：如果二叉树终端结点数为n0，度为2的结点数为n2，则n0=n2+1 证明： 设n1是度为1的结点，则总结
6、点数n= n0+n1+n2 设B为二叉树的分支数，除根结点外，每个结点有且只有一个分支，因此n=B+1 每个分支皆由度为1或2的结点发出，B=n1+2n2 n=B+1=(n1+2n2)+1 = n0+n1+n2，因此 n0=n2+1 证毕,脾系门次吟动炊催贝流科篮楔墩报呻川勃奖剩去梆极洒阵筒枕杀纫狼乖陵数据结构六章节树和二叉树数据结构六章节树和二叉树,6-10,6.2 二叉树,满二叉树： 一个深度为k且有2k-1个结点的二叉树 每层上的结点数都是最大数 可以自上而下、自左至右连续编号,幻玻贰津徘剂空肘露砂臼壹馏渺喂夕鹊弃藏枉篷室幕夕沏铡曰琉蔫墙囊澈数据结构六章节树和二叉树数据结构六章节树和二叉
7、树,6-11,6.2 二叉树,完全二叉树： 当且仅当每一个结点都与深度相同的满二叉树中编号从1到n的结点一一对应的二叉树 叶子结点只在最大两层上出现 左子树深度与右子树深度相等或大,雀捅座沈娩认峡习成恭缄犊香录吧浚文怨刨仓波某束脖灼俯虎逐城炕帕姚数据结构六章节树和二叉树数据结构六章节树和二叉树,6-12,6.2 二叉树,完全二叉树(性质)：具有n个结点的完全二叉树,其深度为 log2n +1 证明：设k为深度，由二叉树性质，已知 2k-1-1 n 2k-1 即 2k-1 n 2k 即 k = log2n +1,钾腿烙任具胺胡蜀屎钾附顽捆董搁卞杆莹篙问襄疼板钱陀珊肮癣尹奥疚回数据结构六章节树和二
8、叉树数据结构六章节树和二叉树,6-13,完全二叉树(性质)： 在完全二叉树中，结点i的双亲为 i/2 结点i的左孩子LCHILD(i)=2i 结点i的右孩子RCHILD(i)=2i+1,6.2 二叉树,苫办池省捏舷谦歪芒苦佃帖闰付善簿颅租剃舶盂彤铝伶咕勇促麦匹返旧粳数据结构六章节树和二叉树数据结构六章节树和二叉树,6-14,6.2 二叉树,二叉树的存储结构 1.顺序存储结构 2.链式存储结构 顺序存储结构：用一个一维数组来存储二叉树的各个结点 C语言表示 #define MAX_TREE_SIZE 100 /二叉树的最大结点数 typedef TElemType SqBiTreeMAX_TRE
9、E_SIZE;/0号单元存储根结点 SqBiTree bt; 显然，二叉树的结点必须按某种次序分别存入数组的各个单元，这种次序应能反映结点间的逻辑关系，否则二叉树上的各种基本运算在顺序存储结构上很难实现。 对于完全二叉树来说，可以采用“以编号为地址”的方法，将编号为i的结点存入一维数组的第i个单元(下标为i-1)。,形彼叠肘值涎罢暮镣拙匿格湿多丘纤痕烬键裙奖矿嚣英碰萧隶醛翰悉薪传数据结构六章节树和二叉树数据结构六章节树和二叉树,6-15,6.2 二叉树,完全二叉树的顺序表示 例: 对应的顺序存储结构: 将编号为i的结点存入一维数组的第i个单元(下标为i-1),基害淤插惊弯蛹舵藐桩伍肄给窜搭辅虫
10、连般灿专姬死丧榆垄营乓糙漾蒙扔数据结构六章节树和二叉树数据结构六章节树和二叉树,6-16,非完全二叉树的顺序表示 例: 对应的顺序存储结构: 一维数组的21单元中只用上了7个.最坏情况下,一个深度为k且只有k个结点的单支树,却需要长度为2k-1的一维数组 总结 顺序存储结构适合存储完全二叉树 对于非完全二叉树，采用链式存储结构更合适,6.2 二叉树,舆森窑屉褪多马煮花拖酱庚个财要舱描发诵夫葬簧震补生势双粪罗怔捉攒数据结构六章节树和二叉树数据结构六章节树和二叉树,6-17,6.2 二叉树,二叉链表 结点结构: 通常每个结点中设置三个域,即值域、左指针域和右指针域，其结点结构如下： 其中data表
11、示值域，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针。 TElemType可以是任何相应的数据类型如int、float或char等。,typedef struct BiTNode TElemType data; struct BiTNode *lchild, *rchild; BiTNode, *BITree;,口搞生烽芋沁臻猜译析吝衣菩匹欠幼无本闪舍昔捻乓吾侵巢啤峰宛惮凯忿数据结构六章节树和二叉树数据结构六章节树和二叉树,6-18,6.2 二叉树,住曰嚏萄锭翟顶绚悟垄碘扮驴旗沸卉恬岩韧诛炎跋逸柒矮疽时募庄衅拂歼数据结构六章节树和二叉树数据
12、结构六章节树和二叉树,6-19,6.2 二叉树,三叉链表 通常每个结点中设置四个域,即值域、左指针域、右指针域和双亲指针域，其结点结构如下： 其中data表示值域，用于存储放入结点的数据，lchild和rchild分别表示左指针域和右指针域，用以分别存储指向左儿子结点和右儿子结点的指针,parent指向双亲结点。,亮号秆炙义拙嚼叉腐滇蝉按案太纷隶埠滤讼希绽变埠硒单羞度惨渐军旭杭数据结构六章节树和二叉树数据结构六章节树和二叉树,6-20,6.3 遍历二叉树,遍历二叉树 定义：二叉树的遍历(Traverse)是指按一定的规律访问二叉树的每个结点，且每个结点只被访问一次的过程。 对二叉树的遍历过程实
13、际上是将非线性结构的二叉树中的结点排列成一个线性序列的过程。 本节仅讨论二叉链表的遍历过程。设访问根结点用D表示，遍历左、右子树用L、R表示 遍历分类：在任一结点上，有三种执行操作：访问结点本身，遍历该结点左子树，遍历该结点右子树。操作次序主要分为三种： 左、根、右；也称为中序遍历、LDR； 根、左、右；也称为先序遍历、DLR； 左、右、根；也称为后序遍历、LRD。,闲鸭附阑盂墩室屿腕烯佃忠居潘手束好搪谢娩霜搔谤人虎山档泞啪蔗嘻瓤数据结构六章节树和二叉树数据结构六章节树和二叉树,6-21,6.3 遍历二叉树,三种遍历次序以递归的形式定义 中序(InOrder)遍历：若树为空，执行空操作；否则依
14、次执行： 中序遍历左子树L； 访问根结点D； 中序遍历右子树R。 先序(PreOrder)遍历：若树为空，执行空操作；否则依次执行： 访问根结点D； 先序遍历左子树L； 先序遍历右子树R。 后序(PostOrder)遍历：若树为空，执行空操作；否则依次执行： 后序遍历左子树L； 后序遍历右子树R； 访问根结点D。,址痪幸疤卡坤钓徘冤遁月啸雁邢倦咒陆抽示设安豫邢虞涎无淆蕾练锚绦蹿数据结构六章节树和二叉树数据结构六章节树和二叉树,6-22,6.3 遍历二叉树,二叉树遍历的实现 template void PreOrder(BiTreeNode *t, void Visit(T item) /使用V
15、isit(item)函数前序遍历二叉树t if(t != NULL) Visit(t-data); PreOrder(t-Left(), Visit); PreOrder(t-Right(), Visit); 为了通用性，把访问操作设计成前序遍历二叉树函数的一个函数虚参 Visit()。,输出结果：ABDEGCF (第一个输出节点必为根节点),瘁祁戌钨寥涉羚估斜填敖瘴韵角延毙步宅咋绚伪改具多篆挥谢琼唯跃懒析数据结构六章节树和二叉树数据结构六章节树和二叉树,6-23,6.3 遍历二叉树,template void InOrder(BiTreeNode *t, void Visit(T item)
16、 /使用Visit(item)函数中序遍历二叉树t if(t != NULL) InOrder(t-Left(), Visit); Visit(t-data); InOrder(t-Right(), Visit); ,输出结果：DBGEAFC （先于根节点A输出的节点为左子树的节点 后于根节点A输出的节点为右子树的节点）,粳十蝎黎洁拆痴捣竭棱盒剃汰抉笛惹拷岸住殷鸵翻哥坛蔗昼炸蜀吏玲驮蕊数据结构六章节树和二叉树数据结构六章节树和二叉树,6-24,6.3 遍历二叉树,template void PostOrder(BiTreeNode *t, void Visit(T item) /使用Visit
17、(item)函数后序遍历二叉树t if(t != NULL) PostOrder(t-Left(), Visit); PostOrder(t-Right(), Visit); Visit(t-data); ,输出结果：DGEBFCA (最后一个输出节点必为根节点),厕陵捧估嫌咒贾汽腊运膨每十蝎撇当悦舱鉴圣萝峙带硼嘉褐砂徊番灯超污数据结构六章节树和二叉树数据结构六章节树和二叉树,6-25,6.3 遍历二叉树,遍历二叉树应用 利用后序求结点个数或树的高度 利用前序实现二叉树复制 判断两棵树是否相等 Return 1+Size (t-lchild) + Size (t-rchild); temp-d
18、ata=progmpde -data; temp -lchile =copy(orignode-lchild); temp -rchile =copy(orignode-rchild); If (a!=NULL & b!=NULL & a-data=b-data & equal(a-lchild=b- lchild) & equal(a-rchild=b- rchild),逛拾干瞳砂醒不麻侧嗅机乙敲盈戒帮薪斟厕屈胆阎漳老扦产品约噎岂抛哮数据结构六章节树和二叉树数据结构六章节树和二叉树,6-26,6.3 遍历二叉树,根据先、中序遍历求序列二叉树：如果已知一棵二叉树的先序遍历和中序遍历序列，则可以
19、惟一确定这棵二叉树 算法： 1.在先序遍历序列中，第一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树,筷喧蘑释尿磅冤镐躯楔哉喷掺勘细掷依拙蒂浇鸯碴杜憨匀鞋尖田害盂赏撕数据结构六章节树和二叉树数据结构六章节树和二叉树,6-27,6.3 遍历二叉树,示例：已知一棵二叉树的 先序遍历序列为：ABDEGCF， 中序遍历序列为：DBGEAFC， 请画出这棵二叉树 解：根据先序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。 重复上述步骤，分别求出左子树和 右子树
20、的细节。,脏弊丑恰刃韩溺轻燃耗溜鞍莎厂体柿搓酉锯驻鸯捻临较鲁袄附学黍著醒霍数据结构六章节树和二叉树数据结构六章节树和二叉树,6-28,6.3 遍历二叉树,根据后、中序遍历求序列二叉树：如果已知一棵二叉树的后序遍历和中序遍历序列，则可以惟一确定这棵二叉树 算法： 1.在后序遍历序列中，最后一个节点为根节点D 2.在中序遍历序列中，根节点D左边的节点归为左子树，根节点D右边的节点归为右子树 3.对每个子树反复使用1,2两步，直到确定二叉树,氧奏药谨嫉跑匠蹋炎纫炭殿猪盐挺箍袍籽融饶药炳尾吞跌吹早堆伟桅吼犯数据结构六章节树和二叉树数据结构六章节树和二叉树,6-29,6.3 遍历二叉树,示例：已知一棵二
21、叉树的 后序遍历序列为：DGEBFCA ， 中序遍历序列为：DBGEAFC， 请画出这棵二叉树 解：根据后序遍历序列，可知根节点为A；再根据中序遍历序列可知，左子树由DBGE组成，右子树由FC组成。 重复上述步骤，分别求出左子树和 右子树的细节。,状淬副赖侄受画查趁届闸篱绿鲜抑储噪耙长裹聂横骋管待尊哪畸欣硅傈九数据结构六章节树和二叉树数据结构六章节树和二叉树,6-30,6.4 线索二叉树,二叉树以二叉链表存储结构不足 所有叶子结点与无子结点的结点指针位置，存储结构都是空的； 同时只能找到结点的左右孩子的信息,而不能在结点的任一序列的前驱与后继信息,这种信息只有在遍历的动态过程中才能得到。 解决
22、办法 利用二叉树中得空位置，建立遍历指针，达到在遍历中不再使用堆栈的目的。遍历指针被称为：线索。带有线索的二叉树被称为：线索二叉树,崔拖从衰疵沪湾所巩津堑靡忙替舷朴朋鞘湘闹基席撤俯式墓上恤洞爪喧痕数据结构六章节树和二叉树数据结构六章节树和二叉树,6-31,6.4 线索二叉树,在中序遍历过程中，遇到空指针时，需要决定遍历的后续结点的位置，所以： 空的右指针指向遍历后继 空的左指针指向遍历前趋,乡膨蹈迪乳禽亮凉衍澄纸裕斥回吞屠睡纠塘掌叮神辕另捂覆议饰研纤终萎数据结构六章节树和二叉树数据结构六章节树和二叉树,6-32,6.4 线索二叉树,线索二叉树中，只有两个空的指针分析中序的遍历过程 从左指针为空
23、的结点开始遍历 到右指针为空的结点结束遍历 建立二叉树的线索：在遍历过程中建立。 遍历时，记录当前结点的前趋和后继，在遇到空指针时，建立相应的连接。,备纸转莆酸践圣戴和小拐瞒皿贸莆临幌燕樊艳峰貌龄徐框肺顽犹膝歇陕粘数据结构六章节树和二叉树数据结构六章节树和二叉树,6-33,6.5 树与森林,树的存储结构 1.双亲表示法 采用一组连续的存储空间 由于每个结点只有一个双亲，只需要一个指针,谍惕芥唐筹糯醇堑制萍失徽寇银冲林祸六瘦讹睫忆算氛帕赢跋骇摊俱谊济数据结构六章节树和二叉树数据结构六章节树和二叉树,6-34,6.5 树与森林,2.孩子表示法多重链表 可以采用多重链表，即每个结点有多个指针 最大缺
24、点是空链域太多 (d-1)n+1个,奎源肄瓶规帧刚裔戮挎鸭旗陕剐菏衷疚间宵唆现庸鸥旬会赫空弄阔蒲昆察数据结构六章节树和二叉树数据结构六章节树和二叉树,6-35,6.5 树与森林,3.孩子表示法单链表 将每个结点的孩子排列起来，用单链表表示 将每个结点排列成一个线性表,锨舒巩酉认展澜号末缸菲峨盏坚辣描末铆泉援翔挣群酞驯熬盐饶柜息汛呈数据结构六章节树和二叉树数据结构六章节树和二叉树,6-36,6.5 树与森林,4.孩子兄弟表示法 采用二叉链表 左边指针指向第一个孩子，右边指针指向兄弟,安途循掀阀仙鹿粪拇讯钒栅锚隅剪钾氏由排恒抠佃滩札尸嫩抉厚恒彦氦臣数据结构六章节树和二叉树数据结构六章节树和二叉树,
25、6-37,6.5 树与森林,树与二叉树的对应关系 树与二叉树都可以采用二叉链表作存储结构 任意给定一棵树，可以找到一个唯一的二叉树(没有右子树) 树转换为二叉树的方法 树中所有相邻兄弟之间加一条连线。 对树中的每个结点，只保留它与第一个孩子结点之间的连线，删去它与其它孩子结点之间的连线。 以树的根结点为轴心，将整棵树顺时针转动450，使之结构层次分明。,尾嘻跨惮债炎卑郊扶膊库鬼梗俄朴铝娘把龙趋茁说搬些吭屏嘱驭争兔抢破数据结构六章节树和二叉树数据结构六章节树和二叉树,6-38,树转换成二叉树的过程举例,6.5 树与森林,渐意憋蜜订半列鸵玛售条晾务艳杠要逮属鹰丧态硷粟渤盾吾勾退扔瞻梆烙数据结构六章
26、节树和二叉树数据结构六章节树和二叉树,6-39,6.5 树与森林,森林与二叉树的对应关系 如果把森林中的第二棵树的根结点看作是第一棵树的根结点的兄弟，则可找到一个唯一的二叉树与之对应。 森林转换成二叉树 如果F=T1,T2, , Tm是森林，按如下规则可转换成一棵二叉树B=(root,LB,RB)。 （1）若F为空，则B为空； （2）若F非空，则森林中第一棵树T1的根结点为二叉树B的根结点，B的左子树LB由树T1根结点下的子树森林转换而成。右子树RB是由森林F中除树T1外余下部分转换而成。,诵渤俄叶集涪阿性法立转抠怔莆付捷屑男溶照丝表唆缠挡断诱镭堤捍鼓癌数据结构六章节树和二叉树数据结构六章节树
27、和二叉树,6-40,6.5 树与森林,树的遍历 对树的遍历主要有两种：先根（次序）遍历、后根（次序）遍历 先根（次序）遍历：当树非空时 访问根结点 依次先根遍历根的各棵子树 输出结果：ABEFCDG 后根（次序）遍历：当树非空时 依次后根遍历根的各棵子树 访问根结点 输出结果：EFBCGDA,兄搞眉灾刁睫舱豫虞饯拆胃峪堪句冀靳艾肆琉嘿尽圭闹频假丙柄宣姓澡飞数据结构六章节树和二叉树数据结构六章节树和二叉树,6-41,6.5 树与森林,与二叉树遍历的关系 当采用孩子兄弟表示法表示树时： 树的先根遍历，与树对应的二叉树的先根遍历完全相同 树的后根遍历，与树对应的二叉树的中根遍历完全相同,脾浆抨驹感翁
28、苗爱理券夸幻驭间朋昭厉麓榔伴议恳分娄锗氮丹憋望肝螺翱数据结构六章节树和二叉树数据结构六章节树和二叉树,6-42,6.6 赫夫曼树及其应用,赫夫曼树 赫夫曼树（Huffman）树也称最优二叉树，是一类带权路径长度最短的树，在判定、查找及数据压缩技术中有着广泛的应用。 基本术语 路径：从树中一个结点到另一个结点之间的分支构成这两个结点之间的路径 路径长度：路径上的分支数目 树的路径长度：从树根到每个结点的路径长度之和 带权路径长度：从结点到树根之间的路径长度与结点权的乘积 树的带权路径长度(WPL)：树中所有叶结点的带权路径长度之和 最优二叉树：假设二叉树有n个叶子，其每个叶子结点权为wi，则带权
29、路径长度WPL最小的二叉树称为最优二叉树。赫夫曼(Huffman)树就是一棵最优二叉树,聘沧豁汀橡价肩读歉橡皖久于滤酚淮围柱聂苇债冀颓凝旭拥野如俞酸交懈数据结构六章节树和二叉树数据结构六章节树和二叉树,6-43,6.6 赫夫曼树及其应用,例：下图所示的树路径长度为：2*1+3*2+1*3=11 下图所示的树的带权路径长度 WPL = 2*5+3*3+2*4=27,农夜系唁棉载魔晌澄衫扫矩麓差辅线鸡诬殴纷氨痛孩鬼渤邱赏忍突县丁那数据结构六章节树和二叉树数据结构六章节树和二叉树,6-44,6.6 赫夫曼树及其应用,构造Huffman树 在Huffman树中，权值最大的结点离根最近 权值最小的结点离
30、根最远 Huffman树算法 根据给定的n个权值(w1, w2, , wn)构成n棵二叉树的集合F=T1, T2, , Tn，其中每棵二叉树Ti中只有一个带树为Ti的根结点 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置其根结点的权值为其左右子树权值之和 在F中删除这两棵树，同时将新得到的二叉树加入F中 重复2, 3，直到F只含一棵树为止,叶核件逐户纪井妓址微明别良庸沦愧示饯侮摩圭浦董促掷洒剐赠非埃瘁酷数据结构六章节树和二叉树数据结构六章节树和二叉树,6-45,6.6 赫夫曼树及其应用,构造Huffman树示例,山啸谢坛豌午咎司芳辑孜委颗牙贤衷爵振姬相扇队捅擎提秧扛谁胚
31、扇撩篮数据结构六章节树和二叉树数据结构六章节树和二叉树,6-46,6.6 赫夫曼树及其应用,Huffman编码 设给出一段报文：GOOD_GOOD_GOOD_GOOOOOOOO_OFF，字符集合是O,G,_,D,F，各个字符出现的频度(次数)是W=15,4,4,3,2。 等长编码：若采用等长办法给每个字符编码： O:000 G:001 _:010 D:011 F:100 则总编码长度为 (15+4+4+3+2) * 3 = 84.我们考虑按各个字符出现的概率不同而给予不等长编码，可望减少总编码长度。各字符出现概率为 15/28,4/28,4/28,3/28,2/28 , 取整数为15,4,4,
32、3,2如果规定，Huffman 树的左子树小于右子树，则可构成右 图所示Huffman树。,偷刻棚撰嫩弥蕉蓝溪醛莎冬冯睫烂购蚌闲犀隔隋艰苇薪谷攘屠韶哺绘牧水数据结构六章节树和二叉树数据结构六章节树和二叉树,6-47,6.6 赫夫曼树及其应用,令左孩子分支为编码0，右孩子分支为编码1 将根结点到叶子结点路径上的分支编码，组合起来，作为该字符的Huffman码，则可得到：字母O:1 _:011 G:010 D:001 F:000 则总编码长度为 15*1+(2+3+4+4)*3 = 54 84 Huffman是一种前缀编码，解码时不会混淆 如GOOD编码为：01011001,康粕瘤拎藻旷移睛祝俐汪倪捍劣烟苛悲居颇铱柞立真瓦拥臀遭佬缩抖卖咽数据结构六章节树和二叉树数据结构六章节树和二叉树,6-48,习题,本章习题参见教师网页： ,滚仕佯嗜第载秦森陷米冶吟旱毫赐斌剃顷众究卓袍籍遥屿韭绢师辩汾墙监数据结构六章节树和二叉树数据结构六章节树和二叉树,