1、假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树。
21、有一个完全二叉树按层次顺序存放在一维数组中，如下所示：
请指出结点P的父结点，左子女，右子女。
3、给出下列二叉树的先序序列。
4、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，画出二叉树。
答案：二叉树形态                     
     
（2）设一棵二叉树的先序序列： A B D F C E G H ，中序序列： B F D A G E H C
画出这棵二叉树。
画出这棵二叉树的后序线索树。
将这棵二叉树转换成对应的树（或森林）。
 
 
 
 
 
 
 
 
        (1)                          (2)
1、已知一棵二叉树的前序序列为：A,B,D,G,J,E,H,C,F,I,K,L中序序列：D,J,G,B,E,H, A,C,K,I,L,F。
i.写出该二叉树的后序序列；
ii.画出该二叉树；
iii.求该二叉树的高度(假定空树的高度为－1)和度为2、度为1、及度为0的结点个数。
该二叉树的后序序列为：J,G,D,H,E,B,K,L,I,F,C,A。
该二叉树的形式如图所示：
该二叉树高度为：5。
度为2的结点的个数为：3。
度为1的结点的个数为：5。
度为0的结点个数为：4。
5、试用权集合{12,4,5,6,1,2}构造哈夫曼树，并计算哈夫曼树的带权路径长度。
答案：
WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69
6、已知权值集合为{5,7,2,3,6,9}，要求给出哈夫曼树，并计算带权路径长度WPL。
答案：(1)树形态：             
(2)带权路径长度：WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79
（3） 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。
试为这8个字母设计赫夫曼编码。
试设计另一种由二进制表示的等长编码方案。
对于上述实例，比较两种方案的优缺点。
解：方案1；哈夫曼编码
先将概率放大100倍，以方便构造哈夫曼树。
w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32
（100）
（40）      （60）
19    21    32  （28）
（17）（11）
  7    10  6    （5）
                2    3
方案比较：
方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61
方案2的WPL＝先序中序后序遍历二叉树3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。