《数据结构-树习题课》由会员分享,可在线阅读,更多相关《数据结构-树习题课(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作业