数据结构-树习题课

习题课—树1. 递归 2. 回溯策略 3. 章末复习 4. 例题讲解 5. 课堂练习 6. 作业

例题讲解1、在结点个数为n (n>1)的各棵树中， (1)高度最小的树的高度是多少？它有多少个叶结点？ 多少个分支结点？ (2)高度最大的树的高度是多少？它有多少个叶结点？ 多少个分支结点？ 【答案】 (1)结点个数为n时，高度最小的树的高度为2,有2层； 它有n -1个叶结点，1个分支结点； (2)高度最大的树的高度为n,有n层； 它有1个叶结点，n-1个分支结点。

例题讲解2、试分别找出满足以下条件的所有二叉树：(1) 二叉树的前序序列与中序序列相同; (2) 二叉树的中序序列与后序序列相同; (3) 二叉树的前序序列与后序序列相同。 【解答】 (1) 二叉树的前序序列与中序序列相同： 空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同： 空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同： 空树或只有根结点的二叉树。

例题讲解3、深度为k(根的层次为1)的完全二叉树至少有多少个结 点？ 至多有多少个结点？k与结点数目n之间的关系是什么？ 【分析】 由完全二叉树的定义可知，对于k层的完全二叉树，其上 的k-1层是一棵深度为k-1的满二叉树。所以对于所有深度为k 的完全二叉树，它们之间的结点数目之差等于各树最后一层的 结点数目之差。

例题讲解3、深度为k(根的层次为1)的完全二叉树至少有多少个结 点？ 至多有多少个结点？k与结点数目n之间的关系是什么？ 【解答】

深度为k的完全二叉树，其最少的结点数=深度为k-1的满二 叉树的结点数+1= 2 k 1 1 1 2 k 1;其最多的结点数=深度为k的满 二叉树的结点数= 2 k 1 。k与结点数目n之间的关系可以根据二叉树的性质4得出：k 1 log2

n

例题讲解4、对于深度为h,且只有度为0或2的结点的二叉树，结点数 至少有多少？至多有多少？(分析) 【分析】 对于结点数至多为多少的问题比较好回答，我们知道满 二叉树中只有度为0或2的结点，所以结点数至多为同等深度 的满二叉树的结点数。 对于结点数至少为多少的问题，由于树中只存在度为0 或2的结点，即对一个结点而言，要么它没有子结点，要么 就有两个子结点，所以在这样的树中，除第一层(根所在的 层)外，每一层至少有两个结点。

例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG , 后序序列为DECBHGFA ,求对应的二叉树。(分析) 【分析】 根据各种遍历方法的定义，可知： 二叉树先序序列=根+左子树先序序列+右子树先序列； 二叉树中序序列=左子树中序序列+根+右子树中序列； 二叉树后序序列=左子

树后序序列+右子树后序序列根；

例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG , 后序序列为DECBHGFA ,求对应的二叉树。(分析) 【分析】 从先序和后序序列中可以很容易的知道那一个结点是根， 而在中序序列中，可以根据根得到左、右子树的中序序 列，相应的也就知道左、右子树的结点集合了。可以根 据集合中的结点划分先序或后序序列中除根以外的结点 序列，从而得到左、右子树的先序或后序序列。依次类 推，便可以递归得到整棵二叉树。 中序序列 左子树中序序列 根 前序序列 根 左子树前序序列

右子树中序序列右子树前序序列

例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG , 后序序列为DECBHGFA ,求对应的二叉树。(分析) 【解答】 构造这棵二叉树的过程如下所示：中序序列：BDCE [A] FHG 后序序列：DECB HGF [A] 中序：[B]DCE 后序：DEC[B] 中序： D [C] E 后序：D E [C] 中序：[D] 后序：[D]

中序： [F]HG 后序： HG[F]中序： H[G] 后序： H[G] 中序：[H] 后序：[H]

中序：[E] 后序：[E]

例题讲解可以画出这棵二叉树为：B C D E H A F G

