第 6 章 树与森林66 第 6 章 树与森林6- 5 在结点个数为n (n>1)的各棵树中， 高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？6- 6 试分别画出具有3 个结点的树和3 个结点的二叉树的所有不同形态6- 7 如果一棵树有n1个度为 1 的结点 , 有 n2个度为 2 的结点 , ⋯ , nm个度为 m 的结点 , 试问有多少个度为 0 的结点 ? 试推导之6- 9 若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：(1) 统计二叉树中叶结点的个数2) 以二叉树为参数，交换每个结点的左子女和右子女6- 10 一棵高度为h的满 k 叉树有如下性质: 第 h 层上的结点都是叶结点, 其余各层上每个结点都有k 棵非空子树 , 如果按层次自顶向下, 同一层自左向右, 顺序从 1 开始对全部结点进行编号, 试问 : (1) 各层的结点个数是多少? (2) 编号为 i 的结点的父结点(若存在 )的编号是多少? (3) 编号为 i 的结点的第m 个孩子结点 (若存在 )的编号是多少 ? (4) 编号为 i 的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为n, 则高度 h 是 n 的什么函数关系? 6- 16 请画出右图所示的树所对应的二叉树。
解答】6- 17 在森林的二叉树表示中，用llink 存储指向结点第一个子女的指针，用 rlink 存储指向结点下一个兄弟的指针，用data存储结点的值如果我们采用静态二叉链表作为森林的存储表示，同时按森林的先根次序依次安放森林的所有结点，则可以在它们的结点中用只有一个二进位的标志ltag 代替 llink ，用 rtag代替 rlink 并设定若ltag = 0，则该结点没有子女，若ltag 0，则该结点有子女；若rtag = 0，则该结点没有下一个兄弟，若rtag 0，则该结点有下一个兄弟试给出这种表示的结构定义，并设计一个算法，将用这种表示存储的森林转换成用llink - rlink 表示的森林解答】1 对应二叉树2 3 4 5 6 7 8 A B C D E F G H K J I H J 对应二叉树llink data rlink0 1 2 3 4 5 6 7 8 9 10 1 -1 -1 4 -1 6 -1 8 9 -1 -1 A B C D E F G H I K J 5 2 3 -1 -1 7 -1 -1 10 -1 -1 森林的左子女 - 右兄弟 表示的静态二叉链表0 1 2 3 4 5 6 7 8 9 10 第 6 章 树与森林67 6- 18 二叉树的双序遍历(Double - order traversal)是指：对于二叉树的每一个结点来说，先访问这个结点，再按双序遍历它的左子树，然后再一次访问这个结点，接下来按双序遍历它的右子树。
试写出执行这种双序遍历的算法6- 19 已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树6- 20 已知一棵树的先根次序遍历的结果与其对应二叉树表示(长子 - 兄弟表示 )的前序遍历结果相同, 树的后根次序遍历结果与其对应二叉树表示的中序遍历结果相同试问利用树的先根次序遍历结果和后根次序遍历结果能否唯一确定一棵树? 举例说明解答】因为给出二叉树的前序遍历序列和中序遍历序列能够唯一地确定这棵二叉树，因此，根据题目给出的条件，利用树的先根次序遍历结果和后根次序遍历结果能够唯一地确定一棵树例如，对于题6-16 所示的树6- 21 给定权值集合 {15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权外部路径长度6- 22 假定用于通信的电文仅由8 个字母 c1, c2, c3, c4, c5, c6, c7, c8 组成 , 各字母在电文中出现的频率分别为 5, 25, 3, 6, 10, 11, 36, 4试为这8 个字母设计不等长Huffman 编码 , 并给出该电文的总码数6- 23 给定一组权值 : 23, 15, 66, 07, 11, 45, 33, 52, 39, 26, 58, 试构造一棵具有最小带权外部路径长度的扩充 4 叉树 , 要求该 4 叉树中所有内部结点的度都是4, 所有外部结点的度都是0。
这棵扩充4 叉树的带权外部路径长度是多少? 【解答】权值个数n = 11，扩充 4 叉树的内结点的度都为4，而外结点的度都为0设内结点个数为n4，外结点个数为n0，则可证明有关系n0 = 3 * n4 + 1由于在本题中n0 = 11≠3 * n4 +1，需要补2 个权值为0 的外结点此时内结点个数n4 = 4仿照霍夫曼树的构造方法来构造扩充4叉树，每次合并4 个结点ltag data rtag1 0 0 1 0 1 0 1 1 0 0 A B C D E F G H I K J 1 1 1 0 0 1 0 0 1 0 0 森林的双标记表示0 0 7 0 11 15 23 26 33 39 45 52 58 66 58 66 82 169 15 23 26 18 33 39 45 52 375 0 0 7 0 11 1 2 3 4 5 6 7 8 对应二叉树1 2 3 4 5 6 7 8 对应二叉树的前序序列为1, 2, 3, 4, 5, 6, 8, 7 ；中序序列为3, 4, 8, 6, 7, 5, 2, 1原树的先根遍历序列为 1, 2, 3, 4, 5, 6, 8, 7 ；后根遍历序列为3, 4, 8, 6, 7, 5, 2, 1。
第 6 章 树与森林68 此树的带权路径长度WPL = 375 + 82 + 169 + 18 = 644 6-5 结点个数为n 时，高度最小的树的高度为1，有 2 层；它有n- 1 个叶结点， 1 个分支结点；高度最大的树的高度为n- 1，有 n 层；它有1 个叶结点， n- 1 个分支结点6- 6【解答】具有 3 个结点的树具有 3 个结点的二叉树6- 7 总结点数n = n0 + n1 + n2 + ⋯ + nm总分支数e = n- 1 = n0 + n1 + n2 + ⋯ + nm- 1 = m*nm + (m- 1)*nm-1 + ⋯ + 2*n2 + n1则有1)1(20miinin6- 9【解答】(1) 统计二叉树中叶结点个数int BinaryTree :: leaf ( BinTreeNode * ptr ) { if ( ptr == NULL ) return 0; else if ( ptr-> leftChild == NULL elsereturn leaf ( ptr->leftChild ) + leaf ( ptr -> rightChild ) ; } (2) 交换每个结点的左子女和右子女void BinaryTree :: exchange ( BinTreeNode * ptr ) { BinTreeNode * temp;if ( ptr->leftChild != NULL || ptr-> rightChild != NULL ) { temp = ptr->leftChild ; ptr-> leftChild = ptr -> rightChild ; ptr-> rightChild = temp ;exchange ( ptr-> leftChild ) ;exchange ( ptr-> rightChild ) ; } } 6- 10【解答】(1) ki( i = 0, 1, ⋯⋯ , h ) (2) k2ki(3) ( i- 1)*k + m + 1 (4) ( i- 1 ) % k 0 或k*k2kii时有右兄弟，右兄弟为i + 1。
5)h = logk (n*(k - 1)+1) - 1 (n = 0 时 h = - 1 ) 第 6 章 树与森林69 6- 18【解答】template void BinaryTree :: Double_order ( BinTreeNode *current ) { if ( current != NULL ) {cout data leftChild ) ;cout data rightChild ) ; } } 【解答】6- 19 当前序序列为ABECDFGHIJ ，中序序列为EBCDAFHIGJ 时，逐步形成二叉树的过程如下图所示：6- 22【解答】已知字母集{ c1, c2, c3, c4, c5, c6, c7, c8 }，频率{5, 25, 3, 6, 10, 11, 36, 4 }，则 Huffman 编码为c1 c2 c3 c4 c5 c6 c7 c8 0110 10 0000 0111 001 010 11 0001 电文总码数为4 * 5 + 2 * 25 + 4 * 3 + 4 * 6 + 3 * 10 + 3 * 11 + 2 * 36 + 4 * 4 = 257 EBCD FHIGJ A A B E F CD HIGJ A B E F C D G J HI A B E F C D G J H I 100 61 39 36 25 22 17 7 10 11 11 4 3 6 5 C3 C8 C5 C6 C1 C4 C2 C7 0 0 0 0 0 0 0 1 1 1 1 1 1 1 。