网站大量收购闲置独家精品文档,联系QQ:2885784924

树与二叉树的关系.ppt

  1. 1、本文档共61页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
带权路径长度:在树形结构中,我们把从树根到某一结点的路径长度与该结点权的乘积,称做该结点的带权路径长度。 树的带权路径长度:树中所有叶子结点的带权路径长度之和,称为树的带权路径长度,通常记为WPL: WPL=?wi×li i=1 n 其中:n为叶子结点的个数;wi为第i个叶子的权值; li为第i个叶子结点的路径长度。 结点的权:给树中每个结点赋予一个具有实际意义的数值,我们称该数值为这个结点的权。 例如下图所示的三棵二叉树 WPL(a)=7×2+5×2+2×2+4×2=36 其带权路径长度分别为: 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(b)=4×2+7×3+5×3+2×1=46 WPL(c)=7×1+5×2+2×3+4×3=35 什么样的树的带权路径长度WPL最小? 例如:给定一个权值序列{2, 4, 5, 7},可构造多种二叉树的形态: 问题2: 2 4 5 7 a 7 5 4 b 2 5 4 2 c 7 WPL(a) = 36 WPL(b) = 46 WPL(c)=35 其带权路径长度分别为: 在各种形态的含有 n个叶子结点的 二 叉树中, 必存在一棵(几棵)其带权路径长度值WPL 最小的树,被称为“最优二叉树” 。 特征:在最优二叉树中没有度数为 1 的结点(可用反证法证明); 含 n个叶子结点的最优二叉树的总结点数为 2*n-1 (依据二叉树性质三)。 最优二叉树的构造方法最早由哈夫曼研究,所以又称为“哈夫曼树”。 二、哈夫曼树的构造 (1) 根据给定的 n 个权值 {w1, w2, …, wn} ,构造 n 棵二叉树的集合 F = {T1, T2, … , Tn}, 其中每棵二叉树中均只含一个带权值为 wi 的根结点,其左、右子树为空树; 构造哈夫曼树的方法: 在 F 中选取其根结点的权值为最小的两棵二叉树, 分别作为左、右子树构造一棵新的二叉树, 并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和; (2) 从F中删去这两棵树,并加入刚生成的新树; 重复 (2) 和 (3) ,直至 F 中只含一棵树为止。 (3) (4) 由此得到二叉树就是“最优二叉树” 即“哈夫曼树” 。 例如: 已知权值 W={ 5, 6, 2, 9, 7 } 9 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 构造哈夫曼树如下: 9 5 2 7 16 6 7 13 29 三、哈夫曼算法的实现 n个叶子结点的哈夫曼树共有2n-1个结点,因此可用有2n-1个元素的数组来存储哈夫曼树, 结点间的关系用游标表示,即采用静态链表来存储哈夫曼树。 1、存储结构 每个结点需包含其双亲结点信息和孩子结点信息,所以构成一个静态三叉链表。 weight parent Lchild Rchild 权值 双亲序号 左孩子序号 右孩子序号 静态三叉链表结构定义 #define N 20 #define M 2*N-1 typedef struct { int weight ; int parent,Lchild,Rchild ; }HTNode, HuffmanTree[M+1]; /*0号单元不用*/ 静态三叉链表数组中前 n 个元素存储叶子结点,后n-1个元素存储分支结点即不断生成的新结点,最后一个元素存储哈夫曼树的根结点。 2、哈夫曼算法 初始化:先将n个元素都视为根结点,即孩子和双亲指针全置0。 建哈夫曼树的过程是:反复在数组中选双亲为0(表示它们当前是树根)且权值最小的两结点, 将它们作为左右孩子挂在新的结点之下, 新结点权值为左右孩子权值之和。 void CrtHuffmanTree(HuffmanTree ht , int w[], int n) { /* w存放已知的n个权值,构造哈夫曼树ht */ } m=2*n-1; for(i=1;i=n;i++) ht[i]={w[i],0,0,0}; for(i=n+1;i=m;i++) ht[i]={0,0,0,0}; for(i=n+1;i=m;i++) { select(ht,i-1,s1,s2); /*ht前i-1项选双亲为零且权最小的两结点*/ ht[s1]

文档评论(0)

wuyoujun92 + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档