数据结构 用C语言描述 课后答案(9)

哈夫曼编码为：

I1：11111 I5：1100 I2：11110 I6： 10

I3：1110 I7： 01 I4：1101 I8： 00

8、八皇后问题 【解答】略

课后练习

一、假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。

二、已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？ 【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1

所以n2= n0 –1=49，当二叉树中没有度为1的结点时，总结点数n=n0+n2=99 三、给出满足下列条件的所有二叉树：

① 前序和后序相同 ② 中序和后序相同 ③ 前序和后序相同 【解答】 (1) 前序与中序相同：空树或缺左子树的单支树； (2) 中序与后序相同：空树或缺右子树的单支树；

(3) 前序与后序相同：空树或只有根结点的二叉树。

四、n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个？

五、画出与下列已知序列对应的树Ｔ：

树的先根次序访问序列为GFKDAIEBCHJ； 树的后根次序访问序列为DIAEKFCJHBG。 六、

七、已知二叉树采用二叉链表存放,要求返回二叉树T的后序序列中的第一个结点指针,是否可不用递归且不用栈来完成?请简述原因. 八、画出和下列树对应的二叉树：

【解答】

九、已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 十、编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。

十一、分别写函数完成：在先序线索二叉树T中，查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。 【解答】

(1) 找结点的先序后继结点

BiTNode *PreSucc (BiTNode *p)

/*在先序线索二叉树中查找p的先序后继结点，并用succ指针返回结果*/ { if (p->Ltag= =0) succ = p->LChild; else succ= p->RChild; return (succ); }

(2) 找结点的后序前驱结点

BiTNode *SuccPre (BiTNode *p)

/*在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; else pre= p->RChild; return (pre);

}

十二、分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。 【解答】

（1）找结点的中序前驱结点

BiTNode *InPre (BiTNode *p)

/*在中序线索二叉树中查找p的中序前驱结点，并用pre指针返回结果*/ { if (p->Ltag= =1) pre = p->LChild; /*直接利用线索*/ else

{/*在p的左子树中查找“最右下端”结点*/

for ( q=p->LChild; q->Rtag= =0; q=q->RChild); pre = q; }

return (pre); }

（2）找结点的中序后继结点

BiTNode *InSucc (BiTNode *p)

/*在中序线索二叉树中查找p的中序后继结点，并用succ指针返回结果*/ { if (p->Rtag= =1) succ = p->RChild; /*直接利用线索*/ else

{/*在p的右子树中查找“最左下端”结点*/

for ( q=p->RChild; q->Ltag= =0; q=q->LChild); succ= q;

}

return (succ); }

十三、编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。 十四、对以孩子-兄弟链表表示的树编写计算树的深度的算法。 十五、已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法。 十六、设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点。

十七、计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。

十八、已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。 【解答】

Void PreOrder(BiTree root) /*先序遍历二叉树的非递归算法*/ {

InitStack(&S); p=root;

while(p!=NULL || !IsEmpty(S) ) { if(p!=NULL) {

Visit(p->data); push(&S,p); p=p->Lchild;

}

else {

Pop(&S,&p); p=p->RChild; } } }

十九、证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树； 给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树； 二十、二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。 二十一、二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。 【解答】 算法(一) Void exchange ( BiTree root )

{

p=root;

}

算法(二) Void exchange ( BiTree root )

{

p=root; if ( p->LChild != NULL || p->RChild != NULL )

{

exchange ( p->LChild ); exchange ( p->RChild ); temp = p->LChild;

p->LChild = p->RChild;

p->RChild = temp; } }

if ( p->LChild != NULL || p->RChild != NULL )

{ temp = p->LChild;

p->LChild = p->RChild; p->RChild = temp; exchange ( p->LChild ); exchange ( p->RChild ); }