___________，它共有___________个叶子结点和___________个分支结点。

8、设深度为 h 的二叉树只有度为 0 和 2 的结点，该二叉树的结点数可能达到的最大值为___________，最小值为___________。

9、已知按先序遍历二叉树的结果为ABC，则共有___________种不同的二叉树可以得到这一遍历结果。

四、解答题

1、已知一棵二叉树的先序遍历序列是ABCDEFGHIJK，中序遍历序列是CDBGFEAHJIK，请构造出该二叉树，并给出该二叉树的后序遍历序列。 2、已知五个权值分别为9，2，5，7，14的叶子结点：

①构造一棵赫夫曼树； ②求此树的带权路径长度。 3、将下图所示的森林转化为二叉树。

ABCE4、已知二叉树的二叉链表定义如下： typedef char TElemType； typedef struct BiTNode { TElemType data；

struct BiTNode *lchild，*rchild； }*BiTree；

FDHGIJ

BiTree root；//root是指向以下二叉树根结点A的指针

- 21 -

ABCE

void traversal(BiTree T) { if (T) {

printf(\，T->data)； traversal(T->lchild)； printf(\，T->data)； traversal(T->rchild)； } }

试回答下列问题：

⑴给出算法traversal(root)的输出结果； ⑵分析算法traversal的时间复杂度。

5、已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，……，nk个度为k 的

结点，问该树中有多少个叶子结点？

6、已知在一棵含有n 个结点的树中，只有度为k 的分支结点和度为0的叶子结点。试求该树含有的叶子结点的数目。 7、找出所有满足下列条件的二叉树：

⑴它们在先序遍历和中序遍历时，得到的结点访问序列相同； ⑵它们在后序遍历和中序遍历时，得到的结点访问序列相同； ⑶它们在先序遍历和后序遍历时，得到的结点访问序列相同。 8、对第3题中森林分别进行先序遍历和中序遍历，给出遍历结果。

- 22 -

DFG

9、一棵含有n个结点的k叉树，可能达到的最大深度和最小深度各为多少？

10、已知一棵二叉树的层次遍历序列是ABCDEFGHIJ，中序遍历序列是DBGEHJACIF，请

构造出该二叉树。

五、算法设计题

注：下列各题中的二叉树如未特殊说明均采用二叉链表作为存储结构。

1、参照课本提供的CreateBiTree和PreOrderTraverse算法，完成对下图所示二叉树的创建以及先序、中序和后序遍历操作。

ABCE2、 求二叉树中分支结点和叶子结点的数目。 3、 求二叉树的深度。

4、 销毁二叉树中的所有结点，要求在销毁每一个结点前，输出该结点的数据域。 5、 编写从上至下、从左到右按层次遍历二叉树的算法。 6、 编写递归算法：将二叉树中所有结点的左、右子树相互交换。 7、 编写算法判别给定二叉树是否为完全二叉树。

8、 编写递归算法：输出在二叉树的先序序列中第k个位置的结点的数据域。

9、 一棵二叉树的繁茂度定义为各层结点数的最大值与树的深度的乘积，编写算法求二叉树

的繁茂度。

10、为二叉链表的结点中增加DescNum域，编写算法求二叉树每个结点的子孙数目并存入

其DescNum域。

11、已知一颗二叉树的先序序列和中序序列，写一个建立该二叉树的二叉链表存储结构的算

法。

12、给出二叉树中的一个非根节点（由指针p所指），求它的兄弟节点（要求用指针q指向

它，若没有兄弟节点，这q为空）。

- 23 -

DFG

13、设计一个中序遍历非递归算法。 14、设计一个后序遍历非递归算法。

15、已知n个节点的完全二叉树已经顺序存储在一维数组A[1…n]中，试设计一算法将其变

成二叉链表存储的完全二叉树。

- 24 -