2．任何一个非空树中：有且仅有一个特定的结点，称为该树的______________的结点，___________结点之外的其余结点可分为m(m≥0)个互不相交的有限集合T1，T2，?，Tm，且其中每一个结点又是一棵树，称之为__________的______________。

3．树的__________是指一个数据元素及指向其子树的分支。通常通过一个__________来描述，在树型表示中，用一个圆圈及短线表示。

4．结点的度是指结点所拥有的________________。 5．树内各结点度的___________________为树的度。

6．度大于0的结点称为________________或______________________。 7．____________称为叶子结点，简称为叶子，又称作终端结点。 8．一个结点的____________，或者说一个结点的____________称为该结点的孩子结点，简称为孩子。

9．一个结点称为其后继结点（即孩子结点）的______________。

10．一个结点的子树中的任一结点都称为该结点的___________________。 11．从根到该结点所经分支上的所有结点称为该结点的_______________。 12．具有_______________________的结点互称为兄弟结点，简称为兄弟。

13．从根结点开始定义，根为________层，根的孩子为__________层，依次往下类推，若某结点在第k层，则其子树的根就在_________________层。 14．其双亲在同一层次上的结点互称为___________________。 15．树中结点的___________称为树的深度，又称为树的高度。

16．如果树中各结点的各子树从左至右是有序排列，不可互换的，则称该树为______。 17．如果树中各结点的各子树无排列顺序，即可以互换位置，则称为该树为_________。 18．n(n≥0)棵互不相交的树的集合称为______________________。

19．二又树（Binary Tree）是结点的有限集合，这个集合或者是空，或者是由一个根结点和__________的称为______________和____________的二叉树构成。 20．二叉树第i层上最多有____________个结点。

21．深度为k的二又树最多有____________个结点(k≥l)。

22．在任意二叉树中，叶子结点的数目(即度为0的结点数)等于度为2的结点数____________。

23．一棵深度为k且具有2k-1个结点的二叉树称为__________。这类二叉树的特点是，二叉树中每一层结点的个数都是______________的个数。

24．_________是那种在一棵二叉树中，除最后一层外，若其余层都是满的，并且最后一层或者是满的，或者所缺少的结点都在右边。

25．具有n个结点的完全二叉树的深度是_______________。

