当前位置：文档之家 › 最优二叉树

最优二叉树

  • 格式：doc
  • 大小：49.50 KB
  • 文档页数：6

下载文档原格式

  / 6

合集下载

最优二叉树的逆推调位启发式算法设计

最优二叉树的逆推调位启发式算法设计
小 。 果 ＡＷＰ 一 如 Ｌ Ａ ＞ ， 执行调动命令 ； 则 ， ０则 否
不执行命令 。
（ ） Ａ１Ｐ 一 ＩＰ ≤０ 不 执 行 位 置 的 调 动 ， ４ 若 Ｖ Ｌ增 Ａ Ｖ Ｌ硪 ， 同时 停 止 对 与 该 叶 子 结 点 同 层 的 其 他 实 叶 子结 点 的 比 较 判 定 ．即停 止 该 实 叶 子 结 点 同层 右 侧 的 实 叶 子 结 点
＼
＼ ＼
＼ ＼
— — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — — —
的 比较 判 定 （ 返 回 至第 Ｋ一 层 按 照 步 骤 （ 、５） 方式 做 比 ５） １ ４） （ 的
较 ， ＝ 一 ， 到 把 包 含 实 叶 子 结 点 的所 有 二 又 树 层 比 ＫＫ 直
较完。
（） 束， ６结 由逆 推调 位 算 法构 造 的 最优 二 叉树 确 立 。
以 ６个 权 值 ｛ ，， ， １９ ８ 对 应 的 结 点 为 例 ２６３ １，，｝
逆 推 调 位算 法 哈 夫 曼 算 法
Ｋ＝Ｆｏ ２ ＋ｌ Ｆｏ ６］ ＝ ｌｇ＂ ＝ ｌｇ ＋１ ４ ｑ
④ ④④④ ④⑨
ｎ 夕
把 ｎ个 结 点 容 纳 下 同 时 将 ｎ个 结 点 按 照 权 值 由小 到 大 的 顺 序 依 次 靠 右 填 充 在 该二 叉 树 的第 Ｋ 层 （） ２ 如果 第 层 存 在 空 叶 子结 点 ． 左 侧 结 点 上 调 将 至 第 Ｋ １ 左 侧 放 置 ． 到 第 Ｋ １ 不 存 在 空 叶子 结 一 层 直 一 层 点 为 止 ． 得 调 整 后 的 二 又 树 叶子 结 点 只 出现 在 第 Ｋ 使 —

动态规划-最优二叉搜索树

动态规划-最优二叉搜索树

动态规划-最优⼆叉搜索树摘要： 本章介绍了⼆叉查找树的概念及操作。

主要内容包括⼆叉查找树的性质，如何在⼆叉查找树中查找最⼤值、最⼩值和给定的值，如何找出某⼀个元素的前驱和后继，如何在⼆叉查找树中进⾏插⼊和删除操作。

在⼆叉查找树上执⾏这些基本操作的时间与树的⾼度成正⽐，⼀棵随机构造的⼆叉查找树的期望⾼度为O(lgn)，从⽽基本动态集合的操作平均时间为θ(lgn)。

1、⼆叉查找树 ⼆叉查找树是按照⼆叉树结构来组织的，因此可以⽤⼆叉链表结构表⽰。

⼆叉查找树中的关键字的存储⽅式满⾜的特征是：设x为⼆叉查找树中的⼀个结点。

如果y是x的左⼦树中的⼀个结点，则key[y]≤key[x]。

如果y是x的右⼦树中的⼀个结点，则key[x]≤key[y]。

根据⼆叉查找树的特征可知，采⽤中根遍历⼀棵⼆叉查找树，可以得到树中关键字有⼩到⼤的序列。

介绍了⼆叉树概念及其遍历。

⼀棵⼆叉树查找及其中根遍历结果如下图所⽰：书中给出了⼀个定理：如果x是⼀棵包含n个结点的⼦树的根，则其中根遍历运⾏时间为θ(n)。

