方案比较： 字 母编号 1 2 3 4 5 6 方案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 结论：哈夫曼编码优于等长二进制编码

（4）已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

答案： 初态:

1 2 3 4 5 6 7 8 9 10 11 12 13 weight 3 12 7 4 2 8 11 parent 0 0 0 0 0 0 0 0 0 0 0 0 0 lchild 0 0 0 0 0 0 0 0 0 0 0 0 0 rchild 0 0 0 0 0 0 0 0 0 0 0 0 0

7 8 对应编码 1100 00 11110 1110 10 11111 01 1101 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 字母编号 1 2 3 4 5 6 7 8 对应编码 000 001 010 011 100 101 110 111 出现频率 0.07 0.19 0.02 0.06 0.32 0.03 0.21 0.10 XXXVII

终态：

1 2 3 4 5 6 7 8 9 10 11 12 13

3．算法设计题

以二叉链表作为二叉树的存储结构，编写以下算法： （1）统计二叉树的叶结点个数。

[题目分析]如果二叉树为空，返回0，如果二叉树不为空且左右子树为空，返回1，如果二叉树不为空，且左右子树不同时为空，返回左子树中叶子节点个数加上右子树中叶子节点个数。 [算法描述]

int LeafNodeCount(BiTree T) { }

（2）判别两棵树是否相等。

if(T==NULL)

return 0; //如果是空树，则叶子结点个数为0

return 1; //判断结点是否是叶子结点（左孩子右孩子都为空），若是则返回1 return LeafNodeCount(T->lchild)+LeafNodeCount(T->rchild); else if(T->lchild==NULL&&T->rchild==NULL) else

weight 3 12 7 4 2 8 11 5 9 15 20 27 47 parent 8 12 10 9 8 10 11 9 11 12 13 13 0 lchild 0 0 0 0 0 0 0 5 4 3 9 2 11 rchild 0 0 0 0 0 0 0 1 8 6 7 10 12

XXXVIII

[题目分析]先判断当前节点是否相等(需要处理为空、是否都为空、是否相等)，如果当前节点不相等，直接返回两棵树不相等;如果当前节点相等，那么就递归的判断他们的左右孩子是否相等。 [算法描述]

int compareTree(TreeNode* tree1, TreeNode* tree2)

//用分治的方法做，比较当前根，然后比较左子树和右子树 {bool tree1IsNull = (tree1==NULL); bool tree2IsNull = (tree2==NULL); if(tree1IsNull != tree2IsNull) { return 1; }

if(tree1IsNull && tree2IsNull) {//如果两个都是NULL，则相等 return 0;

}//如果根节点不相等，直接返回不相等，否则的话，看看他们孩子相等不相等 if(tree1->c != tree2->c) { return 1; }

return (compareTree(tree1->left,tree2->left)&compareTree(tree1->right,tree2->right))

(compareTree(tree1->left,tree2->right)&compareTree(tree1->right,tree2->left)); }//算法结束

（3）交换二叉树每个结点的左孩子和右孩子。

[题目分析]如果某结点左右子树为空，返回，否则交换该结点左右孩子，然后递归交换左右子树。

[算法描述]

void ChangeLR(BiTree &T) {

BiTree temp;

if(T->lchild==NULL&&T->rchild==NULL) else {

temp = T->lchild; T->lchild = T->rchild; T->rchild = temp;

XXXIX

return;

}

}//交换左右孩子

ChangeLR(T->lchild); //递归交换左子树 ChangeLR(T->rchild); //递归交换右子树

（4）设计二叉树的双序遍历算法（双序遍历是指对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树）。

[题目分析]若树为空，返回；若某结点为叶子结点，则仅输出该结点；否则先输出该结点，递归遍历其左子树，再输出该结点，递归遍历其右子树。

[算法描述]

void DoubleTraverse(BiTree T) { }

（5）计算二叉树最大的宽度（二叉树的最大宽度是指二叉树所有层中结点个数的最大值）。

[题目分析] 求二叉树高度的算法见上题。求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。

[算法描述]

int Width(BiTree bt)//求二叉树bt的最大宽度 {if (bt==null) return (0); //空二叉树宽度为0 else

{BiTree Q[];//Q是队列，元素为二叉树结点指针，容量足够大 front=1;rear=1;last=1;

//front队头指针,rear队尾指针,last同层最右结点在队列中的位置 temp=0; maxw=0; //temp记局部宽度, maxw记最大宽度 Q[rear]=bt; //根结点入队列 while(front<=last)

XL

if(T == NULL) { }

cout<data;

DoubleTraverse(T->lchild); //递归遍历左子树 cout<data;

DoubleTraverse(T->rchild); //递归遍历右子树 return;

cout<data; //叶子结点输出 else if(T->lchild==NULL&&T->rchild==NULL) else