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