问题：⼆叉查找树性质与最⼩堆之间有什么区别？能否利⽤最⼩堆的性质在O(n)时间内，按序输出含有n个结点的树中的所有关键字？2、查询⼆叉查找树 ⼆叉查找树中最常见的操作是查找树中的某个关键字，除了基本的查询，还⽀持最⼤值、最⼩值、前驱和后继查询操作，书中就每种查询进⾏了详细的讲解。

（1）查找SEARCH 在⼆叉查找树中查找⼀个给定的关键字k的过程与⼆分查找很类似，根据⼆叉查找树在的关键字存放的特征，很容易得出查找过程：⾸先是关键字k与树根的关键字进⾏⽐较，如果k⼤⽐根的关键字⼤，则在根的右⼦树中查找，否则在根的左⼦树中查找，重复此过程，直到找到与遇到空结点为⽌。

例如下图所⽰的查找关键字13的过程：（查找过程每次在左右⼦树中做出选择，减少⼀半的⼯作量）书中给出了查找过程的递归和⾮递归形式的伪代码：1 TREE_SEARCH(x,k)2 if x=NULL or k=key[x]3 then return x4 if(k<key[x])5 then return TREE_SEARCH(left[x],k)6 else7 then return TREE_SEARCH(right[x],k)1 ITERATIVE_TREE_SEARCH(x,k)2 while x!=NULL and k!=key[x]3 do if k<key[x]4 then x=left[x]5 else6 then x=right[x]7 return x（2）查找最⼤关键字和最⼩关键字 根据⼆叉查找树的特征，很容易查找出最⼤和最⼩关键字。

最优二叉树（哈夫曼树）的构建及编码

最优二叉树（哈夫曼树）的构建及编码

最优⼆叉树（哈夫曼树）的构建及编码参考：数据结构教程（第五版）李春葆主编⼀，概述1，概念 结点的带权路径长度： 从根节点到该结点之间的路径长度与该结点上权的乘积。

树的带权路径长度： 树中所有叶结点的带权路径长度之和。

2，哈夫曼树（Huffman Tree） 给定 n 个权值作为 n 个叶⼦结点，构造⼀棵⼆叉树，若该树的带权路径长度达到最⼩，则称这样的⼆叉树为最优⼆叉树，也称为哈夫曼树。

哈夫曼树是带权路径长度最短的树，权值较⼤的结点离根较近。

⼆，哈夫曼树的构建1，思考 要实现哈夫曼树⾸先有个问题摆在眼前，那就是哈夫曼树⽤什么数据结构表⽰？ ⾸先，我们想到的肯定数组了，因为数组是最简单和⽅便的。

⽤数组表⽰⼆叉树有两种⽅法： 第⼀种适⽤于所有的树。

即利⽤树的每个结点最多只有⼀个⽗节点这种特性，⽤ p[ i ] 表⽰ i 结点的根节点，进⽽表⽰树的⽅法。

但这种⽅法是有缺陷的，权重的值需要另设⼀个数组表⽰；每次找⼦节点都要遍历⼀遍数组，⼗分浪费时间。

第⼆种只适⽤于⼆叉树。

即利⽤⼆叉树每个结点最多只有两个⼦节点的特点。

从下标 0 开始表⽰根节点，编号为 i 结点即为 2 * i + 1 和 2 * i + 2，⽗节点为 ( i - 1) / 2，没有⽤到的空间⽤ -1 表⽰。

但这种⽅法也有问题，即哈夫曼树是从叶结点⾃下往上构建的，⼀开始树叶的位置会因为⽆法确定⾃⾝的深度⽽⽆法确定，从⽽⽆法构造。

既然如此，只能⽤⽐较⿇烦的结构体数组表⽰⼆叉树了。

typedef struct HTNode // 哈夫曼树结点{double w; // 权重int p, lc, rc;}htn;2，算法思想 感觉⽐较偏向于贪⼼，权重最⼩的叶⼦节点要离根节点越远，⼜因为我们是从叶⼦结点开始构造最优树的，所以肯定是从最远的结点开始构造，即权重最⼩的结点开始构造。

