数据结构课后习题及解析第六章.doc

第六章习题
1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树,分别写出前序、中序和后序遍历的序列。
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点,……，nk个度为k的结点，则该树中有多少个叶子结点并证明之.
4。假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
5．已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
6．给出满足下列条件的所有二叉树:
①     前序和后序相同
②     中序和后序相同
③     前序和后序相同
7． n个结点的K叉树,若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个?
8．画出与下列已知序列对应的树Ｔ：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG.
9．假设用于通讯的电文仅由8个字母组成,字母在电文中出现的频率分别为：
0.07,0。19，0。02，0.06，0.32，0.03，0。21，0.10
请为这8个字母设计哈夫曼编码.
10．已知二叉树采用二叉链表存放，要求返回二叉树T的后序序列中的第一个结点指针，是否可不用递归且不用栈来完成？请简述原因.
11。 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储,编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
14．分别写函数完成：在先序线索二叉树T中,查找给定结点*p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱。
15．分别写出算法，实现在中序线索二叉树中查找给定结点*p在中序序列中的前驱与后继。
16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数。
17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储,利用栈的基本操作写出后序遍历非递归的算法。
19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树。正则二叉树是指：在二叉树中不存在子树个数为1的结点.
20．计算二叉树最大宽度的算法。二叉树的最大宽度是指：二叉树所有层中结点个数的最大值。
21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法.
22. 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树;
　　　　　给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23. 二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目.
24。 二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换。

实习题
1。         ［问题描述］ 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序），打印输出遍历结果。
［基本要求］ 从键盘接受输入先序序列，以二叉链表作为存储结构，建立二叉树（以先序来建立）并对其进行遍历（先序、中序、后序)，然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。
[测试数据] ABCффDEфGффFффф(其中ф表示空格字符)
          输出结果为： 先序:ABCDEGF
                       中序:CBEGDFA
                       后序:CGBFDBA
2．已知二叉树按照二叉链表方式存储,编写算法，要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）。
3．如题1要求建立好二叉树,按凹入表形式打印二叉树结构，如下图所示.

2.         按凹入表形式打印树形结构,如下图所示。 

第六章答案

6． 1分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
【解答】
具有3个结点的树          具有3个结点的二叉树      

6。3已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……,nk个度为k的结点，则该树中有多少个叶子结点？
【解答】设树中结点总数为n,则n=n0 + n1 + …… + nk
树中分支数目为B，则B=n1 + 2n2 + 3n3 + …… + knk
因为除根结点外,每个结点均对应一个进入它的分支，所以有n= B + 1
即n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1
由上式可得叶子结点数为:n0 = n2 + 2n3 + …… + (k-1)nk + 1
6.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？
【解答】n0表示叶子结点数，n2表示度为2的结点数，则n0 = n2+1
    所以n2= n0 –1=49，当二叉树中没有度为1的结点时,总结点数n=n0+n2=99 
6。6 试分别找出满足以下条件的所有二叉树:
（1) 前序序列与中序序列相同;
(2） 中序序列与后序序列相同;
(3) 前序序列与后序序列相同。
【解答】
       （1) 前序与中序相同：空树或缺左子树的单支树；
       (2) 中序与后序相同:空树或缺右子树的单支树；
       (3) 前序与后序相同：空树或只有根结点的二叉树。

6。9  假设通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为:
0。07，0.19，0.02，0。06，0。32，0.03，0。21，0.10
请为这8个字母设计哈夫曼编码.
【解答】
     构造哈夫曼树如下：

哈夫曼编码为：
I1：11111                 I5：1100
    I2：11110                 I6： 10
I3：1110          I7： 01 
I4：1101          I8： 00

6.11画出如下图所示树对应的二叉树。

【解答】

