数据结构 第6章习题答案

int sum=0;int m=sizeof(test);

void insert_data(int x) /*如何生成二叉排序树？参见教材P43C程序*/ { liuyu *p,*q,*s; s=(test*)malloc(m); s->data=x;

s->lchild=NULL; s->rchild=NULL;

if(!root){root=s; return;} p=root;

while(p) /*如何接入二叉排序树的适当位置*/ {q=p;

if(p->data==x){printf(\else if(xdata)p=p->lchild; else p=p->rchild; }

if(xdata)q->lchild=s; else q->rchild=s; }

level(liuyu*T)

/* liuyu *T,*p,*q[100]; 假设max已知*/ {int f,r;

f=0; r=0; /*置空队*/ r=(r+1)%max;

q[r]=T; /*根结点进队*/ while(f!=r) /*队列不空*/ {f=(f+1%max);

p=q[f]; /*出队*/

printf(\ /*打印根结点*/

if(p->lchild){r=(r+1)%max; q[r]=p->lchild;} /*若左子树不空，则左子树进队*/ if(p->rchild){r=(r+1)%max; q[r]=p->rchild;} /*若右子树不空，则右子树进队*/ }

return(0); }

void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/ {int i,x; i=1;

root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;

scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){

printf(\

11

else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;}

4. 已知一棵具有n个结点的完全二叉树被顺序存储于一维数组A中，试编写一个算法打印出编号为i的结点的双亲和所有的孩子。

答：首先，由于是完全二叉树，不必担心中途会出现孩子为null的情况。 其次分析：结点i的左孩子为2i，右孩子为2i+1;直接打印即可。

Printf(“Left_child=”, %d, v[2*i].data; “Right_child=”, %d, v[2*i+1].data;);

但其双亲是i/2，需先判断i为奇数还是偶数。若i为奇数，则应当先i-- ，然后再除以2。 If(i/2!=0)i--;

Printf(“Parents=”, %d, v[i/2].data;);

5.【严题集6.49④】编写算法判别给定二叉树是否为完全二叉树。

答：int IsFull_Bitree(Bitree T)//判断二叉树是否完全二叉树,是则返回1,否则返回0 {

InitQueue(Q); flag=0;

EnQueue(Q,T); //建立工作队列 while(!QueueEmpty(Q)) { {

DeQueue(Q,p); if(!p) flag=1;

else if(flag) return 0; else {

EnQueue(Q,p->lchild);

EnQueue(Q,p->rchild); //不管孩子是否为空,都入队列 } }//while return 1; }//IsFull_Bitree

分析:该问题可以通过层序遍历的方法来解决.与6.47相比,作了一个修改,不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针.

6. 【严题集6.26③】假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，

0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计哈夫曼编码。使用0～7的二进制表示形式是另一种编码方案。对于上述实例，比较两种方案的优缺点。 解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ……19, 21, 32

（100）

0 1 （40） （60）

0 1 0 1 19 21 32 （28）

19 21 32 12

0 1 0 1 0 1 7 10 6 0 1 2 3 （17） （11） 7 10 6 （5） 2 3

方案比较：

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

字母编号 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 13