图都显示不出来，可以加我Q 527774550,请注明新浪好友

第六章  树

一．名词解释：

1 树    2。结点的度    3。叶子     4。分支点      5。树的度

6．父结点、子结点   7兄弟   8结点的层数 9树的高度  10 二叉树

11 空二叉树 12 左孩子、右孩子 13孩子数 14 满二叉树  15完全二叉树

16 先根遍历 17 中根遍历 18后根遍历 19二叉树的遍历 20 判定树

21 哈夫曼树

二、填空题

1、  树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。

2、  一棵树上的任何结点（不包括根本身）称为根的________。若B是A的子孙，则称A是B的________

3、  一般的，二叉树有______二叉树、______的二叉树、只有______的二叉树、只有______

的二叉树、同时有______的二叉树五种基本形态。

4、  二叉树第i(i>=1)层上至多有______个结点。

5、  深度为k(k>=1)的二叉树至多有______个结点。

6、  对任何二叉树，若度为2的节点数为n2，则叶子数n₀=______。

7、  满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。

8、  具有n个结点的完全二叉树的深度为______。

9、  如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有：

（1）       若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。

（2）       若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。

（3）       若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。

10.二叉树通常有______存储结构和______存储结构两类存储结构。

11.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。

12.对二叉链表的访问只能从______指针开始，若二叉树为空，则______=NULL.

13.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。

14.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左右孩子，其余的________个指针域为NULL。

15．二叉树有不同的链式存储结构，其中最常用的是________与________。

16．可通过在非完全二叉树的“残缺”位置上增设“________”将其转化为完全二叉树。

17．以下程序段采用先根遍历方法求二叉树的叶子数，请在横线处填充适当的语句。

Void countleaf(bitreptr t,int *count)/*根指针为t，假定叶子数count的初值为0*/

  {if(t!=NULL)

     {if((t->lchild==NULL)&&(t->rchild==NULL))________;

      countleaf(t->lchild,&count);

      ________

     }

  }

18．一棵二叉树由根、左子树和右子树三部分组成，因此对二叉树的遍历也可相应地分解成________、________、________三项“子任务”。

19．若以D、L、R分别表示二叉树的三项子任务，限定“先左后右”，这样可能的次序有：________、________、________三种，按这三种次序进行的遍历分别称为________、________、________。

20．树的主要遍历方法有________、________、________等三种。

21．判定树的每个________包含一个条件，对应于一次比较或判断，每个________对应一种分类结果。

22．设定T是一判定树，其终端结点为n₁,……，n_k。每个终端结点ni对应的百分为pi（通常将p_i称为n₁的权）。再假定n_i的祖先数为l_i，这样，按T进行分类的平均比较次数为________。

23．根据文字说明，请在以下横线处填充适当的语句。

采用静态链表作存储结构，设置一个大小为2n-1的数组,令数组每个元素由四个域组成：wt是结点的权值；lchild、rchild分别为结点的左、右孩子指针；parent是结点的双亲在数组中的下标。其数组元素类型定义如下：

typedef struct

  {float wt                                  

int parent,lchild rchild;                  

   }node;

   typedef node hftree[2*n-1];

在这种存储结构上的哈夫曼算法可描述如下：

void Huffman(int k,float W[k],hftree T)          