26．对于一棵有n个结点的完全二叉树的结点进行编号（自上而下，子左至右），则对任一结点 i（l≤i≤n），如果结点i=l，则结点i是二叉树的____________，无双亲；如果结点i>l，则其双亲Parent(i)的序号是结点_______________；如果2i≤n，则结点i的左孩子Lchild(BT,，i）是_________，否则结点i无左孩子(结点i必为叶子结点)；如果2i＋l≤n，则结点i的右孩子 RChild（BT，i）的序号是____________；否则该结点无右孩子。 27．二叉树的顺序存储结构是用_________________存储二叉树的数据元素。 28．____________是指按照某条搜索路径访问树中的某个结点，使得树中每个结点均被访问一次，而且仅被访问一次。

29．先序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：访问二叉树____________；先序遍历二叉树____________；先序遍历二叉树_________。 30．中序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：

21

中序遍历二叉树__________；访问二又树__________；中序遍历二又树____________。 31．后序遍历二叉树的操作定义为：若二叉树为空，则为空操作；否则进行如下操作：后序遍历二叉树___________；后序遍历二叉树_________；访问二叉树_____________。 32．线索二叉树（Threaded Binary Tree）是充分利用二义链表的 n+1个空的指针域作为线索来标志每一个结点的________和__________信息。当某个结点有左孩子的时候，使其___________指向其左孩子，无左孩子的时候，使其左指针域指向该结点的___________；当某个结点有有孩子的时候，使其右指针域指向该结点的__________，无右孩子的时候，使其有指针域指向该结点的_____________。

33．线索二叉树的线索链表中，指向结点前驱和后继的指针称为___________；加上线索的二叉树称为_____________；对二叉树以某种次序进行遍历使其成为线索二叉树的过程称为_______________________。

34．树的存储结构常见的有____________、____________和________________。 35．树的先序遍历过程如下：若树为空，则进行空操作；若树非空，则：访问树 的＿；依次先序遍历树的＿。

36．树的后序遍历过程为：若树为空，则进行空操作；若树非空，则：依次后序遍历__________；访问_________________。

37．森林的先序遍历过程为：若森林非空，则： （1）访问森林中第一棵树的___________。 （2）先序遍历第一棵树中_____________。 （3）先序遍历_______________________。

38．森林的后序遍历过程为：若森林非空，则： （l）后序遍历森林中第一棵树的_______________。 （2）访问第一棵树的_________________________。 （3）后序遍历_______________________________。

39．从树中一个结点到另一个结点之间的_________称为这两个结点的路径。 40．路径上的分支数目称为______________。

41．树的路径长度是指从树根到每一结点的__________________。

42．将树中的结点赋上一个有着某种意义的实数，称此实数为该结点的____________。 43．树的带权路径长度为树中所有叶子结点的____________。

44．哈夫曼树（Huffman Tree）又称___________。它是n个带权叶子结点构成的所有二叉树中，带权路径长度WPL__________________。

45，所谓前缀编码是指在所有对字符的编码中，任何一个字符都不是____________。

46．已知完全二叉树的第八层有8个结点，则其叶子结点数是__________________。 47．在有n个叶子结点的哈夫曼树中，总结点数是___________。

48．已知完全二又树的第7层有10个叶子结点，则整个二又树的结点数最多是___。 49．已知二叉树中叶子数为50，仅有一个孩子的结点数为30，则总结点数为___。 50．一棵树T采用二叉链表BT存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定满足___________________。

51．在二叉链表中，判断某指针P所指结点为叶子结点的条件是______________。 52．若以{4，5，6，7，8}作为叶子结点的权值构造哈夫曼树，则其带权路径长度是___________。

53．已知二叉树有50个叶子结点，则该二叉树的总结点数至少是______________。 54．3个结点可构成___________________棵不同形态的树。

55．已知完全二叉树的第七层有8个结点，则其叶子结点数是______________.

22

56．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结 点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为____________。

57．若要对某二叉排序树进行遍历，保证输出的所有结点序列按键值递增次序排列， 应对该二叉树采用_______________遍历法。 三、判断题

1．完全二叉树的某个结点若无左孩子，则它必然是叶结点。（ ） 2．存在这样一种二叉树，对它采用任何次序的遍历结果相同。（ ） 3．度为二的树称为二叉树。（ ） 4．二叉树中不存在度大于2的结点。（ ）

5．当二叉树中某个结点只有一棵子树的时候，无左右子树之分。（ ） 6．任何一棵二叉树都可以不用栈实现前序线索树的前序遍历。（ ） 7．哈夫曼编码是一种前缀编码，不允许出现两个字符编码相同的情况。（ ） 8．完全二叉树某结点有右子树，则必然有左子树。（ ） 9．前序遍历一棵二叉树的结点就可以得到排好序的结点序列。（ ） 10．将一棵拥有子树的树转换为二叉树后，根结点可能没有左子树。（ ） 11．根据二叉树的前序遍历和中序遍历可以得到二又树的后序遍历。（ ） 12．哈夫曼树是带权路径长度最短的树。（ ） 13．哈夫曼树的路径上权值较大的结点离根较远。（ ）

14．后序遍历森林与后序遍历与森林相对应的二叉树结果相同。（ ）

15．在二叉树中，具有一个孩子的结点，在中序遍历序列中，没有后继子女结点。

（ ）

16．前序遍历与森林相对应的二叉树结果不同。（ ）

17．若一棵二叉树的任一非叶子结点的度为2，则该二叉树为满二叉树。（ ） 18．二叉树只能采用二叉链表来存储。（ ） 19．给定结点数的平衡二叉树的高度是惟一的。（ ） 四、综合题

1．一棵树表达成如下形式：

D＝{A，B，C，D，E，F，G， H，I，J，K，L，M，N，O}

R=＜A，B＞，＜A，C＞，＜A，D＞，＜B，E＞，＜B，F＞，＜C，G＞，＜D，H＞，＜D，I＞，＜D，J＞，＜K，F＞，＜K，L＞，＜F，M＞，＜I，N＞，＜I，O＞｝

其中D为结点集合，R为边的集合。请根据以上内容回答以下问题： (1) 画出这棵树。

(2) 该树的根结点是哪一个？ (3) 哪些是叶子结点？ (4) F结点的双亲是谁？ (5) F结点的祖先是哪些？ (6) F结点的孩子是哪些？ (7) F结点的兄弟是哪些？ (8) F结点的堂兄弟是哪些？ (9) F结点的度是多少？ (10)F结点的层次是多少？ (11)D结点的子孙有哪些？

(12) 以结点D为根的子树度是多少？ (13) 以结点D为根的子树层是多少？

23

(14) 该树的层是多少？ (15) 该树的度是多少？

2．画出图6-1中树的二叉树表示形式。

（a） （b） （c） 图6-l

3．已知某二叉树的先序遍历的结果是：A，B，D，QC，E，H，L，I，K，M，F和J，它的中序遍历的结果是：QD，B，A，L，H，E，K，LM，C，F和J，请画出这棵二叉树，并且写出该二叉树后序通历的结果。

4．写一个将一棵二叉树复制给另一棵二又树的算法。

5．已知—个二叉树用二叉链表表示，其根指针为t，请写一个算法，从根结点开始按层次通历该二叉树，同层的结点接从左到右的次序进行访问。

6．已知一棵二叉树的先序遍历序列和中序遍历序列，请写出根据二又树先序遍历序列和中序遍历序列构造一棵二叉树的算法。

7．假设一棵哈夫曼树共有n0个叶子结点，试证明树中共有2no-l个结点。

8．假设通信用的报文由9个字母A、B、C、D、E、F、G、H和I构成，它们出现的频率分别是：10、20、5、15、8、2、3、7和30。请用这9个字母出现得频率作为权值求：

（l）设计一棵哈夫曼树。

（2）计算其带权路径长度WPL值。 （3）写出每个字符的哈夫曼编码。

24