发布时间 : 星期一 文章数据结构（C语言版）习题解答更新完毕开始阅读
A B C D E F H 森林对应的二叉树：
I K J M L N O 图6-2
G
A B C D L E F H G M N O J K I 6.11已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。
A B C D G E I H F J K
6.14 假设某个电文由(a,b,c,d,e,f,g,h)8个字母组成，每个字母在电文中出现的次数分别为(7,19,2,6,32,3,21,10)，试解答下列问题： (1) 画出出huffman树；
1000 60 28 11 G40 19b 21g 5 2c 3f 17 6d 7a 10h 32e
(2) 写出每个字母的huffman编码；
a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011 (3) 在对该电文进行最优二进制编码处理后，电文的二进制位数。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=261 6.17 写出按层次遍历二叉树的算法。 思路：用队列存储结构，并用递归方法
Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)//层序遍历二叉树 {
InitQueue(Q); //初始化队列
if(!T) return Error;//空树，直接返回 EnQueue(Q,T);//根结点入队 BiTNode *p;
while(!QueueEmpty(Q)) {
DeQueue(Q,p); Visit(p->data);
if(p->lchild) EnQueue(Q,p->lchild); if(p->rchild) EnQueue(Q,p->rchild); }//while return Ok;
}//LevelOrderTraverse
6.19 写出判断两棵给定二叉树是否相似的算法。
(注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。) 思路：采用递归进行比较判断
bool BiTreeSimilar (BiTree T1,BiTree T2) {
if(T1==Null&&T2==Null) return 1;
else if(T1==Null || T2==Null) return 0; else
return (BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild)); }
6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。
思路：在孩子兄弟链表中，若结点的firstchild为Null，则为叶子结点；采用递归方法。 int CountLeaves(Tree T，int &num)//num传递的初值为0
{
if(T->nextsibling!=Null)
num+=CountLeaves (T->nextsibling); if(T->firstchild!=Null)
num+=CountLeaves(T-> firstchild); else
num+=1;//firstchild域为空，则为叶子结点 return num; }
V1 V5 V6 第七章 图
7.1 已知有向图如图7-1所示， 请给出该图的
V3 图7-1
V2 V4 (1)邻接矩阵示意图 (2)邻接表示意图 (3)逆邻接表 (4)所有强连通分量 (1) 邻接矩阵 （2）邻接表
（3）逆邻接表
553153421<0v11v22v3345
< 1 2 3 4 5 6 7 8 9 10 1 0 0 0 0 0 1 0 1 0 1 < V1 V5 7.2 已知图G的邻接矩阵如图7-2所示。写出该图从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。 V6 2 0 0 0 0 0 1 0 0 0 0 3 0 1 0 0 0 0 1 0 0 0 4 0 0 1 0 0 0 0 1 0 0 5 0 0 0 1 0 0 0 0 1 0 6 0 0 0 0 1 0 0 0 0 1 7 1 8 0 9 1 0 0 1 10 0 0 0 0 1 V2 0 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0 V4 V3 1 0 0 0 1 0 0 0 1 0 1 0 图7-2 深度优先序列：1 7 3 4 5 6 2 10 9 8