4.3.3 最优二叉树+二叉查找树
文章目录
- 基本概念
- 哈夫曼方法
- 应用：通信编码译码
- 二叉查找树
基本概念
最优二叉树=哈夫曼树
哈夫曼树：带权路径长度最短的树。
路径：一个结点到另一个结点的通路。
路径长度：路径上的分支数量。
树的路径长度：根到每个叶子结点路径长度之和。
结点带权路径长度：结点到根的路径长度乘以结点权值。
树的带权路径长度：所有叶子结点带权路径长度之和。
哈夫曼方法
① 将n个权值转换成n棵二叉树的根结点，二叉树的集合为F。
② F中根结点权值最小的2棵树X, Y，组成新树Z的左、右子树，根结点为左右子树权值之和。
③ 删除F中X，Y这2棵树，新树Z加入F。
重复②和③，直至F中剩下1颗树，这就是哈夫曼树。
应用：通信编码译码
字符和权值用哈夫曼方法形成哈夫曼树，树的左分支标0，右分支标1。根到叶子路径的01字符串就是字符的编码。
helloworld的编码为
0000 0001 001 001 100 101 100 01 001 11
译码时，按照01字符串的顺序，从哈夫曼树的根结点开始读取，找到叶子结点，就返回对应字符。然后回到根结点，继续寻找，直至01字符串读取完毕。
二叉查找树
二叉查找树=二叉排序树=二叉检索树
具有3个性质：
- 左树所有结点的值均小于根结点
- 右树所有节点的值均大于根节点
- 左、右子树也是二叉查找树
二叉查找树中序遍历，可以得到递增序列。