当前位置:首页 >> 学科竞赛 >> 树与二叉树、哈夫曼树学案

树与二叉树、哈夫曼树学案


信息学

科学案

序号

高一

年级



学生

树与二叉树学案
一、树的定义及特点 树(tree)是 n(n>0)个结点的有限集 T。 特点: 树中至少有一个结点——根,树的根结点没有_______________,

除根结点以外的所有结点有_______个前驱结点。 树的所有结点都可以有_______________个后继结点。 二、树的术语 结点(node)——表示树中的元素,包括数据项及若干指向其子树的分支 度(degree)——结点拥有的子树数 叶子(leaf)——度为 0 的结点 孩子(child)——结点子树的根称为该结点的孩子 双亲(parents)——孩子结点的上层结点叫该结点的双亲 兄弟(sibling)——同一双亲的孩子 树的度——一棵树中最大的结点度数 层次(level)——从根结点算起,根为第一层,它的孩子为第二层…… 深度(depth)——树中结点的最大层次数 结点 A 的度:__________ 森林(forest)——m(m>=0)棵互不相交的树的集合 结点 B 的度:__________ 结点 M 的度:__________ 结点 A 的孩子:__________ 结点 B 的孩子:__________ 树的度:___________________ B C D 叶子:___________________ 结点 I 的双亲:_________ E F G H I J 结点 L 的双亲:_________ 结点 B,C,D 为_________ 结点 K,L 为____________ K L M 结点 A 的层次:_________ 结点 M 的层次_________ 三、二叉树定义及特点 树的深度_______________ 定义:二叉树是 n(n>=0)个结点的有限集,它或为空树(n=0),或由一个根结点和两棵分别称为左子树和右子树的互不相 交的二叉树构成。 特点: ① 每个结点至多有二棵子树(即不存在度大于 2 的结点) ② 二叉树的子树有左、右之分,且其次序不能任意颠倒 四、二叉树的性质 性质 1 在二叉树的第 i 层上至多有________________个结点(i>=1) 性质 2 深度为 k 的二叉树至多有___________________个结点(k>=1) 性质 3 对任何一棵二叉树 T,如果其终端结点数为 n0,度为 2 的结点数为 n2,则 n0 和 n2 的关系:______________ 证明: 因为二叉树中所有结点的度均不大于 2,所以结点总数(记为 n)应等于 0 度结点数、1 度结点(记为 n1)和 2 度 结点数(记为 n2)之和 n=_____________(式子 1) 另一方面,1 度结点有一个孩子,2 度结点有两个孩子,故二叉树中孩子结点总数是:n1+2n2,树中只有根结点不 是任何结点的孩子,故二叉树中的结点总数又可表示为 n=_____________(式子 2) A

由式子 1 和式子 2 得到:_____________________ 五、满二叉树 定义:一棵深度为 k 且有 2k-1 个结点的二叉树称为满二叉树。 特点: 每一层上的结点数都达到最大值 满二叉树中不存在度数为 1 的结点,每个结点均有两棵高度相同的子树,且树叶都在最下一层。 六、完全二叉树 定义:若一棵二叉树至多只有最下面的两层上结点的度数小于 2,并且最下一层上的结点都集中在该层最左边的若干位 置上,则此二叉树称为完全二叉树。 特点: 满二叉树是完全二叉树,完全二叉树不一定是满二叉树。 在满二叉树的最下一层上,从最右边开始连续删去若干结点后得到的二叉树仍然是一棵完全二叉树。 若某个结点没有左孩子,则它一定没有右孩子,即该结点必是叶子结点。 例:已知一棵完全二叉树共有 892 个结点,试求: ① 树的高度___________________ ② 叶子结点数___________________ ③ 单支结点数___________________ ④ 最后一个非终端结点的序号___________________ 七、二叉树的遍历 NLR:前序遍历,访问结点的操作发生在遍历其左右子树之前 LNR:中序遍历,访问结点的操作发生在遍历其左右子树之中(间) LRN:后序遍历,访问结点的操作发生在遍历其左右子树之后 【练习】 1. 一棵完全二叉树上有 1001 个结点,其中叶子结点的个数是( ) A A.250 B.500 C.254 D.505 E.以上答案都不对 2. 将有关二叉树的概念推广到三叉树,则一棵有 244 个结点的完全三叉树的高度是( ) A.4 B.5 C.6 D.7 B 3. 某二叉树中序序列为 abcdefg,后序序列为 bdcafge,则前序序列是( ) A. egfacbd B.egfacbd C.eacbdgf D.eagcfbc E.以上答案都不对 C D 4. 给定如图 1 所示的一棵二叉树,写出它的前序、中序、后序遍历。 前序: F E 中序: 后序: 图1 5. 已知,按中序遍历二叉树的结果为:abc,问:有多少种不同形态的二叉树可以得到这一遍历结果? 答: 6. 对于前序遍历与中序遍历结果相同的二叉树为( ) ,对于前序遍历和后序遍历结果相同的二叉树为( A. 一般二叉树 B. 只有根结点的二叉树 C. 根结点无左孩子的二叉树 D. 根结点无右孩子的二叉树 E. 所有结点只有左孩子的二叉树 F. 所有结点只有右子树的二叉树
G

) 。

