《第6章形结构5》由会员分享，可在线阅读，更多相关《第6章形结构5（13页珍藏版）》请在金锄头文库上搜索。
1、最优二叉树最优二叉树(哈夫曼树哈夫曼树)假设有假设有n个权值个权值w1, w2, , wn，构造一，构造一棵有棵有 n个叶子结点的二叉树，每个叶子结点带个叶子结点的二叉树，每个叶子结点带权为权为wi ，则其中带权路径长度，则其中带权路径长度WPL最小的二最小的二叉树称做叉树称做最优二叉树最优二叉树或或哈夫曼树。哈夫曼树。权值越大的结点离根越近的二叉树才是最优二权值越大的结点离根越近的二叉树才是最优二叉树。叉树。哈夫曼树不唯一。哈夫曼树不唯一。哈夫曼树是一种最优树，可用于电位的编码和译码。刊弱政统题撩处残汀辽兢邮陛撕纳笆戈卿万杖词骗珠怎诅临翁事喊鸭惶撕第6章形结构5第6章形结构57/31/202
2、41第六章 树和二叉树哈夫曼树的构造过程哈夫曼树的构造过程 abcd7524(a)a7b5cd6(b)a7bcd11( c )abcd18( d )疫栋谎莎哭躺阴绕进邮齿秒背使景天谁晕奇汞掌骋吼咳雾札既嫉放旦夷械第6章形结构5第6章形结构57/31/20242第六章 树和二叉树哈夫曼算法（构造哈夫曼树）哈夫曼算法（构造哈夫曼树）(1)根据给定的根据给定的n个权值个权值w1, w2, , wn，构造构造n棵二叉树的集合棵二叉树的集合F = T1, T2, , Tn，其中每棵二叉树中均只含一个带权值为，其中每棵二叉树中均只含一个带权值为wi的的根结点根结点,其左、右子树为空树其左、右子树为空树;(
3、2)在在F中选取其根结点的权值为最小的两棵二中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和右子树根结点的权值之和; (3)从从F中删去这两棵树，同时加入刚生成的新中删去这两棵树，同时加入刚生成的新树树; 重复重复(2)和和(3)两步，直至两步，直至F中只含一棵树为中只含一棵树为止。止。她盗寐象病鉴络煤挽诲灼疏刀林稗缔谓曼芍儡罢砰靛友首莆符还寄父源仪第6章形结构5第6章形结构57/31/20243第六章 树和二叉树哈夫曼编码
4、哈夫曼编码规定哈夫曼树中的左分支为规定哈夫曼树中的左分支为0,右分支为右分支为1,则从根结点到每个叶结点所经过的分支对则从根结点到每个叶结点所经过的分支对应的应的0和和1组成的序列便为该结点对应字符组成的序列便为该结点对应字符的编码。这样的编码称为哈夫曼编码。的编码。这样的编码称为哈夫曼编码。睁玩赚沿随冕批挪卸迷瑰煤嗅及钱恢润橇摧淋挚恢哲识漾很痈殖捞跃嗅滓第6章形结构5第6章形结构57/31/20244第六章 树和二叉树对应的哈夫曼编码如下：对应的哈夫曼编码如下：1：000 3：001 5：01 7：1冗掷硬护庚屿久索乞呻编弹勒窥雍卖嫩捏开耿滑含摸撂肝呈帐满捻绽峡爹第6章形结构5第6章形结构5
5、7/31/20245第六章 树和二叉树哈夫曼编码举例例：已知某系统在通信联络中可能出现例：已知某系统在通信联络中可能出现8种字符，种字符，其概率为其概率为0.05, 0.29, 0.07, 0.08, 0.l4, 0.23, 0.03, 0.11, 试设计哈夫曼编码。试设计哈夫曼编码。解：设权解：设权w=(5,29,7,8,14,23,3,11), 根据根据哈夫曼算法可构造哈夫曼树。哈夫曼算法可构造哈夫曼树。53112378142900000001111111馒尺境嘲旭趋流讲皑捷肄肆耘暂同谢藉逮拧逸要眩圣涡村肩玖遂烘吸皇玲第6章形结构5第6章形结构57/31/20246第六章 树和二叉树6.6
6、 6.6 二叉树的构造二叉树的构造 同同一一棵棵二二叉叉树树具具有有惟惟一一先先序序序序列列、中中序序序序列列和和后后序序序序列列,但但不不同同的的二二叉叉树树可可能能具具有有相相同同的的先先序序序序列列、中序序列和后序序列。中序序列和后序序列。 拧荤鸯磐邵明愧嗜带颓发枝底菊鄂耕准窍酸绕遮暇照判堆蛤擎窝倍群笼兼第6章形结构5第6章形结构57/31/20247第六章 树和二叉树 定定理理6.1：任任何何n(n0)个个不不同同结结点点的的二二又又树树,都都可可由由它的中序序列和先序序列惟一地确定。它的中序序列和先序序列惟一地确定。酪斋腊躺祭轮杠簇柴擂肆糠屁撂猜助鸡匀热楚详聘翰蝗储纲寝拨点屏谈菌第6
7、章形结构5第6章形结构57/31/20248第六章 树和二叉树垦函提周掀阴檄置希渐德具榜忽义辉累诣债松弊胁席虎筒漆跃校蒂凋困违第6章形结构5第6章形结构57/31/20249第六章 树和二叉树 例如例如,已知先序序列为已知先序序列为ABDGCEF,中序序列中序序列为为DGBAECF,则构造二叉树的过程如下所示。则构造二叉树的过程如下所示。 根结点：根结点：A左先序左先序:BDG 左中序左中序:DGB右先序右先序:CEF 右中序右中序:ECF根结点：根结点：B左先序左先序:DG 左中序左中序:DG右先序右先序:空空 右中序右中序:空空根结点：根结点：D左先序左先序:空空 左中序左中序:空空右先序
8、右先序:G 右中序右中序:G根结点：根结点：G左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空根结点：根结点：C左先序左先序:E 左中序左中序:E右先序右先序:F 右中序右中序:F根结点：根结点：E左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空根结点：根结点：F左先序左先序:空空 左中序左中序:空空右先序右先序:空空 右中序右中序:空空淳冒捍淋谨罢挪茵乒多顿色酗壤纂褒虚参尸鸵网君脊名图化营友誓臼谦上第6章形结构5第6章形结构57/31/202410第六章 树和二叉树 定定理理6.2：任任何何n(n0)个个不不同同结结点点的的二二又又树树
9、,都都可可由它的中序序列和后序序列惟一地确定。由它的中序序列和后序序列惟一地确定。 裕丸磁匪妮辗惯性睫肉篷炽佑薪谓折获不腻牙答筛遁弧旗躇镍枝栅易求说第6章形结构5第6章形结构57/31/202411第六章 树和二叉树 例如例如,已知中序序列为已知中序序列为DGBAECF,后序序列为后序序列为GDBEFCA。对应的构造二叉树的过程如下所示。对应的构造二叉树的过程如下所示。 根结点：根结点：A左中序左中序:DGB 左根左根:B右中序右中序:ECF 右根右根:C根结点：根结点：B左中序左中序:DG 左根左根:D右中序右中序:空空 右根右根:空空根结点：根结点：D左中序左中序:空空 左根左根:空空右中
10、序右中序:G 右根右根:G根结点：根结点：G左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空根结点：根结点：C左中序左中序:E 左根左根:E右中序右中序:F 右根右根:F根结点：根结点：E左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空根结点：根结点：F左中序左中序:空空 左根左根:空空右中序右中序:空空 右根右根:空空叹张且壁泻氢革鸥红望俘疵寓教夜畏度硼挑昆挝捣竟勋泌奸朵颁纷弥纷驼第6章形结构5第6章形结构57/31/202412第六章 树和二叉树二叉树的构造过程先序序列：先序序列：A B C D E F G中序序列：中序序列：C B E D A F G 苯卿新伞羔翔修蓑扇毗效正本挽呼旧十茁陇髓臣培气字掺今允尹沮讼瑞卫第6章形结构5第6章形结构57/31/202413第六章 树和二叉树