6。15分别写出算法，实现在中序线索二叉树T中查找给定结点＊p在中序序列中的前驱与后继。在先序线索二叉树T中,查找给定结点＊p在先序序列中的后继。在后序线索二叉树T中,查找给定结点*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);  
}
(3) 找结点的先序后继结点
BiTNode  ＊PreSucc (BiTNode  ＊p)
/＊在先序线索二叉树中查找p的先序后继结点,并用succ指针返回结果＊/
{ if （p-〉Ltag= =0)  succ = p—>LChild；  
 else   succ= p-〉RChild；
 return (succ）；  
｝
（4） 找结点的后序前驱结点
BiTNode  ＊SuccPre （BiTNode  *p）
/＊在后序线索二叉树中查找p的后序前驱结点，并用pre指针返回结果*/
{ if (p—>Ltag= =1）  pre = p—>LChild;  
 else   pre= p—〉RChild；
 return （pre)；   
}
6.21已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法.
【解答】
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；
}
}
}
6.24已知二叉树按照二叉链表方式存储，编写算法，将二叉树左右子树进行交换.
【解答】
   算法(一)
       Void  exchange ( BiTree  root )
{
    p=root;
              if ( p—>LChild ！= NULL || p->RChild ！= NULL )
 {
                     temp = p->LChild；
p->LChild = p—>RChild;
                     p—〉RChild = temp；
                     exchange （ p—〉LChild )；
                     exchange （ p—>RChild );
              }
       }     

算法（二）
       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；
         }
       ｝     

第六章 习题解析
1．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。
2．对题1所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列.
3．已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……,nk个度为k的结点，则该树中有多少个叶子结点?
[提示]:参考 P。116 性质3
∵　n=n0 + n1 + …… + nk
B=n1 + 2n2 + 3n3 + …… + knk
n= B + 1
∴  n0 + n1 + …… + nk = n1 + 2n2 + 3n3 + …… + knk + 1
∴  n0 = n2 + 2n3 + …… + (k-1)nk + 1
4。假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二叉树。
［提示］:参考 P.148 
6．       已知二叉树有50个叶子结点,则该二叉树的总结点数至少应有多少个？
［提示]：
[方法1]
     （1）一个叶子结点，总结点数至多有多少个？
结论：可压缩一度结点.
（2）满二叉树或完全二叉树具有最少的一度结点
（3）可能的最大满二叉树是几层？有多少叶结点？如何增补?
25〈50<26
可能的最大满二叉树是6层
有 25 = 32个叶结点
假设将其中x个变为2度结点后，总叶结点数目为50
则:2x + (32 – x) = 50
得:x = 18
此时总结点数目= （ 26 – 1） + 18×2
[方法2]
假设完全二叉树的最大非叶结点编号为m，
则最大叶结点编号为2m+1,
(2m+1）-m=50
m=49
总结点数目=2m+1=99
［方法3]
由性质3:n0=n2+1
即：50=n2+1
所以：n2=49
令n1=0得：n= n0 + n2=99
7．       给出满足下列条件的所有二叉树:
a)     前序和中序相同
b)    中序和后序相同
c)     前序和后序相同
［提示]:去异存同.
a)   D L R 与L D R 的相同点：D R,如果无 L，则完全相同, 如果无 LR,…。
b）   L D R 与L R D 的相同点：L D，如果无 R，则完全相同。
c)   D L R 与L R D 的相同点:D，如果无 L R,则完全相同。
（如果去D，则为空树)
7． n个结点的K叉树，若用具有k个child域的等长链结点存储树的一个结点，则空的Child域有多少个?
[提示]：参考 P.119 
8．画出与下列已知序列对应的树Ｔ：
树的先根次序访问序列为GFKDAIEBCHJ；
树的后根次序访问序列为DIAEKFCJHBG.
［提示]：
（1)先画出对应的二叉树
(2）树的后根序列与对应二叉树的中序序列相同
9．假设用于通讯的电文仅由8个字母组成，字母在电文中出现的频率分别为：
0。07，0.19，0.02,0。06，0。32，0。03，0.21,0。10
（1）请为这8个字母设计哈夫曼编码,
（2）求平均编码长度。
10．已知二叉树采用二叉链表存放，要求返回二叉树T的后序序列中的第一个结点的指针,是否可不用递归且不用栈来完成？请简述原因。
［提示］：无右子的“左下端” 
11。 画出和下列树对应的二叉树：

12．已知二叉树按照二叉链表方式存储，编写算法，计算二叉树中叶子结点的数目。
13．编写递归算法：对于二叉树中每一个元素值为x的结点，删去以它为根的子树，并释放相应的空间。
［提示］：
［方法1]：（1）按先序查找；（2）超前查看子结点(3）按后序释放；
void DelSubTree(BiTree  *bt，  DataType x）
{
if （ ＊bt ！= NULL && (*bt） —〉data==x ）
｛  FreeTree(*bt）；
*bt =NULL;
}
else  DelTree( *bt,  x)

void DelTree（BiTree bt,  DataType x)
{ if ( bt )
   ｛ if （bt-〉LChild ＆＆ bt->LChild—〉data==x）
{ FreeTree（bt-〉LChild);
  bt—〉LChild=NULL；
}

     if （bt—>RChild ＆＆ bt—〉RChild->data==x）
{ FreeTree（bt->RChild);
  bt—>RChild=NULL；
｝

DelTree（bt-〉LChild,  x);
DelTree（bt—>RChild,  x);
}
｝
[方法2]：（1)先序查找；(2)直接查看当前根结点（3）用指针参数；
［方法3］:（1）先序查找；（2）直接查看当前根结点
(3)通过函数值,返回删除后结果;
（参示例程序）
14．分别写函数完成:在先序线索二叉树T中，查找给定结点＊p在先序序列中的后继。在后序线索二叉树T中，查找给定结点*p在后序序列中的前驱.
［提示］：
（1）先查看线索，无线索时用下面规律:
(2)结点＊p在先序序列中的后继为其左子或右子;
（3)结点*p在后序序列中的前驱也是其左子或右子。
15．分别写出算法,实现在中序线索二叉树中查找给定结点＊p在中序序列中的前驱与后继。（参例题)

