}
}//Get_Sub_Depth
int Get_Depth(Bitree T)//求子树深度的递归算法 {
if(!T) return 0; else {
m=Get_Depth(T->lchild); n=Get_Depth(T->rchild); return (m>n?m:n)+1; }
}//Get_Depth
附：上机调试过程
步骤1 键盘输入序列12，8，17，11，16，2，13，9，21，4，构成一棵二叉排序树。层数应当为4
12 8 17 2 11 16 21 4 9 13
步骤2： 执行求深度的函数，并打印统计出来的深度值。 完整程序如下： #include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root;
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(x
if(x
int depth(liuyu*root) /*统计层数*/
{int d,p; /*注意每一层的局部变量d,p都是各自独立的*/ p=0;
if(root==NULL)return(p); /*找到叶子之后才开始统计*/ else{
16
d=depth(root->lchild);
if(d>p) p=d; /*向上回朔时，要挑出左右子树中的相对大的那个深度值*/ d=depth(root->rchild); if(d>p)p=d; }
p=p+1; return(p); }
void main() /*先生成二叉排序树，再调用深度遍历递归函数进行统计并输出*/ {int i,x; i=1;
root=NULL; /*千万别忘了赋初值给root!*/ do{printf(\i++;
scanf(\ /*从键盘采集数据，以-9999表示输入结束*/ if(x==-9999){
printf(\ else insert_data(x);} /*调用插入数据元素的函数*/ while(x!=-9999); return;} 执行结果：
3. 【严题集6.47④】编写按层次顺序（同一层自左至右）遍历二叉树的算法。 或：按层次输出二叉树中所有结点；
解：思路：既然要求从上到下，从左到右，则利用队列存放各子树结点的指针是个好办法。 这是一个循环算法，用while语句不断循环，直到队空之后自然退出该函数。
技巧之处：当根结点入队后，会自然使得左、右孩子结点入队，而左孩子出队时又会立即使得它的左右孩子结点入队，??以此产生了按层次输出的效果。 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;} /*若右子树不空，则右子树进队*/ }
17
return(0); }
法二：
void LayerOrder(Bitree T)//层序遍历二叉树 {
InitQueue(Q); //建立工作队列
EnQueue(Q,T);
while(!QueueEmpty(Q)) {
DeQueue(Q,p); visit(p);
if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }
}//LayerOrder
可以用前面的函数建树，然后调用这个函数来输出。
完整程序如下（已上机通过） #include
typedef struct liuyu{int data;struct liuyu *lchild,*rchild;}test; liuyu *root,*p,*q[max];
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(x
if(x
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]; /*出队*/
18
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(\ 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相比,作了一个修改,不管当前结点 是否有左右孩子,都入队列.这样当树为完全二叉树时,遍历时得到是一个连续的不包含空 指针的序列.反之,则序列中会含有空指针.
19
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 （17） （11） 0 1 7 10 6 （5） 0 1 0 1 2 3 7 10 6 0 1
2 3
方案比较：
字母编号 对应编码 出现频率 字母编号 对应编码 出现频率 1100 0.07 1 000 0.07 1 00 0.19 2 001 0.19 2 11110 0.02 3 010 0.02 3 1110 0.06 4 011 0.06 4 5 10 0.32 5 100 0.32 6 11111 0.03 6 101 0.03 7 01 0.21 7 110 0.21 方案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 8 1的WPL＝1101 0.10 8 111 0.10 方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3 结论：哈夫曼编码优于等长二进制编码
第7章 图 自测卷解答
一、单选题（每题1分，共16分） 前两大题全部来自于全国自考参考书！ （ C ）1. 在一个图中，所有顶点的度数之和等于图的边数的 倍。
A．1/2 B. 1 C. 2 D. 4 （ B ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。 A．1/2 B. 1 C. 2 D. 4 （ B ）3. 有8个结点的无向图最多有 条边。
A．14 B. 28 C. 56 D. 112 （ C ）4. 有8个结点的无向连通图最少有 条边。
A．5 B. 6 C. 7 D. 8 （ C ）5. 有8个结点的有向完全图有 条边。
A．14 B. 28 C. 56 D. 112 （ B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 （ A ）7. 用邻接表表示图进行深度优先遍历时，通常是采用 来实现算法的。
A．栈 B. 队列 C. 树 D. 图 （ C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是
?0?1??1??1?1??0??1111101?001001??000100??100110?011010??001101?100010??A．0 2 4 3 1 5 6
B. 0 1 3 6 5 4 2 C. 0 4 2 3 1 6 5 20 D. 0 3 6 1 5 4 2
建议：0 1 3 4 2 5 6
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库数据结构期末复习章节试题（附答案） - 图文(4)在线全文阅读。
相关推荐：