习题5参考答案5.1 选择（1）C（2）B（3）C（4）B（5）C（6）D（7）C（8）C（9）B（10）C （11）B（12）C（13）C（14）C（15）C（16）B5.2 填空（1）1（2）1036；1040（3）2i（4） 1 ； n ; n-1 ; 2（5）2k-1；2k-1（6）ACDBGJKIHFE（7）p->lchild==NULLL（8）Huffman树（9）其第一个孩子; 下一个兄弟（10）先序遍历；中序遍历5.3叶子结点:C、F、G、L、I、M、K；非终端结点：A、B、D、E、J；各结点的度：结点： A B C D E F G L I J K M度： 4 3 0 1 2 0 0 0 0 1 0 0树深：45.4无序树形态如下：二叉树形态如下：5.5二叉链表如下:三叉链表如下:5.6先序遍历序列:ABDEHICFJG中序遍历序列:DBHEIAFJCG后序遍历序列:DHIEBJFGCA5.7(1) 先序序列和中序序列相同：空树或缺左子树的单支树；(2) 后序序列和中序序列相同：空树或缺右子树的单支树；(3) 先序序列和后序序列相同：空树或只有根结点的二叉树。
5.8这棵二叉树为:5.9先根遍历序列:ABFGLCDIEJMK后根遍历序列:FGLBCIDMJKEA层次遍历序列:ABCDEFGLIJKM5.10证明：设树中结点总数为n，叶子结点数为n0，则n=n0 + n1 + …… + n m （1）再设树中分支数目为B，则B=n1 + 2n2 + 3n3+ …… + m n m （2）因为除根结点外，每个结点均对应一个进入它的分支，所以有n= B + 1 （3）将（1）和（2）代入（3），得n0 + n1 + …… + n m = n1 + 2n2 + 3n3+ …… + m n m + 1从而可得叶子结点数为：n0 = n2 + 2n3+ …… + (m-1)n m + 15.11由5.10结论得，n0 = (k-1)n k + 1又由 n=n0 + n k，得n k= n-n0，代入上式，得n0 = (k-1)（n-n0）+ 1叶子结点数为：n0 = n (k-1) / k5.12int NodeCount(BiTree T){ //计算结点总数if(T)if (T-> lchild==NULL )&&( T --> rchild==NULL )return 1;elsereturn NodeCount(T-> lchild ) +Node ( T --> rchild )+1;elsereturn 0;}5.13void ExchangeLR(Bitree bt){/* 将bt所指二叉树中所有结点的左、右子树相互交换 */if (bt && (bt->lchild || bt->rchild)) {bt->lchild<->bt->rchild;Exchange-lr(bt->lchild);Exchange-lr(bt->rchild);}}/* ExchangeLR */5.14int IsFullBitree(Bitree T){/* 是则返回1，否则返回0。
*/Init_Queue(Q); /* 初始化队列*/flag=0;In_Queue(Q，T); /* 根指针入队列，按层次遍历*/while(!Empty_Queue (Q)){Out_Queue(Q,p);if(!p) flag=1; /* 若本次出队列的是空指针时，则修改flag值为1。
若以后出队列的指针存在非空，则可断定不是完全二叉树 */else if (flag) return 0; /*断定不是完全二叉树 */else{In_Queue(Q，p->lchild);In_Queue(Q，p->rchild); /* 不管孩子是否为空，都入队列。
*/}}/* while */return 1; /* 只有从某个孩子指针开始，之后所有孩子指针都为空，才可断定为完全二叉树*/}/* IsFullBitree */5.15转换的二叉树为：5.16对应的森林分别为：5.17typedef char elemtype; typedef struct{ elemtype data;int parent;} NodeType;(1) 求树中结点双亲的算法:int Parent(NodeType t[ ], elemtype x){/* x不存在时返回-2,否则返回x双亲的下标(根的双亲为-1 */ for(i=0;i<MAXNODE;i++)if(x==t[i].data) return t[i].parent;return -2;}/*Parent*/(2) 求树中结点孩子的算法:void Children(NodeType t[ ], elemtype x){for(i=0;i<MAXNODE;i++){if(x==t[i].data)break;/*找到x,退出循环*/}/*for*/if(i>=MAXNODE) printf(“x不存在\n”);else {flag=0;for(j=0;j<MAXNODE;j++)if(i==t[j].parent){ printf(“x的孩子:%c\n”,t[j].data);flag=1;}if(flag==0) printf(“x无孩子\n”);}}/*Children*/5.18typedef char elemtype;typedef struct ChildNode{ int childcode;struct ChildNode *nextchild;}typedef struct{ elemtype data;struct ChildNode *firstchild;} NodeType;(1) 求树中结点双亲的算法:int ParentCL(NodeType t[ ], elemtype x){/* x不存在时返回-2, 否则返回x双亲的下标 */for(i=0;i<MAXNODE;i++)if(x==t[i].data) {loc=i;/*记下x的下标*/break;}if(i>=MAXNODE) return -2; /* x不存在 *//*搜索x的双亲*/for(i=0;i<MAXNODE;i++)for(p=t[i].firstchild;p!=NULL;p=p->nextchild)if(loc==p->childcode)return i; /*返回x结点的双亲下标*/}/* ParentL */(2) 求树中结点孩子的算法:void ChildrenCL(NodeType t[ ], elemtype x){for(i=0;i<MAXNODE;i++)if(x==t[i].data) /*依次打印x的孩子*/{flag=0; /* x存在 */for(p=t[i].firstchild;p;p=p->nextchild){ printf(“x的孩子:%c\n”,t[p-> childcode].data);flag=1;}if(flag==0) printf(“x无孩子\n”);return;}/*if*/printf(“x不存在\n”);return;}/* ChildrenL */5.19typedef char elemtype;typedef struct TreeNode{ elemtype data;struct TreeNode *firstchild;struct TreeNode *nextsibling;} NodeType;void ChildrenCSL(NodeType *t, elemtype x){ /* 层次遍历方法 */ Init_Queue(Q); /* 初始化队列 */In_Queue(Q,t);count=0;while(!Empty_Queue (Q)){Out_Queue(Q,p);if(p->data==x){ /*输出x的孩子*/p=p->firstchild;if(!p) printf(“无孩子\n”);else{ printf(“x的第%i个孩子:%c\n”,++count, p->data);/*输出第一个孩子*/p=p->nextsibling; /*沿右分支*/while(p){printf(“x的第%i个孩子:%c\n”, ++count, p->data);p=p-> nextsibling;}}return;}if(p-> firstchild) In_Queue(Q,p-> firstchild);if(p-> nextsibling) In_Queue(Q,p-> nextsibling);}}/* ChildrenCSL */5.20(1) 哈夫曼树为:(2) 在上述哈夫曼树的每个左分支上标以1，右分支上标以0，并设这7个字母分别为A、B、C、D、E、F和H，如下图所示：则它们的哈夫曼树为分别为: A：1100B：1101C：10D：011E：00F：010H：111。