- 1、本文档共12页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
会计学; 1. 基本概念
路径:从一个结点到另一个结点之间的分支.
路径长度:路径上分支数目.
结点的路径长度:从根结点到该结点的路径长度.
树的路径长度:树中每个结点的路径长度之和.
完全二叉树这种长度最短的二叉树.
结点的带权路径长度:该结点的路径长度*结点的权值
树的带权路径长度:树中所有叶子结点的带权路径长度之和.记作:WPL=∑wklk 例如
最优二叉树:在所有含n个叶子结点、并带相同权值的二叉树中,必 存在WPL最小的二叉树.又叫Huffman树;W={7,2,4,5,9}; 在解决某些判定问题时,利用Huffman树可得
到最佳判定算法
例如,某厂生产螺钉,要求直径为d,误差σ.现测量某螺钉直径,方法与标准的比较,判定树?; 2. Huffman树的构造(自底向上)
; 接上页:; 构造过程(Huffman算法)
(1) n个权值构成n棵独立二叉树的森林F={T1,…Tn}
(2)在森林中选出两棵根权值最小的二叉树作为左右子树,构造二叉树,根权值为左右子树的和
(3) 在F中删除这两棵,新构成的添加到F中
(4)重复(2)和(3),直到F中含一棵二叉树为止.;
两个结论:
(1) 在Huffman树中没有度为1的结点.
(2) 一棵有n个叶子结点的Huffman树共有2n-1个结点.证明?
; 3. Huffman编码
(1) 等长编码
(2) 不等长编码:出现多的字符采用短码,总长短了!
但出现二义性!
(3) 前缀编码:一个字符的编码都不是另一个字符的编码的前缀.; (4) Huffman编码:设计Huffman树而得到的编码.
例如:有8种字符,概率如下:
{0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11}
解:同时扩大100倍,得权值集合:
{5,29,7,8,14,23,3,11};
作业:;本章小结
1. 掌握树的定义,表示形式和术语(二叉树通用)
掌握树的存储结构(孩子-兄弟表示)
掌握树与二叉树的转换
了解树的ADT定义与树和森林遍历
2. 掌握二叉树的ADT定义,特点,结点的形态,性质,存储结构(二叉链表)
掌握二叉树的遍历,线索的方法
掌握遍历算法的应用
掌握二叉树与树和森林的转换
掌握Huffman树概念,构造和编码
文档评论(0)