16．编写算法，对一棵以孩子-兄弟链表表示的树统计其叶子的个数.
[提示]：
（1)可将孩子-兄弟链表划分为根、首子树、兄弟树，递归处理。
(2）可利用返回值，或全局变量。

17．对以孩子-兄弟链表表示的树编写计算树的深度的算法。
18．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出后序遍历非递归的算法. （参课本）

19．设二叉树按二叉链表存放，写算法判别一棵二叉树是否是一棵正则二叉树.正则二叉树是指：在二叉树中不存在子树个数为1的结点.
［提示］：可利用任何递归、非递归遍历算法。

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

21．已知二叉树按照二叉链表方式存储，利用栈的基本操作写出先序遍历非递归形式的算法。

22。 证明：给定一棵二叉树的前序序列与中序序列，可唯一确定这棵二叉树；
　　给定一棵二叉树的后序序列与中序序列，可唯一确定这棵二叉树；
23. 二叉树按照二叉链表方式存储，编写算法将二叉树左右子树进行交换。

实习题
1.     [问题描述］ 建立一棵用二叉链表方式存储的二叉树，并对其进行遍历（先序、中序和后序),打印输出遍历结果.
[基本要求］ 从键盘接受输入先序序列,以二叉链表作为存储结构,建立二叉树（以先序来建立）并对其进行遍历(先序、中序、后序），然后将遍历结果打印输出。要求采用递归和非递归两种方法实现。
[测试数据] ABCффDEфGффFффф（其中ф表示空格字符）
          输出结果为： 先序：ABCDEGF
                       中序：CBEGDFA
                       后序：CGBFDBA
2．已知二叉树按照二叉链表方式存储，编写算法,要求实现二叉树的竖向显示（竖向显示就是二叉树的按层显示）.
[提示]:
（1）参习题6.20，实现逐层遍历
（2）队中保存每个结点的打印位置，其左、右子的距离
3．如题1要求建立好二叉树，按凹入表形式打印二叉树结构，如图6。34所示。

图6。34
4．按凹入表形式打印树形结构,如图6。35所示。
［提示]：参P。129例，用先根遍历。