6 - 1 列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

6 - 2 在结点个数为 n (n>1) 的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？

6 - 3 如果一棵树有 n 1 个度为 1 的结点 , 有 n 2 个度为 2 的结点 , … , n m 个度为 m 的结点 , 试问有多少个度为 0 的结点 ? 试推导之。

6 - 4 试分别找出满足以下条件的所有二叉树 :

(1) 二叉树的前序序列与中序序列相同 ;

(2) 二叉树的中序序列与后序序列相同 ;

(3) 二叉树的前序序列与后序序列相同。

6 - 5 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：

(1) 统计二叉树中叶结点的个数。

(2) 以二叉树为参数，交换每个结点的左子女和右子女。

6 - 6 一棵高度为 h 的满 k 叉树有如下性质 : 第 h 层上的结点都是叶结点 , 其余各层上每个结点都有 k 棵非空子树 , 如果按层次自顶向下 , 同一层自左向右 , 顺序从 1 开始对全部结点进行编号 , 试问 :

(1) 各层的结点个数是多少 ?

(2) 编号为 i 的结点的父结点 ( 若存在 ) 的编号是多少 ?

(3) 编号为 i 的结点的第 m 个孩子结点 ( 若存在 ) 的编号是多少 ?

(4) 编号为 i 的结点有右兄弟的条件是什么 ? 其右兄弟结点的编号是多少 ?

(5) 若结点个数为 n, 则高度 h 是 n 的什么函数关系 ?

6 - 7 试用判定树的方法给出在中序线索化二叉树上：

6 - 8 已知一棵完全二叉树存放于一个一维数组 T[n] 中， T[n] 中存放的是各结点的值。试设计一个算法，从 T[0] 开始顺序读出各结点的值，建立该二叉树的二叉链表表示。

6 - 9 请画出右图所示的树所对应的二叉树。
【解答】

  对应二叉树

6 - 10 在森林的二叉树表示中，用 llink 存储指向结点第一个子女的指针，用 rlink 存储指向结点下一个兄弟的指针，用 data 存储结点的值。如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志 ltag 代替 llink ，用 rtag 代替 rlink 。并设定若 ltag = 0 ，则该结点没有子女，若 ltag 1 0 ，则该结点有子女；若 rtag = 0 ，则该结点没有下一个兄弟，若 rtag 1 0 ，则该结点有下一个兄弟。试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用 llink - rlink 表示的森林。

6 - 11 二叉树的双序遍历 (Double - order traversal) 是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。试写出执行这种双序遍历的算法。

6 - 12 已知一棵二叉树的前序遍历的结果是 ABECDFGHIJ, 中序遍历的结果是 EBCDAFHIGJ, 试画出这棵二叉树。

6 - 13 已知一棵树的先根次序遍历的结果与其对应二叉树表示 ( 长子 - 兄弟表示 ) 的前序遍历结果相同 , 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同。 试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树 ? 举例说明。

【解答】

因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树， 能够唯一地确定一棵树。

6 - 14 给定权值集合 { 15, 03, 14, 02, 06, 09, 16, 17 } , 构造相应的霍夫曼树 , 并计算它的带权外部路径长度。

6 - 15 假定用于通信的电文仅由 8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成 , 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4 。试为这 8 个字母设计不等长 Huffman 编码 , 并给出该电文的总码数。

6 - 16 给定一组权值 : 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充 4 叉树 , 要求该 4 叉树中所有内部结点的度都是 4, 所有外部结点的度都是 0 。这棵扩充 4 叉树的带权外部路径长度是多少 ?

答案

>>返回