{int i,j,x,y;

float m,n;

for(i=0;i<2*k-1;i++)

{  T[i].parent=-1;T[i].lchild=-1;T[i].rchild=-1;

   if(________)T[i].wt=W[i];

      else T[i].wt=0

}

for(i=0;i<k-1;i++)

{   x=0;y=0;m=maxint;n=maxint;

    for(j=0;j<k=i;j++)

     if((T[j].wt<m)&&(T[j].parent==-1)){n=m;y=________;m=________;x=j;}

         else if((T[j].wt<n)&&(T[j].parint==-1)){n=T[j].wt;y=j;}

       T[x].parent=________;T[y].parent=________;

       T[k+i].wt=________;

       T[k+i].lchild=________;T[k+i].rchild=________;

}

24．若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。

25．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。

26．具有n个结点的完全二叉树，若按层次从上到下、从左到右对其编，号（根结点为1号），则编号最大的分支结点序号是________，编号最小的分支结点序号是________，编号最大的叶子结点序号是________，编号最小的叶子结点序号是________。

27．二叉树的先根遍历序列中，除根结点外，任一结点均处在其双亲结点的________。

28．先根遍历树和先根遍历与该树对应的二叉树，其结果________。

29．树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。

30．由________转换成二叉树时，其根结点的右子树总是空的。

31．哈夫曼树是带权路径度________的树，通常权值较大的结点离根________。

32．有m个叶子结点的哈夫曼树，其结点总数为________。

 

33．一棵树的形状如图填空题33所示，它的根结点是________，叶子结点是________，结点H的度是________，这棵树的度是________，这棵树的深度是________，结点F的儿子结点是________，结点G的父结点是________。

34．树的结点数目至少为________，二叉树的结点数目至少为________。

35．________中结点的最大度数允许大于2，而________中结点的最大度数不允许大于2。

36．结点最少的树为________，结点最少的二叉树为________。

37．若一棵二叉树的叶子数为n，则该二叉树中，左、右子树皆非空的结点个数为________。

38．任意一棵具有n个结点的二叉树，若它有m个叶子，则该二叉树上度数为1的结点为________个。

39．现有按中序遍历二叉树的结果为ABC，问有________种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是________。

40．以数据集{4，5，6，7，10，12，18}为叶结点权值所构造的哈无曼树为________，其带权路径长度为________。

41．有m个叶子结点的哈夫曼树上的结点数是________。

42．已知一棵度为3的树有2个度为1的结点，3个度过为2的结点，4个度为3的结点，则该树中有________个叶子结点。

43．设树T的度为4，其中度为1、2、3和4的结点个数分别是4、2、1和1，则T中叶子结点的个数是________。

三、单向选择题

1．  以下说法错误的是                                               (        )

①树形结构的特点是一个结点可以有多个直接前趋

②线性结构中的一个结点至多只有一个直接后继

③树形结构可以表达(组织)更复杂的数据

④树(及一切树形结构)是一种"分支层次"结构

⑤任何只含一个结点的集合是一棵树

2，以下说法错误的是                                               (        )

①二叉树可以是空集

②二叉树的任一结点都有两棵子树

③二叉树与树具有相同的树形结构

④二叉树中任一结点的两棵子树有次序之分

3、以下说法错误的是                                                (        )

①完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达

②在三叉链表上，二叉树的求双亲运算很容易实现

③在二叉链表上，求根，求左、右孩子等很容易实现

④在二叉链表上，求双亲运算的时间性能很好

4、以下说法错误的是                                               (        )  

①一般在哈夫曼树中，权值越大的叶子离根结点越近

②哈夫曼树中没有度数为1的分支结点

③若初始森林中共有n裸二叉树，最终求得的哈夫曼树共有2n-1个结点

④若初始森林中共有n裸二叉树，进行2n-1次合并后才能剩下一棵最终的哈夫曼树

5．深度为6的二叉树最多有(    )个结点                              (        )

①64      ②63      ③32       ④31

6．将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双结点编号为                   (        )

①42     ②40        ③21        ④20

7．任何一棵二叉树的叶结点在其先根、中根、后跟遍历序列中的相对位置  (        )  

①肯定发生变化      ②有时发生变化

③肯定不发生变化    ④无法确定

8．设二叉树有n个结点，则其深度为                                 (        )

①n-1     ②n     ③5floor(log₂n)    ④无法确定

9．设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少（   ）个

①k+1      ②2k    ③2k-1     ④2k+1

10.下列说法正确的是                                                 (        )

①树的先根遍历序列与其对应的二叉树的先根遍历序列相同

②树的先根遍历序列与其对应的二叉树的后根遍历序列相同

③树的后根遍历序列与其对应的二叉树的先根遍历序列相同

④树的后根遍历序列与其对应的二叉树的后根遍历序列相同

11．下列说法中正确的是                                              (        )

①任何一棵二叉树中至少有一个结点的度为2

②任何一棵二叉树中每个结点的度都为2

③任何一棵二叉树中的度肯定等于2

④任何一棵二叉树中的度可以小于2

12．一棵二叉树满足下列条件：对任意结点，若存在左、右子树，则其值都小于它的左子树上所有结点的值，而大于右子树上所有结点的值。现采用（    ）遍历方式就可以得到这棵二叉树所有结点的递增序列。

①先根    ②中根    ③后根    ④层次

13．设森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的右子树上有（    ）个结点。

①n₁-1    ②n₁    ③n₁+n₂+n₃    ④n₂+n₃+n₄

14．森林T中有4棵树，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4,那么当把森林T转换成一棵二叉树后，且根结点的左孩子上有（    ）个结点。

①n₁-1    ②n₁    ③n₁+n₂+n₃   ④n₂+n₃+n₄

15.对含有（       ）个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。

①0        ②1             ③2             ④不存在这样的二叉树

16．讨论树、森林和二叉树的关系，目的是为了（    ）

①借助二叉树上的运算方法去实现对树的一些运算

②将树、森林按二叉树的存储方式进行存储

③将树、森林转换成二叉树

④体现一种技巧，没有什么实际意义

 

 

17．如图选择题17所示二叉树的中序遍历序列是（         ）

①abcdgef        ② dfebagc          ③dbaefcg         ④defbagc

18.已知某二叉树的后续遍历序列是dabec,中序遍历序列是deabc,它的前序遍历序列是（  ）

①acbed         ②deabc           ③decab     ④cedba

19.如果T₂是由有序树T转化而来的二叉树，那么T中结点的前序就是T₂中结点的（    ）

①前序           ②中序        ③后序          ④层次序

20．如果T₂是由有序树T转化而来的二叉树，那么T中结点的后序就是T₂中结点的（    ）

①前序           ②中序        ③后序          ④层次序

21．某二叉树的前序遍历结点访问顺序是abdgcefh,中序遍历的结点访问顺序是dgbaechf,则其后序遍历的结点访问顺序是                                              （    ）

①bdgcefha         ②gdbecfha          ③④ bdgechfa      ④ gdbehfca

22.在图选择题22中的二叉树中，（      ）不是完全二叉树。

 

23、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法     (   )

①正确           ②错误

24、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法     (   )

①五确           ②错误

25，二叉树是每个结点的度不超过2的有序树的特殊情况，这种说法      (   )

①正确           ②错误

26·树最适合用来表示                                          (   )

①有序数据元素                                 ②无序数据元素

③元素之间具有分支层次关系的数据               ④元素之间无联系的数据

27，深度为5的二叉树至多有(   )个结点。

①16       ②32         ③31             ④10

28、在计算递归函数时，如不使用递归过程，则一般情况下必须借助于（    ）数据结构

①栈       ②树         ③双向队列       ④顺序表

29.堆(Heap)是                                                 (   )

①完全二叉树            ②线性表         ③满二叉树

30、下列说法中正确的是                                          (   )

①二叉树中任何一个结点的度都为2          ②二叉树的度为2

③任何一棵二叉树中至少有一个结点的度为2  ④一棵二叉树的度可以小于2

31、设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是（    ）

①2^h             ②2^h-1             ③2^h-1           ④2^h+1-1

32、设二叉树结点的先根序列、中根序列和后根序列中，所有叶子结点的先后顺序(   )

①都不相同                         ②完全相同                                    

③先序和中序相同，而与后序不同     ④中序和后序相同，而与先序不同

33·以下说法错误的是                                          (   )

①存在这样的二叉树，对它采用任何次序的遍历，其结点访问序列均相同

②二叉树是树的特殊情形

③由树转换成二叉树，其根结点的右子树总是空的

④在二叉树只有一棵子树的情况下也要明确指出该子树是左子树还是右子树

34、以下说法正确的是                                         (   )

①先根遍历树和前序遍历与该树对应的二叉树，其结果不同

②后根遍历树和前序遍历与该树对应的二叉树，其结果不同

③前序遍历森林和前序遍历与该森林对应的二叉树，其结果相同

④后序遍历森林和中序遍历与该森林对应的二叉树，其结果不同

35·以下说法正确的是                                         (   )

①一般来说，若深度为k的n个结点的二叉树具有最小路径长度，那么从根结点到第k-1层具有最多的结点数为2^k-1-1余下的n-2^k-1+1个结点在第k层的任一位置上

②若有一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。

③若一个结点是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序遍历序列中的最后一个结点。

④在二叉树中插人结点，该二叉树便不再是二叉树

36、以下说法正确的是                                                (    )

①若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的前序遍历序列中的最后一个结点。

②若一个树叶是某二叉树子树的前序遍历序列中的最后一个结点，则它必是该子树的中序离历序列中的最后一个结点

③二叉树中，具有两个子女的父结点，在中序遍历序列中，它的后继结点最多只能有一个子女结点。

④在二叉树中，具有一个子女结点，在中序遍历序列中，它没有后继子女结点。

37、以下说法错误的是                                     (    )

①哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

②若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。

③已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。

④在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。

四、简答及应用题

1．简述二叉链表的类型定义。

2．简述三叉链表的类型定义。

3．简述孩子链表表示法的类型定义。

4．分别就图简答题4.1中的二叉树和树回答下列问题

(1)哪个是根结点?

(2)哪些是叶结点?

(3)哪个是G的双亲?

(4)哪些是G的祖先?

(5)哪些是G的孩子?

(6)哪些是E的子孙?

(7)哪些是E的兄弟? 哪些是C的兄弟?

(8)结点B和I的层数分别是多少?

(9)树的深度是多少?

(10)以结点G为根的子树的深度是多少?

(11)树的度数是多少？         

 

5．为什么图简答题5所示的结构都不是树形结构？详细说明理由。

 

6．分别画出含3个结点的树与二叉树的所有不同形态。

7．分别画出图简答题7-1所示二叉树的二叉链表、三叉链表和顺序存储结构。

 

8．分别写出图简答题4.1（a）所示二叉树的先根、中根和后根序列。

9.试找出分别满足下列条件的所有二叉树：

（1）       先根序列和中根序列相同； （2）中根序列和后根序列相同；

（ 3 ）先根序列和后根序列相同。

10．已知一棵二叉树的中根序列和后根序列分别为BDCEAFHG和EDCBHGEA，试画出这棵二叉树。

11．       试分别画出图简答题11-1所示树的孩子链表、孩子兄弟链表和静态双亲链表。

 

12．分别给出简答题11.1图中树的先根、后根和层次遍历的结点访问序列。

13．将图简答题13-1所示的林转换成二叉树。

 

14．分别画出图简答题14-1所示各二叉树对应的林。

 

15．给定权值7，18，3，32，5，26，12，8，构造相应的哈夫曼树。

16．试以三种遍历为基础，分别写出在二叉树上查找直接前趋或直接后继的关键操作步骤。

17．已知一棵二叉树的前根序列和中根序列分别为ABDGHECFIJ及GDHBEACIJF，请画出这棵二叉树。

18．设某密码电文由8个字母组成，每个字母在电文中的出现频率分别是7，19，2，6，32，3，21，10，试为这8个字母设计相应的哈夫曼编码。

19．有一二叉树如图19-1所示，试画出它的顺序存储结构示意图。

 

20．将图简答20-1所示森林转换为二叉树。

 

五，算法设计

1、以二叉链表为存储结构，分别实现二叉树的下列运算:

（1）PARENT (BT,X)；

（2）CREATE ( X, LBT.RBT)；

(3)DELLEFT(BT,X)。

2.以三叉链表作存储结构重做上题。

3．以二叉链表作存储结构，试编写求二叉树深度的算法。

4．一棵n个结点的完全二叉树存放在二叉树的顺序存储结构中，试编写非递归算法对该树进行先根遍历。

5．试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价，则T1和T2都是空的二叉树；或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。

6．试编写算法交换二叉树中所有结点的左、右子树（自选存储结构）。

7．试编写算法查找二叉链表中数据域值为X的结点（假定各结点的数据域值各不相同），并打印出X所有祖先的数据域值（提示：利用后根遍历非递归算法）。

8．试以孩子链表为存储结构，实现树数据结构的下列运算：

（1）PARENT（T，X）；   （2） CHILD (T,X,i)；    （3）DELETE(T,X，i)。

9．试分别以孩子兄弟链表和静态双亲链表为存储结构，重做上题。

10．试分别编写二叉树中根遍历在下列存储结构上的非递归算法：

（1）       二叉链表；

（2）       三叉链表（提示：考虑是否需要引入工作栈）；

11．试分别编写二叉树后根遍历在下列存储结构上的非递归算法：

（1）       二叉链表（提示：可在指针进栈的同时将一个标志进栈）；

（2）       在存储结点中增设了标志域的mark:0..2的三叉链表（要求不用工作栈）；

12．试编写一个将百分制转换成五分制的算法，要求其时间性能尽可能地高（即平均比较次数尽可能少）。假定学生成绩的分布情况如下：

分数	0-59	60-69	70-79	80-89	90-100
比例	0．05	0．15	0．40	0．30	0．10

13．有一二叉链表，按后根遍历时输出的结点顺序为a₁, a₂,…a a_n。试编写一算法，要求输出后根序列的逆序a_n,a_n-1 …，a₂ , a₁ 。

14．有一二叉链表，试编写按层次顺序遍历二叉树的算法。

15．以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。