发布时间 : 星期一 文章中南大学数据结构与算法第6章树和二叉树课后作业答案更新完毕开始阅读38193a1dfe4733687e21aa5c
答：
第二组不是前缀码。因为0，1分别是00和11的前缀。(前缀码是指该编码集中的任一编码不是其他编码的前缀)
6.21 假设用于通信的电文由字符集{a,b,c,d,e,f,g,h}中的字母构成，这8个字母在电文中出现的概率分别为{0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10}.
(1)为这8个字母设计哈夫曼编码。
(2)若用这三位二进制数(0…7)对这8个字母进行等长编码，则哈夫曼编码的平均码长是等长编码的百分之几?它使电文总长平均压缩多少? 解：
(1)哈夫曼编码
根据上图可得编码表： a:1001 b:01 c:10111 d:1010 e:11
f:10110 g:00 h:1000
(2)用三位二进行数进行的等长编码平均长度为3，而根据哈夫曼树编码的平均码长为： 4*0.07+2*0.19+5*0.02+4*0.06+2*0.32+5*0.03+2*0.21+4*0.10=2.61 2.61/3=0.87=87%
其平均码长是等长码的87%。 所以平均压缩率为13%。
6.22 二叉树的遍历算法可写为通用形式。例如通用的中序遍历为： void Inorder(BinTree,T,void(* visit)(DataType x)){ if (T){
Inorder(T->lchild,Visit);//遍历左子树
Visit(T->data);//通过函数指针调用它所指的函数来访问结点 Inorder(T->rchild,Visit);//遍历右子树 } }
其中Visit是一个函数指针，它指向形如void f(DataType x)的函数。因此我们可以将访问结点的操作写在函数f中通过调用语句Inorder(root,f)将f的地址传递给Visit,来执行遍历操作。请写一个打印结点数据的函数，通过调用上述算法来完成书中6.3节的中序遍历。 解：
函数如下：
void PrintNode(BinTree T) {
printf(\ }
//定义二叉树链式存储结构
typedef char DataType;//定义DataType类型 typedef struct node{ DataType data;
struct node *lchild, *rchild;//左右孩子子树 }BinTNode; //结点类型
typedef BinTNode *BinTree ;//二叉树类型
void Inorder(BinTree T,void(* Visit)(DataType x)) { if(T) {
Inorder(T->lchild,Visit);//遍历左子树
Visit(T->data); //通过函数指针调用它所指的函数访问结点 Inorder(T->rchild,Visit);//遍历右子树 } }
6.23 以二叉链表为存储结构，分别写出求二叉树结点总数及叶子总数的算法。 解：
(1)求结点数的递归定义为： 若为空树，结点数为0 若只有根结点，则结点数为1；
否则，结点数为根结点的左子树结点数+右子树结点数+1
(2)求叶子数的递归定义为： 若为空树，叶子数为0 若只有根结点，则叶子数为1；
否则，叶子数为根结点的左子树叶子数+右子树叶子数
typedef char DataType;//定义DataType类型 typedef struct node{ DataType data;
struct node *lchild, *rchild;//左右孩子子树 }BinTNode; //结点类型
typedef BinTNode *BinTree ;//二叉树类型
int Node(BinTree T) {//算结点数 if(T)
if (T->lchild==NULL)&&(T->rchild==NULL) return 1;
else return Node(T->lchild)+Node(T->rchild)+1; else return 0; }
int Leaf(BinTree T) { //算叶子数 if(T)
if (T->lchild==NULL)&&(T->rchild==NULL) return 1;
else return Leaf(T->lchild)+Node(T->rchild); else return 0; }
6.24以二叉链表为存储结构，分别写出求二叉树高度及宽度的算法，所谓宽度是指二叉树的各层上，具有结点数最多的那一层上的结点总数。 解：
(1)根据递归定义：二叉树的高度为：