数据结构-树习题课

《数据结构-树习题课》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、习题课—树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)二叉树

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后序序列：DECBHGF[A]中序：[B]DCE后序：DEC[B]

6、中序：[F]HG后序：HG[F]中序：D[C]E后序：DE[C]中序：H[G]后序：H[G]中序：[D]后序：[D]中序：[E]后序：[E]中序：[H]后序：[H]AFGHEDCB可以画出这棵二叉树为：例题讲解例题讲解1、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）A）EB）FC）GD）H【答案】1、C2、B3、D2、某二叉树结点的对称序（中序）序列为ABCDEFG，后序序列为BDCAFGE。该二叉树结点的前序序列为（）A）EGFACDBB）EACBDGFC）EAGCFBDD）EGAC

7、DFB3、如果一棵二叉树结点的前序序列是ABC，后序序列是CBA，则该二叉树结点的对称序序列A)必为ABCB)必为ACBC)必为BCAD)不能确定6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【解答】具有3个结点的树有两种形态，如图1所示；而具有3个结点的二叉树有5种形态，如图2所示。图1图2具有3个结点的二叉树的5种形态例题讲解6、分别画出具有3个结点的树和具有3个结点的二叉树的所有不同形态。并判断下列论述

8、是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序