例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK; 中序遍历：HFIEJKG 。该二叉树根的右子树的根是 ( ) A)E B)F C)G D)H 2、某二叉树结点的对称序(中序)序列为ABCDEFG,后序序 列为BDCAFGE。该二叉树结点的前序序列为 ( ) A)EGFACDB B)EACBDGF C)EAGCFBD D)EGACDFB 3、如果一棵二叉树结点的前序序列是ABC,后序序列是CBA, 则该二叉树 结点的对称序序列 A) 必为ABC B) 必为ACB C) 必为BCA D) 不能确定 【答案】 1、C 2、B 3、D

例题讲解6、分别画出具有3个结点的树和具有3个结点的二叉树的所 有不同形态。并判断下列论述是否正确，为什么？ (1)二叉树是一种特殊的树； (2)度为2的树是一棵二叉树； (3)度为2的有序树是一棵二叉树。【解答】具有3个结点的树有两种形态，如图1所示； 而具有3个结点的二叉树有5种形态，如图2所示。

图1

图2 具有3个结点的二叉树的5种形态

例题讲解6、分别画出具有3个结点的树和具有3个结点的二叉树的所 有不同形态。并判断下列论述是否正确，为什么？ (1)二叉树是一种特殊的树； (2)度为2的树是一棵二叉树； (3)度为2的有序树是一棵二叉树。 【答案】 (1)错误 (2)错误 (3)错误

课堂练习7、在二叉树结点的先序序列、中序序列和后序序列中，所有 叶子结点的先后顺序 A)都不相同 B)先序和中序相同，而与后序不同 C)完全相同 D)中序和后序相同，而与先序不同 8、在完全二叉树中，若一个结点只有一个子结点，则它没 A)左子结点 B)左子结点和

右子结点 C)右子结点 D)左子结点、右子结点和兄弟结点 9、在下列存储形式中，哪一个不是树的存储形式 A)双亲表示法 B)孩子链表表示法 B)孩子兄弟表示法 D)顺序存储表示法 【答案】 7、C

8、C

9、D

课堂练习10、在树中，一个结点的直接子结点的个数称为该结点

度 的_____ 。11、如果对于给定的一组权值，所构造出的二叉树的带权路径

哈夫曼树(Huffman) 长度最小，则该树称为_____________________ 。 12、用数组A[1..n]顺序存储完全二叉树的各结点,则当i<=(nA[2i+1] 1)/2时, 结点A[i]的右孩子是 结点______________。叶子 13、完全二叉树中某结点无左子树，则它必是___________。

课堂练习14、对于如图所示的森林 (1)将其转换为相应的二叉树； (2)写出该森林的先序遍历序列和中序遍历序列。A G C H D E F I J L K

B

图题 14

课堂练习A G K B

CH I J L

D

E A

F

【答案】B D C E

先序序列为：ABDEFCGHIJKLG H

中序序列为：DEFBCAHIJGLKK

IJ

L

F

课堂练习15、已知一棵树的先根遍历序列为ABCED,后根遍历序 列为BECDA,求对应的树。 (分析) 【分析】 根据树与二叉树之间的转换关系，可知： 树的先序序列 = 对应二叉树先序序列 树的后跟序列 = 对应二叉树中序序列 因此，可以先这两个序列构造对应的二叉树，再将 二叉树转换为树。

课堂练习15、已知一棵树的先根遍历序列为ABCED,后根遍历序 列为BECDA,求对应的树。 (分析) 【答案】B C E D B C D A A

E

课堂练习16、设电文中出现的字母为A、B、C、D和E,每个字母在 电文中出现的次数分别9、27、3、5、和11。按哈夫曼 编码，则C的编码为 : (分析) A、10 B、110 C、1110 D、1111 【分析】 先构造哈夫曼树，再根据哈夫曼树进行编码。

课堂练习16、设电文中出现的字母为A、B、C、D和E,每个字母在 电文中出现的次数分别9、27、3、5、和11。按哈夫曼 编码，则C的编码为 : (分析) A、10 B、110 C、1110 D、1111 【分析】 55 A B C D E 28 27 9 27 3 5 11 8 17 9 27 11 8 17 11 27 11 17 28 8 9 27 28 55 5 【答案】 C 3

本文来源：https://www.bwwdw.com/article/sv34.html