各字母的编码为： A:0001 B:10 C:0000 E:0111 F:001 G:11
D:0110 H:010
【练习】假设二叉树采用如下顺序存储结构：
（1）试画出二叉树； （2）写出先序遍历、中序遍历和后序遍历的结果。
修补后的二叉树
二叉树Leabharlann 先序遍历：ABDGEHCFI 中序遍历：GDBEHAFIC 后序遍历：GDHEBIFCA
先序遍历序列为：abcedfhgij 中序遍历序列为：ecbhfdjiga 后序遍历序列为：echfjigdba
7.2 已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa， 试给出该二叉树树形表示。
7.3 设给定权集w={2,3,4,7,8,9}，试构造关于w的一棵哈夫曼树，并
求取加权路径长度WPL。
加权路径长度WPL=(9+7+8)×2+4×3+(2+3)×4=80
7.5 设计一个算法，将一棵以二叉链方式存储的二叉树t按顺序方
式存储到数组A中。
Void ctree(BTNode *t,char A[],int i) { if(t!=null) //t=null不做任何事，为出口 { A[i-1]=t->data; ctree(t->lchild,A,2*i); ctree(t->rchild,A,2*i+1); } } /*调用从ctree(t,A,1)开始*/
【补充作业2】假定用于通信的电文由8个字母组成，各字母在电文 中出现的频率如下表。试为这8个字母设计其所对应的哈夫曼编码 （要求按照每个结点的左子树根结点的权值小于或等于右子树根结 点的权值的次序构造）。
字母 频率 A 6% B 27% C 3% D 7% E 8% F 9% G 29% H 11%
第七章 作业参考解答
7.1 设二叉树bt的存储结构如下：
lchild 1 0 j 0 2 0 h 0 3 2 f 0 4 3 d 9 5 7 b 4 6 5 a 0 7 8 c 0 8 0 e 0 9 10 g 0 10 1 i 0
data
rchild
（2）写出先序、中序和后序遍历二叉树bt所得到的结点序列。
补充作业1：试确定分别满足下面条件的所有二叉树。
（1）中根遍历序列和后根遍历序列相同。 （2）前根、中根、后根遍历序列均相同。 解：中根顺序为左根右，后根遍历顺序为左右根，则只 有右子树为空或左右子树均为空时相同，即该二叉树的 任何结点至多只有左子树。 （2）前根遍历顺序为根左右，中根遍历序列为左根右， 后根遍历顺序为左右根，则只有左右子树均为空时相同， 即该二叉树只含一个根结点。