数据结构牛小飞6树习题课

例题讲解1、在节点个数为n(n1)的各棵树中，（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=；其最多的节点数=深度为k的满二叉树的节点数=。k与节点数目n之间的关系可以根据二叉树的性质4得出：112112kk12knk2log1例题讲解4、对于深度为h，且只有度为0或2的节点的二叉树，节点数至少有多少？至多有多少？(分析)【分析】对于节点数至多为多少的问题比较好回答，我们知道满二叉树中只有度为0或2的节点，所以节点数至多为同等深度的满二叉树的节点数。对于节点数至少为多少的问题，由于树中只存在度为0或2的节点，即对一个节点而言，要么它没有子节点，要么就有两个子节点，所以在这样的树中，除第一层（根所在的层）外，每一层至少有两个节点。例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】根据各种遍历方法的定义，可知：二叉树先序序列=根+左子树先序序列+右子树先序列；二叉树中序序列=左子树中序序列+根+右子树中序列；二叉树后序序列=左子树后序序列+右子树后序序列根；例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【分析】从先序和后序序列中可以很容易的知道那一个节点是根，而在中序序列中，可以根据根得到左、右子树的中序序列，相应的也就知道左、右子树的节点集合了。可以根据集合中的节点划分先序或后序序列中除根以外的节点序列，从而得到左、右子树的先序或后序序列。依次类推，便可以递归得到整棵二叉树。中序序列左子树中序序列根右子树中序序列前序序列根左子树前序序列右子树前序序列例题讲解5、已知一棵二叉树的中序序列为BDCEAFHG，后序序列为DECBHGFA，求对应的二叉树。(分析)【解答】构造这棵二叉树的过程如下所示：中序序列：BDCE[A]FHG后序序列：DECBHGF[A]中序：[B]DCE后序：DEC[B]中序：[F]HG后序：HG[F]中序：D[C]E后序：DE[C]中序：H[G]后序：H[G]中序：[D]后序：[D]中序：[E]后序：[E]中序：[H]后序：[H]AFGHEDCB可以画出这棵二叉树为：例题讲解例题讲解6、二叉树的先序遍历和中序遍历为：先序遍历：EFHIGJK；中序遍历：HFIEJKG。该二叉树根的右子树的根是（）A）EB）FC）GD）H【答案】1、C2、B3、D7、某二叉树节点的对称序（中序）序列为ABCDEFG，后序序列为BDCAFGE。该二叉树节点的前序序列为（）A）EGFACDBB）EACBDGFC）EAGCFBDD）EGACDFB8、如果一棵二叉树节点的前序序列是ABC，后序序列是CBA，则该二叉树节点的对称序序列A)必为ABCB)必为ACBC)必为BCAD)不能确定9、分别画出具有3个节点的树和具有3个节点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【解答】具有3个节点的树有两种形态，如图1所示；而具有3个节点的二叉树有5种形态，如图2所示。图1图2具有3个节点的二叉树的5种形态例题讲解9、分别画出具有3个节点的树和具有3个节点的二叉树的所有不同形态。并判断下列论述是否正确，为什么？（1）二叉树是一种特殊的树；（2）度为2的树是一棵二叉树；（3）度为2的有序树是一棵二叉树。【答案】（1）错误例题讲解（2）错误（3）错误尽管树和二叉树的概念之间有许多的类似，但它们是两个不同的数据结构。因为从定义来看，二叉树既不是只有两个子树的树，也不是最多只有两个子树的树.树和二叉树最主要的区别是：二叉树中结点的子树要区分左子树和右字树，即使在结点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树.不是，只能所示一种分类而已树有且只有一个根结点，而二叉树可以为空。11、在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序A）都不相同B）先序和中序相同，而与后序不同C）完全相同D）中序和后序相同，而与先序不同12、在完全二叉树中，若一个节点只有一个子节点，则它没A）左子节点B）左子节点和右子节点C）右子节点D）左子节点、右子节点和兄弟节点13、在下列存储形式中，哪一个不是树的存储形式A）双亲表示法B）孩子链表表示法B）孩子兄弟表示法D）顺序存储表示法【答案】11、C12、C13、D例题讲解14、在树中，一个节点的直接子节点的个数称为该节点的_____。15、如果对于给定的一组权值，所构造出的二叉树的带权路径长度最小，则该树称为_____________________。16、用数组A[1..n]顺序存储完全二叉树的各节点,则当i=(n-1)/2时,节点A[i]的右孩子是节点______________。17、完全二叉树中某节点无左子树，则它必是___________。度哈夫曼树(Huffman)A[2i+1]叶子例题讲解18、对于如图所示的森林（1）将其转换为相应的二叉树；（2）写出该森林的先序遍历序列和中序遍历序列。A18题图BCEFDGHIJKL例题讲解【答案】ABCEFDGHIJKLABCEFDGHIJKL先序序列为：ABDEFCGHIJKL例题讲解中序序列为：DEFBCAHIJGLK19、已知一棵树的先根遍历序列为ABCED，后根遍历序列为BECDA，求对应的树。(分析)【分析】根据树与二叉树之间的转换关系，可知：树的先序序列=对应二叉树先序序列树的后跟序列=对应二叉树中序序列因此，可以先这两个序列构造对应的二叉树，再将二叉树转换为树。例题讲解19、已知一棵树的先根遍历序列为ABCED，后根遍历序列为BECDA，求对应的树。(分析)【答案】ABCDEABCDE例题讲解20、设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别9、27、3、5、和11。按哈夫曼编码，则C的编码为:(分析)A、10B、110C、1110D、1111【分析】先构造哈夫曼树，再根据哈夫曼树进行编码。例题讲解【分析】ABCDE927351189271181727111728272855【答案】C55273511281789例题讲解20、设电文中出现的字母为A、B、C、D和E，每个字母在电文中出现的次数分别9、27、3、5、和11。按哈夫曼编码，则C的编码为:(分析)A、10B、110C、1110D、1111