所以先选择权重最⼩的两个结点，构造⼀棵⼩⼆叉树。

然后那两个最⼩权值的结点因为已经构造完了，不会在⽤了，就不去考虑它了，将新⽣成的根节点作为新的叶⼦节加⼊剩下的叶⼦节点，⼜因为该根节点要能代表整个以它为根节点的⼆叉树的权重，所以其权值要为其所有⼦节点的权重之和。

哈夫曼编码

哈夫曼编码
15
例：证明：一棵二叉树的前序序列和中序序 列可以唯一的确定这棵二叉树。
用归纳法证明： 1、当 n = 1时，结论显然成立； 2、假定当 n <= k 时，结论成立； 3、当 n = k + 1 时，假定前序序列为和中序序列 分别为： {a1，…，am} 和 {b1， … ，bm}
16
如 中 序 序 列 中 与 前 序 序 列 a1 相 同 的 元 素 为 b j 。 j =1时，二叉树无左子树，由 {a2，…，am} 和
先举例！
3
例1：设有4个字符d,i,a,n，出现的频度分别为7,5,2, 4，
怎样编码才能使它们组成的报文在网络中传得最快？ 法1：等长编码。例如用二进制编码来实现。 取 d=00，i=01，a=10，n=11
法2：不等长编码，例如用哈夫曼编码来实现。 取 d=0; i=10, a=110, n=111 最快的编码是哪个？是非等长的Huffman码！
提示2：霍夫曼树的存储结构可采用顺序存储结构： 将整个霍夫曼树的结点存储在一个数组中：HT[1..n]; 将结点的编码存储在HC[1..n]中。 提示3：霍夫曼树如何构造？构造好之后又如何求得 各结点对应的霍夫曼编码？——算法参见教材P147。
参考 实验二补充材料中的方案二程序； 资料 喻信星空FTP网站上的“数据结构”演示程序
注：若圆满实现了此方案，平时成绩将以满分计。
字符 空格 频度 186 a 64 b 13 c 22 d 32
e
103
f 21
g 15
h 47
i 57
字符 频度
字符 频度
j 1
k 5
u 23
l 32
v 8
m 20
w 18

最优二叉树

最优二叉树

