《数据结构-树习题课》由会员分享，可在线阅读，更多相关《数据结构-树习题课（22页珍藏版）》请在金锄头文库上搜索。
1、习题课树1. 递归2. 回溯策略3. 章末复习4. 例题讲解5. 课堂练习6. 作业例题讲解1、在结点个数为n (n1)的各棵树中，（1）高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？（2）高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 【答案】 （1）结点个数为n时，高度最小的树的高度为2，有2层；它有n -1个叶结点，1个分支结点；（2）高度最大的树的高度为n，有n层；它有1个叶结点，n-1个分支结点。例题讲解2、试分别找出满足以下条件的所有二叉树：(1) 二叉树的前序序列与中序序列相同;(2) 二叉树的中序序列与后序序列相同;(3) 二叉树的前序序列与后序序列
2、相同。 【解答】 (1) 二叉树的前序序列与中序序列相同：空树或缺左子树的单支树； (2) 二叉树的中序序列与后序序列相同：空树或缺右子树的单支树； (3) 二叉树的前序序列与后序序列相同：空树或只有根结点的二叉树。例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结 点？至多有多少个结点？k与结点数目n之间的关系是什么？ 【分析】由完全二叉树的定义可知，对于k层的完全二叉树，其上 的k-1层是一棵深度为k-1的满二叉树。所以对于所有深度为k 的完全二叉树，它们之间的结点数目之差等于各树最后一层的 结点数目之差。例题讲解3、深度为k（根的层次为1）的完全二叉树至少有多少个结 点？至多
3、有多少个结点？k与结点数目n之间的关系是什么？【解答】深度为k的完全二叉树，其最少的结点数=深度为k-1的满二 叉树的结点数+1= ；其最多的结点数=深度为k的满 二叉树的结点数= 。k与结点数目n之间的关系可以根据二叉树的性质4得出：例题讲解4、对于深度为h，且只有度为0或2的结点的二叉树，结点数至少有多少？至多有多少？(分析) 【分析】对于结点数至多为多少的问题比较好回答，我们知道满 二叉树中只有度为0或2的结点，所以结点数至多为同等深度 的满二叉树的结点数。对于结点数至少为多少的问题，由于树中只存在度为0 或2的结点，即对一个结点而言，要么它没有子结点，要么 就有两个子结点，所以在这样的
4、树中，除第一层（根所在的 层）外，每一层至少有两个结点。例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG ，后序序列为DECBHGFA ，求对应的二叉树。(分析)【分析】 根据各种遍历方法的定义，可知：二叉树先序序列=根+左子树先序序列+右子树先序列；二叉树中序序列=左子树中序序列+根+右子树中序列；二叉树后序序列=左子树后序序列+右子树后序序列根；例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG ，后序序列为DECBHGFA ，求对应的二叉树。(分析) 【分析】 从先序和后序序列中可以很容易的知道那一个结点是根 ，而在中序序列中，可以根据根得到左、右子树的中序 序列，相应的也就知
5、道左、右子树的结点集合了。可以 根据集合中的结点划分先序或后序序列中除根以外的结 点序列，从而得到左、右子树的先序或后序序列。依次 类推，便可以递归得到整棵二叉树。中序序列左子树中序序列 根 右子树中序序列前序序列根 左子树前序序列 右子树前序序列例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG ，后序序列为DECBHGFA ，求对应的二叉树。(分析) 【解答】 构造这棵二叉树的过程如下所示： 中序序列：BDCE A FHG 后序序列：DECB HGF A中序：BDCE 后序：DECB 中序： FHG 后序： HGF 中序： D C E 后序：D E C 中序： HG 后序： HG 中序
6、：D 后序：D 中序：E 后序：E 中序：H 后序：H AFGHEDCB可以画出这棵二叉树为：例题讲解例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG 。该二叉树根的右子树的根是 （ ）A）E B）F C）G D）H【答案】 1、C 2、B 3、D2、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序列为BDCAFGE。该二叉树结点的前序序列为 （ ） A）EGFACDB B）EACBDGF C）EAGCFBD D）EGACDFB 3、如果一棵二叉树结点的前序序列是ABC，后序序列是CBA ， 则该二叉树 结点的对称序序列 A) 必为ABC B
7、) 必为ACB C) 必为BCA 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）错误
8、 例题讲解（2）错误 （3）错误7、在二叉树结点的先序序列、中序序列和后序序列中，所有 叶子结点的先后顺序 A）都不相同 B）先序和中序相同，而与后序不同 C）完全相同 D）中序和后序相同，而与先序不同8、在完全二叉树中，若一个结点只有一个子结点，则它没 A）左子结点 B）左子结点和右子结点 C）右子结点 D）左子结点、右子结点和兄弟结点 9、在下列存储形式中，哪一个不是树的存储形式 A）双亲表示法 B）孩子链表表示法 B）孩子兄弟表示法 D）顺序存储表示法 【答案】课堂练习7、C8、C9、D10、在树中，一个结点的直接子结点的个数称为该结点的_ 。11、如果对于给定的一组权值，所构造出的二叉
9、树的带权路径长度最小，则该树称为_ 。12、用数组A1n顺序存储完全二叉树的各结点,则当i=(n- 1)/2时, 结点Ai的右孩子是 结点_。13、完全二叉树中某结点无左子树，则它必是_。 课堂练习度哈夫曼树(Huffman)A2i+1叶子14、对于如图所示的森林（1）将其转换为相应的二叉树；（2）写出该森林的先序遍历序列和中序遍历序列。A图题 14BCEFDGHIJKL课堂练习【答案】ABCEFDGHIJKLABCEFDGHIJKL先序序列为：ABDEFCGHIJKL中序序列为：DEFBCAHIJGLK 课堂练习15、已知一棵树的先根遍历序列为ABCED，后根遍历序列 为BECDA，求对应的
10、树。 (分析)【分析】根据树与二叉树之间的转换关系，可知：树的先序序列 = 对应二叉树先序序列树的后跟序列 = 对应二叉树中序序列因此，可以先这两个序列构造对应的二叉树，再将二叉树转换为树。课堂练习15、已知一棵树的先根遍历序列为ABCED，后根遍历序列 为BECDA，求对应的树。 (分析)【答案】ABCDEABCDE课堂练习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 【分析】A B C D E 9 27 3 5 11 89 27 11 8 1727 11 17 2827 28 55 【答案】 C55273511281789课堂练习作业：6.26作业