哈夫曼树及哈夫曼编码

第 1 页 共 2 页

一、几个定义:
树的路径长度:从树根到每一个结点的路径长度之和。图 1 中树的路径长度为__________ 结点的带权路径长度:结点到树根之间的路径长度与该结点上权的乘积。图 1 中权为 2 的结点的带权路径长度为 _____________。 树的带权路径长度:树中所有叶子结点的带权路径长度之和。图 1 中树的带权路径长度为_____________

C. 哈夫曼树是一棵二叉树,因此它的结点的度可以为 0、1 或 2 D. 哈夫曼树是带权外路径长度最短的二叉树 3. 已知某系统在通讯时,只出现 F,T,D,S,H 五种字 H. 给定权值集合:7,19,2,6,32,21,3,10,试画出以 符, 它们出现的频率依次为 5,10,4,2,2, 试设计 Huffman 权值为叶子结点的哈夫曼树,并求出其带权路径长度。 编码。 (权值小的为左子树,权值大的为右子树)

4 3 2 图1

记作:wp l ?

?w
k ?1

n

k

lk

其中: w在权为 —权值 的 n 个叶子所构成德所有二叉树中, Huffman 树—— k — w1,w2,……wn l k — —结点到根的路径长度 带权路径长度最小的二叉树称为最优二叉树或哈夫曼树
4. 下程序为构建哈夫曼树,请补充完整。 (顺序结构,数组存储) program huffmantree; var i:integer; const n=4;m=7; small1,small2:real; type j,k:0..m; node=record begin weight:real;{权重} for i:=1 to m do{初始化} parent,lchild,rchild:0..m; with ht[i] do end; begin htree=array[1..m] of node; weight:=0;lchild:=0;parent:=0;rchild:=0; var htree1:htree; end; i:integer; for i:=1 to n do read(ht[i].weight);{读入权重} procedure gjtree(var ht:htree); for i:=n+1 to m do{构造最优二叉树} function min(h:integer):integer;{在前 h 个 begin 结点中选择父指针为 0 且权值最小的结点 min} j:=min(i-1); var m1:real; ht[j].parent:=______________; temp:integer; ht[i].lchild:=______________; begin k:=min(i-1); m1:=10000; ht[k].parent:=______________; for i:=1 to h do ht[i].rchild:=______________; begin ht[i].weight:=_________________________; if (_______________) end; and (_______________) end; then begin begin temp:=_______________; gjtree(htree1); m1:=________________; for i:=1 to m do end; with(htree1[i]) do end; begin min:=________________; writeln(weight:1:0,',',parent,',',lchild,',',rchild); end; end; end.