哈夫曼编码的另一种表示： 1.00
0 0.40 0 g 0.21 1
1
b 0.19
0
0.28 0 0.17 1
0.60 1 e 0.32
0.11 0 1
0
1 d 0.07 0.06
h 0.10
哈夫曼编码树
a
0.05
0 f 0.03 1 c 0.02
练习题：设计哈夫曼编码，通信中可能有8种字符,其频率 分别为:0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11
0 d
1
0
i 0 a
1
1 n
Huffman编码结果：d=0, i=10, a=110, n=111 WPL=1bit×7＋2bit×5+3bit(2+4)=35（小于等长码的WPL=36） 特征：每一码不会是另一码的前缀，译码时唯一，不会错! Huffman编码也称为前缀码
Huffman编码
哈夫曼编码的基本思想是——— 出现概率大的信息用短码，概率小的用长码
最佳判定方法
Y Y E Y D Y a<60 N a<70 N C Y B Y D 70a<80 N 80a<90 N 60a<70 N
a<80
N a<90 N A
Y
E
C
Y B
a<60
N A
(b)WPL=40x1+30x2+15x3+5x4+10x4=205
(a)WPL=10x4+30x4+40x3+15x2+5x1=315
void Select (HuffmanTree HT,int t,int&s1,int&s2) {//在HT[1...t]中选择parent为0且权值最小的两个结点，其 序号分别为s1和s2 int i, m, n; m=n=100000; for(i=1;i<=t;i++) {if(HT[i].parent==0&&(HT[i].weight<m||HT[i].weight<n)) if(m<n) { n=HT[i].weight ; s2=i ; } else { m=HT[i].weight ; s1=i ; } } if(s1>s2) //s1放较小的序号 {i=s1;s1=s2;s2=i;} }

32.二叉树与最优二叉树

32.二叉树与最优二叉树
通信中八进制数出 现的频率如下：
0 1 2 3 4 5 30% 20％ 15% 10％ 10％ 5% 6 5% 7 5％
求传输它们的最佳前缀 码。
参考答案： 0 01 1 11 2 3 4 5 6 7 1001
001 101 0000 0001 1000
教师：田检
30
教师：田检
60 20 10 15 10 15 0 01 10 5 0 00 1 5 0 00 00 5 0 00 01 0 10 10 0 11 0 10 0 11 1 20 10
40 20
25
35
10 1 11
1 10
图 9.2.11
w0=20； w1=15；w2=10；w3=10； w4=10； w5=5； w6=10； w7=5； w8=10；w9=5。
教师：田检
26
解 （1）令i对应树叶权为wi，wi=100i，则 w0=20；w1=15；
w2=10；w3=10； w4=10；w5=5； w6=10；w7=5； w8=10；w9=5。 构造一棵带权5,5,5,10,10,10,10,10,15, 20的最优二叉树。
教师：田检
27
1 00 0 —10 1 —01 0 2 —11 1 3 —11 0 4 —01 11 5 —00 01 6 —01 10 7 —00 00 1 8 —00 1 9 —00 00 0
31
16 16
10 10
最优二叉树不唯一！
6
6
4
6 3
1
3
2
4
6
3
1 2
3
教师：田检
18
练习 1：求带权为 2,4,7,8,10,12的最优二叉树 43

最优二叉搜索树


8
2 最优二叉搜索树
xal
wan wil wen wim wul xem yo xul yu m
zol zom
yon
zi
A
A代表其值处于 代表其值处于wim和wul之间的可能关键码集合 代表其值处于 和 之间的可能关键码集合
9
2 最优二叉搜索树
在二叉搜索树中搜索一个元素x 在二叉搜索树中搜索一个元素
1 2 3 2 (c) (d) (a) (b) (e) 1 3 1 2 1 3 2 1 2 3
• 设每个内、外结点检索的概率相同：pi=qi=1/7， 设每个内、外结点检索的概率相同： ， 求每棵树的平均比较次数（成本）。 求每棵树的平均比较次数（成本）。 • 若P1=0.5, P2=0.1, P3=0.05, q0=0.15, q1=0.1, q2=0.05, q3=0.05，求每棵树的平均比较 ， 次数（成本）。 次数（成本）。 13
2 最优二叉搜索树
在检索过程中，每进行一次比较，就进入下面一层， 在检索过程中，每进行一次比较，就进入下面一层， • 对于成功的检索，比较的次数就是所在的层数加 。 对于成功的检索，比较的次数就是所在的层数加1。 • 对于不成功的检索，被检索的关键码属于那个外部结 对于不成功的检索， 点代表的可能关键码集合， 点代表的可能关键码集合，比较次数就等于此外部结 点的层数。 点的层数。
6
2 最优二叉搜索树
2、最优二叉搜索树 、
存在的两个问题 1 在实际中也会遇到不成功检索的情况。 在实际中也会遇到不成功检索的情况。 不成功检索的情况 2 在实际中，不同标识符会有不同的检索概率。 在实际中，不同标识符会有不同的检索概率。 不同的检索概率 • 对给定的标识符集合，希望给出构造二分搜索 对给定的标识符集合， 树的方法，使得所构造的二分搜索树具有最优 树的方法，使得所构造的二分搜索树具有最优 的性能。 的性能。

最优二叉搜索树

最优⼆叉搜索树背景：语⾔翻译，从英语到法语，对于给定的单词在单词表⾥找到该词⽅法：创建⼀棵⼆叉搜索树，以英语单词作为关键字构建树⽬标：尽快地找到英语单词，使总的搜索时间尽量少思路：频繁使⽤的单词，如the应尽可能的靠近根；⽽不经常出现的单词可以离根远⼀点前提假设：所有元素互异⼀些定义：⼆叉搜索树⼆叉搜索树T是⼀棵⼆元树，它或者为空，或者其每个结点含有⼀个可以⽐较⼤⼩的数据元素，且有：T的左⼦树的所有元素⽐根结点中的元素⼩；T的右⼦树的所有元素⽐根结点中的元素⼤；T的左⼦树和右⼦树也是⼆叉搜索树。

最优⼆叉搜索树给定含有n个关键字的已排序的序列K=<k1,k2,…,k n>（不失⼀般性，设k1<k2<…<k n），对每个关键字k i，都有⼀个概率p i表⽰其被搜索的频率。

根据k i和p i构建⼀个⼆叉搜索树T，每个k i对应树中的⼀个结点。

搜索对象x，在T中可能找到、也可能找不到：若x等于某个k i，则⼀定可以在T中找到结点k i，称为成功搜索。

成功搜索的情况⼀共有n种，分别是x恰好等于某个k i。

若x<k1或x>k n或k i<x<k i+1(1≤i<n), 则在T中搜索x将失败，称为失败搜索。

为此引⼊外部结点d0,d1,...,d n，⽤来表⽰不在K中的值,称为伪关键字。

伪关键字在T中对应外部结点,共有n+1个。

—扩展⼆叉树：内结点表⽰关键字k i，外结点(叶⼦结点)表⽰d i这⾥每个d i代表⼀个区间。

d0表⽰所有⼩于k1的值，d n表⽰所有⼤于k n的值，对于i=1,…,n−1，d i表⽰所有在k i和k i+1之间的值。

每个d i也有⼀个概率表⽰搜索对象x恰好落q i⼊区间d i的频率。

⼆叉搜索树的期望搜索代价⼀次搜索的代价等于从根结点开始访问结点的数量（包括外部结点）。

从根结点开始访问结点的数量等于结点在T中的深度+1。

记depth T(i)为结点i在T中的深度。

数据结构哈夫曼树和哈夫曼编码PPT课件


C
AB
AC
BC
ABC
第27页/共55页
回朔策略—求幂集
000
000
100
000
010
100
110
000
001
010
011 100 101 110
111
第28页/共55页
回朔策略—求幂集
void powerSet(int num){ if (num<=len-1) { for (int i=0; i<2; i++){ if (i = = 0) mask[num]=1; else mask[num]=0; powerSet(num+1);} } else{ for (int j=0; j<len; j++){ if (mask[j]==1) printf("%c",set[j]);} printf("\n");}
}
第29页/共55页
回朔策略—求幂集
int len=3; int mask[]={0,0,0}; char set[]={'A','B','C'}; int main(int argc, char* argv[]) {
powerSet(0); return 0; }
第30页/共55页
章末复习
1. 熟练掌握二叉树的结构特性，了解相应的证 明方法。 2. 熟悉二叉树的各种存储结构的特点及适用范 围。 3. 遍历二叉树是二叉树各种操作的基础。实现 二叉树遍历的具体算法与所采用的存储结构有 关。掌握各种遍历策略的递归算法，灵活运用 遍历算法实现二叉树的其它操作。层次遍历是 按另一种搜索策略进行的遍历。

哈夫曼压缩算法

文件压缩总结（哈夫曼压缩）在学习哈弗曼压缩之前，还是首先来了解什么是哈夫曼树，哈夫曼编码。

1.哈夫曼树是一种最优二叉树，它的带权路径长度达到最小。

树的带权路径长度为所有叶子结点带权路径长度之和。

而结点的带权路径长度是结点的路径长度乘以结点的权值。

2.哈夫曼编码是依据字符出现概率来构造异字头的平均长度最短的码字。

从哈弗曼树的根结点开始，按照左子树代码为“0”，右子树代码为“1”的规则，直到树的叶子结点，每个叶子结点的哈弗曼编码就是从根结点开始，将途中经过的枝结点和叶子结点的代码按顺序串起来。

哈夫曼压缩是字节符号用一个特定长度的01序列替代，在文件中出现频率高的符号，使用短的01序列，而出现频率少的字节符号，则用较长的01序列表示。

这里的文件压缩，我还只能做简单的文件A-->压缩为文件B--->解压为文件C，看文件A和文件C是不是相同。

那么就要分两个大步骤，小步骤：不过，根据哈弗曼树的特点，我们首先还是要定义结点类型结点类型代码1.public class TreeNode {2. public TreeNode parent; //双亲结点3. public TreeNode left; //左孩子结点4. public TreeNode right; //右孩子结点5.6. public byte con;// 结点的数据7. public int rate;8. public String bian="";9. public int count=0;10. public TreeNode(byte con, int rate) {11. super();12. this.con= con;13. this.rate = rate;14. }15. }然后分两大步骤一. 首先压缩文件1. 将源文件A中数据按字节读取，然后用MAP统计每个字节出现的次数（Key--不同的字节，value--次数）。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
if(min > BH[k]->weight)
{m1=k;
min = BH[k]->weight;
}
}
min = 1000000;
for(int a=0;a<m1;a++)
{
if(BH[a]!=NULL)
if(min>BH[a]->weight)
{
m2=a;
min = BH[a]->weight;
}
PreOrder(abc);
free(abc);
}
运行结果：
实验结论：
指导教师批阅意见：
成绩评定：
指导教师签字：
年月日
备注：
注：1、报告内的项目或内容设置，可根据实际情况加以调整和补充。
2、教师批改学生实验报告时间应在学生提交实验报告时间后10日内。
bt->lchild=BH[m1];
bt->rchild=BH[m2];
BH[m1]=bt;
BH[m2]=NULL;
rn--;
}
return BH[m1];
}
void PreOrder(BHTree BH)
{
if(BH)
{
printf("%d ",BH->weight);
PreOrder(BH->lchild);
深圳大学实验报告
课程名称：数据结构
实验项目名称：最优二叉树
学院：医学院
专业：生物医学工程
指导教师：倪东
报告人：马镇荣学号：2010222046班级：2
实验时间：2011-12-24
实验报告提交时间：2011-12-24
教务部制
一.实验目的：
掌握Haffman树的创建
二实验内容
用二叉链表作为二叉树的物理存储结构；
int rn=n;
CreateSmallTree(BH,n);
BHTree bt;
while(rn>1)
{
SortTwoTree(BH,n,m1,m2);
bt=(BHTree)malloc(sizeof(BHNode));
bt->weight =BH[m1]->weight+BH[m2]->weight;
struct BHNode *rchild;
}BHNode,*BHTree;
void CreateSmallTree(BHTree BH[], int n)
{
for(int i=0;i<n;i++)
{
BH[i]=(BHTree)malloc(sizeof(BHNode));
scanf("%d",&BH[i]->weight);
输入权重；
根据输入的权重，建立Haffman树；
利用遍历的方法验证Haffman树；
实验程序：
#include "stdafx.h"
#include "stdio.h"
#include "malloc.h"
typedef struct BHNode
{
int weight;
struct BHNode *lchild;
PreOrder(BH->rchild);
}
//else printf("");
}
void main()
{
int n;
printf("请输入权重的个数：");
scanf("%d",&n);
printf("请输入权重（输入一次回车一次）:\n");
BHTree abc= CreateHuffmanTree(n);
BH[i]->lchild=NULL;
BH[i]->rchild=NULL;
}
}
void SortTwoTree(BHTree BH[],int n,int &m1,int &m2)
{
//m1=0,m2=0;
int min = BH[0]->weight;
for(int k=1;k<n;k++)
{
if(BH[k]!=NULL)
}
for(a=m1+1;a<n;a++)
{
if(BH[a]!=NULL)
if(min>BH[a]->weight)
{
m2=a;
min = BH[a]-ቤተ መጻሕፍቲ ባይዱweight;
}
}
}
BHTree CreateHuffmanTree(int n)
{
BHTree BH[20];
int m1=0,m2=0;//m1,m2是两个权值最小的数的位置