二、构造 Huffman 树的方法
1. 2. 根据给定的 n 个权值{w1,w2,……wn},构造 n 棵只有根结点的二叉树,令其权值为 wj,构成森林 F 在森林 F 中选取两棵根结点权值最小值作为左右子树(当这样的树不止两棵树时,可以从中任选两棵) ,构造一棵 新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和 3. 重复②,直到只含一棵树为止,这棵树即哈夫曼树 思考:若初始结点数为 n,那么构建的哈夫曼树有多少结点?________________________ 哈夫曼树的建立 结点的定义: for j:=1 to i-1 do{在 ht[k](1<=k<=i-1)中选择两个其双亲 Type 域为零且权值最小的结点,并记下它们的序号} node=record begin weight:real; if ___________________ then parent,lchild,rchild:0..m; begin end; if ht[j].weight<small1 then htree=array[1..m] of node; begin var htree1:htree; small2:=small1;small1:=_______________; procedure gjtree(var ht:htree); p2:=_______________; p1:=_____________; var i,j:integer; end small1,small2:real; else if ht[j].weight<small2 then p1,p2:0..m; begin begin small2:=_______________; for i:=1 to m do p2:=_______________; with ht[i] do end; begin end; weight:=0;lchild:=0;parent:=0;rchild:=0; end; end; ht[p1].parent:=i; for i:=1 to n do read(ht[i].weight); ht[p2].parent:=i; for i:=n+1 to m do ht[i].lchild:=p1; begin ht[i].rchild:=p2; p1:=0;p2:=0; ht[i].weight:=ht[p1].weight+ht[p2].weight; small1:=1000;small2:=1000; end; G. 下列关于哈夫曼树的叙述,错误的是:( ) end; A. 哈夫曼树根结点的权值等于所有叶结点的权值之和 B. 具有 n 个叶结点的哈夫曼树共有 2n-1 个结点、

第 2 页 共 2 页


更多相关文档:

树与二叉树、哈夫曼树学案

信息学 科学案 序号 高一 年级 班 学生 树与二叉树学案一、树的定义及特点 树(tree)是 n(n>0)个结点的有限集 T。 特点: 树中至少有一个结点——根,树...

二叉树和哈夫曼树实验报告

2.熟练哈夫曼树的定义,掌握构造哈夫曼树的方法、哈夫曼编码译码的方法。 二、实验原理主要内容 1、实验内容: 1.实现二叉树中所有结点的左、右子树相互交换...

树和二叉树习题及答案

树和二叉树习题及答案_工学_高等教育_教育专区。数据结构一、 填空题 1. 不...7. 哈夫曼树 是带权路径最小的二叉树。 8. 前缀编码是指任一个字符的编码...

二叉树和哈夫曼树题目详解之一

二叉树和哈夫曼树题目详解之一_计算机软件及应用_IT/计算机_专业资料。1、 已知...第6章 树和二叉树4-哈夫... 25页 免费 最优二叉树(哈夫曼树) 14页 免费...

第5章+树与二叉树习题解析(答)

A、哈夫曼树是带权路径长度最短得数,路径上权值较大的结点离根较近 B、 若一个二叉树的树叶是某子树中序遍历序列中的第一个结点, 则它必是该子树后序 ...

数据结构详细教案——树与二叉树

数据结构详细教案——树与二叉树_计算机软件及应用_IT/计算机_专业资料。超详细...16 6.8 哈夫曼树及其应用 ......

第5章 树与二叉树习题参考答案

对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行( B )遍历操作相同。...有 m 个叶结点的哈夫曼树中,结点的总数是 2m-1 。 6. 若一棵完全二叉树...

第6章 树和二叉树练习题及答案

(√ )14、具有 n 个结点的满二叉树,其叶结点的个数为(n+1)/2。 (√ )15、前序中序遍历用线索树方式存储的二叉树,不必使用栈。 (╳ )16、哈夫曼树...

第5章 树与二叉树习题参考答案

层次 2.在哈夫曼树中,任何一个结点它的度都是(习题五参考答案一、选择题 1.对一棵树进行后根遍历操作与对这棵树所对应的二叉树进行( B )遍历操作相同。 A...

第5章_树与二叉树习题解析

A、哈夫曼树是带权路径长度最短得数,路径上权值较大的结点离根较近 B、若一个二叉树的树叶是某子树中序遍历序列中的第一个结点,则它必是该子树后 序遍历...
更多相关标签:
二叉树 哈夫曼树编码 | 哈夫曼树 完全二叉树 | 线索二叉树和哈夫曼树 | 哈夫曼树 | 哈夫曼树的构造 | 哈夫曼树编码 | 哈夫曼树带权路径长度 | 哈夫曼树c语言实现 |
网站地图

文档资料共享网 nexoncn.com copyright ©right 2010-2020。
文档资料共享网内容来自网络,如有侵犯请联系客服。email:zhit325@126.com