1、树与二叉树模拟试卷 3 及答案与解析一、单项选择题1 已知一算术表达式的中缀形式为 A+B*C-DE，后缀形式为 ABC*+DE-，其前缀形式为( ) 。（A）一 A+B*CDE（B） -A+B*CDE（C） -+*ABCDE（D）-+A*BC DE2 设树 T 的度为 4，其中度为 1、2、3 和 4 的结点个数分别为 4、2、1、1，则树T 中的叶子数为( )。（A）5（B） 6（C） 7（D）8-3 在下述结论中，正确的是( )。 只有一个结点的二叉树的度为 0； 二叉树的度为 2；二叉树的左右子树可任意交换；深度为 K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。（A）（B）
2、（C） （D）4 设森林 F 对应的二叉树为 B，它有 m 个结点，二叉树 B 的根为 p，p 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是 ( )。（A）m-n（B） m-n-1（C） n+1（D）无法确定-5 若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 O 的结点个数是( )。 （A）9（B） 11（C） 15（D）不确定6 在一棵三叉树中度为 3 的结点数为 2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0 的结点数为( )个。（A）4（B） 5（C） 6（D）77 设森林 F 中有 3 棵树，第一、第二、第三棵树
3、的结点个数分别为 M1，M 2 和M3。与森林 F 对应的二叉树根结点的右子树上的结点个数是( )。（A）M 1（B） M1+M2（C） M3（D）M 2+M38 一棵完全二叉树上有 1001 个结点，其中叶子结点的个数是( )。（A）250（B） 500（C） 254（D）5019 设给定权值总数有 n 个，其哈夫曼树的结点总数为( )。（A）不确定（B） 2n（C） 2n+l（D）2n-110 若度为 m 的哈夫曼树中，其叶结点个数为 n，则非叶结点的个数为 ( )。（A）n-1（B） nm 一 1（C） (n 一 1)(m 一 1)（D）(n+1)(m+1) 一 l11 一个具有 1 0
4、25 个结点的二叉树的高度 h 为( )。（A）1 1（B） 10（C） 111025（D）10102412 一棵二叉树高度为 h，所有结点的高度或为 0，或为 2，则这棵二叉树最少有( )结点。（A）2h（B） 2h-一 1（C） 2h+l（D）h+l13 对于有 n 个结点的二叉树，其高度为( )。（A）nlog 2n（B） 10g2n（C） 10g2n+l（D）不确定14 若二叉树采用二叉链表存储结构，要交换其所有分支结点左、右子树的位置，利用( )遍历方法最合适。（A）前序（B）中序（C） 后序（D）按层次15 一棵二叉树的前序遍历序列为 ABCDEFG，它的中序遍历序列可能是( )。
5、（A）CABDEFG（B） ABCDEFG（C） DACEFBG（D）ADCFEG16 某二叉树中序序列为 ABCDEFG，后序序列为 BDCAFGE，则前序序列是( )。（A）EGFACDB（B） EACBDGF（C） EAGCFBD（D）上面的都不对17 某二叉树中序序列为 ABCDEFG，后序序列为 BDCAFGE，该二叉树对应的森林包括多少棵树( ) 。（A）1（B） 2（C） 3（D）概念上是错误的18 一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足( )。（A）所有的结点均无左孩子（B）所有的结点均无右孩子（C）只有一个叶子结点（D）是任意一棵二叉树19
6、在二叉树结点的先序序列，中序序列和后序序列中，所有叶子结点的先后顺序( )。（A）都不相同（B）完全相同（C）先序和中序相同，而与后序不同（D）中序和后序相同，而与先序不同20 某二叉树的前序序列和后序序列正好相反，则该二叉树一定是( )的二叉树。（A）空或只有一个结点（B）任一结点无左子树（C）高度等于其结点数（D）任一结点无右子树21 一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是( )。（A）不确定（B） 0（C） 1（D）222 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是( )。（A）0（B） 1（C） 2（D）不确定23 ( )的遍历仍需要栈的支持。（
7、A）前序线索树（B）中序线索树（C）后序线索树（D）以上都不是24 n 个结点的线索二叉树上含有的线索数为( )。（A）2n（B） n-1（C） n+1（D）n25 下面几个符号串编码集合中，不是前缀编码的是( )。（A）0 ，10 ，110，1111（B） 11，10，001，101，0001（C） 00，010，0110，1000（D）b ，C，aa，aC，aba，abb，abC二、综合题26 从概念上讲，树、森林和二叉树是 3 种不同的数据结构，说明将树、森林转化为二叉树的基本目的是什么，并指出树和二叉树的主要区别。27 一棵高度为 h 的满尼叉树有如下性质：根据结点所在层次为 0；第
8、h 层上的结点都是叶子结点；其余各层上每个结点都有 k 棵非空子树，如果按层次自顶向下，同一层自左向右，顺序从 1 开始对全部结点进行编号，试问：(1)各层的结点个数是多少?(2)编号为 i 的结点的双亲结点 (若存在) 的编号是多少?(3)编号为 i 的结点的第 m 个孩子结点(若存在) 的编号是多少 ?(4)编号为 i 的结点有右兄弟的条件是什么 ?其右兄弟结点的编号是多少 ?28 证明任一结点个数为 n 的二叉树的高度至少为 O(log2n)。29 已知一棵满二叉树的结点个数为 2040 的素数，此二叉树的叶子结点有多少个?30 一棵共有 n 个结点的树，其中所有分支结点的度均为 K，求
9、该树中叶子结点的个数。31 若一棵树中有度数为 1m 的各种结点数为 n1， n2，n m(nm 表示度数为 m 的结点个数)，请推导出该树中共有多少个叶子结点 n0 的公式。32 高度为 k 的完全二叉树至少有多少个叶结点?33 试证明，在具有 n(n1)个结点的 m 次树中，有 n(m 一 1)+1 个指针是空的。34 对于任何一棵非空的二叉树，假设叶子结点的个数为 n0，而次数为 2 的结点个数为 n2，请给出 n0 和 n2 之间所满足的关系式 n0=f(n2)。要求给出推导过程。35 试求有 n 个叶结点的非满的完全二叉树的高度。36 对于一个堆栈，若其入栈序列为 1，2，3，n，不
10、同的出入栈操作将产生不同的出栈序列。其出栈序列的个数正好等于结点个数为 n 的二叉树的个数，且与不同形态的二叉树一一对应。请简要叙述一种从堆栈输入(固定为 1，2，3，n)输出序列对应一种二叉树形态的方法，并以人栈序列 1，2，3(即 n=3)为例加以说明。37 如果给出了一个二叉树结点的前序序列和对称序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。如果给出了一个二叉树结点的前序序列和后序序列，能否构造出此二叉树?若能，请证明之。若不能，请给出反例。38 用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL。请写出后序遍历该二叉树的访问结点序列。39 已知一棵二叉树的先序、
11、中序和后序序列如下，其中有部分空缺，请画出该二叉树。先序序列：_B C_ E F G_ I J K_中序序列：C B E D _G A J _H _L后序序列：_E _F D _J _L _H A40 对于二叉树 T 的两个结点 n1 和 n2，我们应该选择树 T 结点的前序、中序和后序中哪两个序列来判断结点 n1 必定是结点 n2 的祖先?试给出判断的方法。(不需证明判断方法的正确性)41 什么是前缀编码? 举例说明如何利用二叉树来设计二进制的前缀编码。42 如果一棵哈夫曼树 T 有 n0 个叶子结点，那么，树 T 有多少个结点?(要求给出求解过程)43 已知字符及其权值如下：A(6)，B(
12、7)，C(1) ，D(5) ，E(2)，F(8) ，给出构造哈夫曼树和哈夫曼编码的过程，并计算带权路径长度。44 要求二叉树按二叉链表形式存储，编写算法实现：(1)建立二叉树的算法。(2)判别给定的二叉树是否是完全二叉树的算法。(完全二叉树的定义为：深度为 K，具有 N 个结点的二叉树的每个结点都与深度为 K 的满二叉树中编号从 1N 的结点一一对应。此题以此定义为准)45 假设以双亲表示法作树的存储结构，写出双亲表示的类型说明，并编写求给定的树的深度的算法。(注：已知树中的结点数)46 二叉树采用二叉链表存储：(1)编写计算整个二叉树高度的算法(二叉树的高度也叫二叉树的深度)。(2)编写计算
13、二叉树最大宽度的算法(二叉树的最大宽度是指二叉树所有层中结点个数的最大值)。47 已知一棵二叉树按顺序方式存储在数组 An中。设计算法，求出下标分别为 i和 j 的两个结点的最近的公共祖先结点的值。48 在二叉树中查找值为 x 的结点，试编写算法(用 C 语言)打印值为 x 的结点的所有祖先，假设值为 x 的结点不多于一个，最后试分析该算法的时间复杂度。树与二叉树模拟试卷 3 答案与解析一、单项选择题1 【正确答案】 D【试题解析】 此题考查的知识点是树的应用及遍历。用树表示表达式，前缀是前序遍历，中缀是中序遍历，后缀是后序遍历，本题就是已知中序遍历和后序遍历，求前序遍历的问题。按规则后缀最后
14、一个元素“一”是树的根结点，在中缀中“一”的左边(A+BC)为左子树，右边(DE)为右子树，据此再查后缀的倒数第二个元素“”，其为右子树的根，再到中缀中“”左 D 是左子树，右 E 是右子树，以此类推即可构造出该树，前序遍历序列即为所求。所以选择 D。【知识模块】 树与二叉树2 【正确答案】 D【试题解析】 此题考查的知识点是树的结点个数与分支数的关系。设 B 为分支数，N 为结点总数，则 B=N 一1，N=n 0+n1+n2+n3+n4，n 1+n2+n3+n4=8，B=41+22+31+41=15，所以 n0=8，应选 D。【知识模块】 树与二叉树3 【正确答案】 D【试题解析】 此题考查
15、的知识点是二叉树的定义与性质。在二叉树中没有分支的结点度数为 0，二叉树最大度数为 2，左右子树不可以任意交换，完全二叉树与满二叉树的区别就是完全二叉树最后一层结点不满，且若有一个结点应是左子树，所以应选 D。【知识模块】 树与二叉树4 【正确答案】 A【试题解析】 此题考查的知识点是二叉树与森林的转换。根据转换规则，森林中的第一棵树为二叉树的左子树，其余为右子树，所以应选 A。【知识模块】 树与二叉树5 【正确答案】 B【试题解析】 此题考查的知识点是二叉树的性质。n 0=n2+1，n 0=10+1=11，所以选B。【知识模块】 树与二叉树6 【正确答案】 C【试题解析】 此题考查的知识点是
16、树的结点个数与分支数的关系。设 B 为分支数，N 为结点总数，则 B=N 一 1，N=n 0+n1+n2+n3，已知n3+n2+n1=2+1+2=5，B=32+21+12=10，所以 n0=115=6，应选 C。【知识模块】 树与二叉树7 【正确答案】 D【试题解析】 此题考查的知识点是二叉树与森林的转换。根据转换规则，森林中的第一棵树为二叉树的左子树，其余为右子树，所以应选 D。【知识模块】 树与二叉树8 【正确答案】 D【试题解析】 由二叉树结点的公式：n=n 0+n1+n2=n0+n1+(n01)=2n0+n1=1，因为n=100l，所以 1002=2n0+n1，在完全二叉树树中，n 1
17、 只能取 0 或 1，在本题中只能取 0，故 n=501，因此选 D。【知识模块】 树与二叉树9 【正确答案】 D【试题解析】 此题考查的知识点是哈夫曼树的定义。没有特殊说明表示该树只有高度为 0 和 2 的结点，且满足 n0=n2+1，总数=n 0+n2，给定的权值个数 n 即为叶结点数，所以应选 D。【知识模块】 树与二叉树10 【正确答案】 C【试题解析】 此题考查的知识点是哈夫曼树的定义。哈夫曼树都是 m 叉正则树。可以这样计算：设分支节点数为 i，则总结点数=ixm+1(im 没有带根结点，所以加 1)又总结点数=i+n 两式相减就能得到 i=(n 一 1)(m 一 1)。应选 C。
18、【知识模块】 树与二叉树11 【正确答案】 C【试题解析】 此题考查的知识点是二叉树的性质。根据题意二叉树最高是单链树，高度为 1025，最矮为 h=logn+1，n=1025 ，h=11，应选 C。【知识模块】 树与二叉树12 【正确答案】 B【试题解析】 此题考查的知识点是二叉树的结点个数与高度的关系。根据题意当h=1 时，一个结点，h=2 时，最少 3 个，h=3 时，最少 5 个，最少结点为 2h一 1，应选 B。【知识模块】 树与二叉树13 【正确答案】 D【试题解析】 此题考查的知识点是二叉树的性质。根据题意二叉树最高是单链树，高度为 n，最矮为 h=1+log2n，所以不确定，应
19、选 D。【知识模块】 树与二叉树14 【正确答案】 C【试题解析】 此题考查的知识点是对四种遍历算法的理解。前序遍历是“根左右”；后序遍历是“左右根”；中序遍历是“左根右”；层序遍历是“从上到下从左到右”。后序遍历符合题意，所以选 C。【知识模块】 树与二叉树15 【正确答案】 B【试题解析】 此题考查的知识点是对前序遍历、中序遍历算法的理解。据题意，根为 A、B 或为左子树，或为右子树，中序遍历的序列前两个字符要么 AB，要么BA，所以选项 A、C、D 均错。应选选项 B，即为右单链树。【知识模块】 树与二叉树16 【正确答案】 B【知识模块】 树与二叉树17 【正确答案】 B【知识模块】
20、树与二叉树18 【正确答案】 C【试题解析】 此题考查的知识点是对后序遍历、前序遍历算法的理解。前序序列是“根左右”，后序序列是“左右根”，若要这两个序列相反，只有单支树，所以本题的选项 A 和选项 B 均对，单支树的特点是只有一个叶子结点，故选项 C 是最合适的，故选 C。选项 A 或选项 B 都不全。【知识模块】 树与二叉树19 【正确答案】 B【试题解析】 此题考查的知识点是对二叉树遍历算法的理解。前序序列是“根左右”，后序序列是“左右根”，中序序列是“左根右”，所以叶结点顺序不变，应选B。【知识模块】 树与二叉树20 【正确答案】 C【知识模块】 树与二叉树21 【正确答案】 D【试题
21、解析】 此题考查的知识点是线索二叉树的定义。根据二叉树线索化的概念，其先序序列中的第一个为根结点，最后一个结点为其最右下的叶结点。左子树为空的二叉树的根结点的左线索为空(无前驱)，先序序列的最后结点的右线索为空(无后继)，共 2 个空链域，应选 D。【知识模块】 树与二叉树22 【正确答案】 B【试题解析】 此题考查的知识点是线索二叉树的定义。根据二叉树线索化的概念，其先序序列中的第一个为根结点，最后一个结点为其最右下的叶结点。因为其左、右子树都不为空，所以该结点无空指针域；而对最后一个结点，该节点为叶子结点，即左、右子树都为空，那么该结点在先序序列中必然有一个前驱，因此该结点就只有一个空指针
22、域。共 1 个空链域，应选 B。【知识模块】 树与二叉树23 【正确答案】 C【试题解析】 后序线索二叉树仍需要栈的支持。因后序遍历先访问子树，后访问根，本质上要求运行栈中存放祖先信息，故即使对二叉树进行了后序线索化，仍然不能脱离栈的支持独立遍历。而前序线索和中序线索不用。所以应选 C。【知识模块】 树与二叉树24 【正确答案】 C【试题解析】 此题考查的知识点是线索二叉树的定义。根据二叉树线索化的概念，只有空链才是线索，n 个结点有 n 一 1 个实链，2n 个链，空链数为 n+1，所以有n+1 个线索。应选 C。【知识模块】 树与二叉树25 【正确答案】 B【试题解析】 此题考查的知识点是
23、前缀编码的定义。前缀编码就是任一字符的编码不能是另一字符编码的前缀，选项 B 中 10 是 101 的前缀。应选 B。【知识模块】 树与二叉树二、综合题26 【正确答案】 树的孩子兄弟链表表示法和二叉树二叉链表表示法，本质是一样的，只是解释不同，也就是说树(树是森林的特例，即森林中只有一棵树的特殊情况)可用二叉树唯一表示，并可使用二叉树的一些算法去解决树和森林中的问题。树和二叉树的区别有三：一是二叉树的度至多为 2，树无此限制；二是二叉树有左右子树之分，即使在只有一个分支的情况下，也必须指出是左子树还是右子树，树无此限制；三是二叉树允许为空，树一般不允许为空(个别书上允许为空)。【试题解析】
24、此问题考查的知识点是树、二叉树的定义及区别。【知识模块】 树与二叉树27 【正确答案】 (1)k 1(1 为层数，按题意，根结点为 0 层)。 (2)因为该树每层上均有 k1 个结点，从根开始编号为 1，则结点 i 的从右向左数第 2 个孩子的结点编号为ki。设 n 为结点 i 的子女，则关系式(i 一 1)k+2nik+1 成立，因 i 是整数，故结点i 的双亲的编号为(i 一 2)k+1 。 (3)结点 i(i1)的前一结点编号为 i 一 1(其最右边子女编号是(i 一 1)k+1)，故结点 i 的第 m 个孩子的编号是(i 一 1)k+1+m。 (4)根据以上分析，结点 i 有右兄弟的条
25、件是，它不是双亲的从右数的第一个子女，即 (i一 1) k!=0，其右兄弟编号是 i+1。【知识模块】 树与二叉树28 【正确答案】 设 n 个结点的二叉树的最低高度是 h，则 n 应满足 2h-1n2h-1 关系式。解此不等式，并考虑 h 是整数，则有 h=log2n+l，即任一结点个数为 n 的二叉树的高度至少为 O(log2n)。【试题解析】 此问题考查的知识点是二叉树的性质。最低高度二叉树的特点是，除最下层结点个数不满外，其余各层的结点数都应达到各层的最大值。【知识模块】 树与二叉树29 【正确答案】 其叶子数是 16。【试题解析】 此问题考查的知识点是满二叉树的性质。结点个数在 20
26、40 的满二叉树且结点数是素数的数是 31，即满二叉树结点数为 31，根据其性质知n0+n2=31，n 0=n2+1，n 0=16。【知识模块】 树与二叉树30 【正确答案】 树中叶子结点的个数为 n0=n 一 nk=(n(K 一 1)+1)K。【试题解析】 此问题考查的知识点是 K 叉树的性质。设分支结点和叶子结点数分别是为 nk 和 n0，因此有 n=n 0+nk (1) 另外，从树的分支数 B 与结点的关系有 n=B+1=Knk+1 (2) 由式(1)和式(2)有 n0=nnk=(n(K 一 1)+1)K【知识模块】 树与二叉树31 【正确答案】 结点数 n0=1+n2+2n3+(m 一
27、 1)nm【试题解析】 此问题考查的知识点是树的度数与叶结点的关系。利用二叉树的性质，推广到树。 设树的结点数为 n，分支数为 B，则下面二式成立 n=n0+n1+n2+nm (1) n=B+1=n1+2n2+nnm (2) 由式(1)和式(2)得叶子结点数n0=1+n2+2n3+(m 一 1)nm【知识模块】 树与二叉树32 【正确答案】 叶结点的个数是即 2k-2 个。【试题解析】 此问题考查的知识点是完全二叉树的性质。当高度为 k 的完全二叉树的第 k 层只有一个结点时，结点数达到最少，这也是高度为 k 的完全二叉树具有的最少叶结点数，所以，第 k 一 1 层有 2k-2 一 1 个叶结
28、点，第 k 层只有一个叶结点，所以总的叶结点的个数是即 2k-2 个。【知识模块】 树与二叉树33 【正确答案】 n 个结点的 m 次树，共有 nm 个指针。除根结点外，其余 n 一1 个结点均有指针所指，故空指针数为 nm 一(n 一 1)=n(m1)+1。证毕。【知识模块】 树与二叉树34 【正确答案】 设度为 1 和 2 及叶子结点数分别为 n0、n 1 和 n2，则二叉树结点数n 为 n=n 0+n1+n2 (1) 再看二叉树的分支数，除根结点外，其余结点都有一个分支进入，设 B 为分支总数，则 n=B+1。度为 1 和 2 的结点各有 1 个和 2 个分支，度为0 的结点没有分支，故
29、 n=n 1+2n2+1 (2) 由式(1) 和式(2)，得 n0=n2+1。【知识模块】 树与二叉树35 【正确答案】 n 个叶结点的非满的完全二叉树的高度是log 2n+1。(最下层结点数2)。【试题解析】 此问题考查的知识点是完全二叉树的性质。设完全二叉树中叶子结点数为 n，则根据完全二叉树的性质，度为 2 的结点数是 n 一 1，而完全二叉树中，度为 1 的结点数至多为 1，所以具有 n 个叶子结点的完全二叉树结点数是 n+(n 一1)+1=2n 或 2n 一 1(有或无度为 1 的结点) 。由于具有 2n(或 2n 一 1)个结点的完全二叉树的深度是log 2(2n)+1(或log
30、2(2n 一 1)+l，即log 2n+1)，故 n 个叶结点的非满的完全二叉树的高度是log 2n+l。(最下层结点数2)。【知识模块】 树与二叉树36 【正确答案】 由于二叉树前序遍历序列和中序遍历序列可唯一确定一棵二叉树，因此，若人栈序列为 1，2，3，n，相当于前序遍历序列是 1，2，3，n，出栈序列就是该前序遍历对应的二叉树的中序序列的数目。因为中序遍历的实质就是一个结点进栈和出栈的过程，二叉树的形态确定了结点进栈和出栈的顺序，也就确定了结点的中序序列。当结点入栈序列为1，2，3 时，出栈序列可能为：3，2， 1， 2，3，1， 2，1，3，1 ，3，2， 1，2，3。【知识模块】
31、树与二叉树37 【正确答案】 给定二叉树结点的前序序列和对称序(中序)序列，可以唯一确定该二叉树。因为前序序列的第一个元素是根结点，该元素将二叉树中序序列分成两部分，左边(设 l 个元素) 表示左子树，若左边无元素，则说明左子树为空；右边(设 r 个元素)是右子树，若为空，则右子树为空。根据前序遍历中“根一左子树一右子树”的顺序，则由从第二元素开始的 1 个结点序列和中序序列根左边的 l 个结点序列构造左子树，由前序序列最后 r 个元素序列与中序序列根右边的 r 个元素序列构造右子树。由二叉树的前序序列和后序序列不能唯一确定一棵二叉树，因无法确定左右子树两部分。例如，任何结点只有左子树的二叉树
32、和任何结点只有右子树的二叉树，其前序序列相同，后序序列相同，但却是两棵不同的二叉树。【知识模块】 树与二叉树38 【正确答案】 HIDJKEBLFGCA【试题解析】 此问题考查的知识点是二叉树的遍历。完全二叉树的数组存放形式可以按从左到右，从上到下画出该二叉树，对其进行后序遍历即可得到后序序列。【知识模块】 树与二叉树39 【正确答案】 前序序列：ABCDEFGHIJKL中序序列：CBEDFGAJIHKL后序序列：CEGFDBJILKHA【试题解析】 此问题考查的知识点是二叉树的遍历。由题意在后续序列中找到根结点为 A，在中序中知左子树的序列，在前序中知左子树的根为 B，以此不断重复推导可以得
33、到结论。【知识模块】 树与二叉树40 【正确答案】 采用前序和后序两个序列来判断二叉树上结点 n1 必定是结点 n2 的祖先。在前序序列中某结点的祖先都排在其前。若结点 n1 是 n2 的祖先，则 n1 必定在 n2 之前。而在后序序列中，某结点的祖先排在其后，即若结点 n1 是 n2 的祖先，则 n1 必在 n2 之后。根据这条规则来判断若结点 n1 在前序序列中在 n2 之前，在后序序列中又在 n2 之后，则它必是结点 n2 的祖先。【知识模块】 树与二叉树41 【正确答案】 前缀码是一编码，不是任何其他编码前缀的编码。例如，0 和 01就不是前缀码，因为编码 0 是编码 01 的前缀。仅
34、从编码来看，0 和 01 是前缀码，但因历史的原因，它不被称为前缀码，而是把一编码不是另一编码前缀的编码称为前缀码。利用二叉树可以构造前缀码，例如，以 A、B 、C、D 为叶子可构成二叉树，将左分支解释为 0，右分支解释成 1，从根结点到叶子结点的 0、1 串就是叶子的前缀码。用哈夫曼树可构造出最优二叉树，使编码长度最短。【知识模块】 树与二叉树42 【正确答案】 哈夫曼树只有度为 0 的叶子结点和度为 2 的分支结点，设数量分别为 n0 和 n2，则树的结点数 n=n0+n2。另根据二叉树性质：任意二叉树中度为 0 的结点数 n0 和度为 2 的结点数 n2 间的关系是 n2=n0 一 1，
35、代人上式，则 n=n0+n2=2n0一 1。【知识模块】 树与二叉树43 【正确答案】 假设有 n 个权值，则构造出的哈夫曼树有 n 个叶子结点。n 个权值分别设为 1， 2， 2，则哈夫曼树的构造规则为： (1)将 1， 2， n看成是有 n 棵树的森林(每棵树仅有一个结点)。如下图所示。(2)在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和。如下图所示。(3)从森林中删除选取的两棵树，并将新树加入森林。如下图所示。(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。如下图所示。【知识模块】 树与二
36、叉树44 【正确答案】 typedef struct BiNodeElemType data；BiNode*lchild：BiNode*rchild：*BiTree；BiTree Creat()建立二叉树的二叉链表形式的存储结构ElemType x；BiTree bt；scanf(“d” ，x) ；本题假定结点数据域为整型if(x=0)bt=null；else if(x0)bt=(BiNode*)malloc(sizeof(BiNode)；bt 一data=x ；bt 一1child=ereat() ；bt-rchild=creat()；else error(”输入错误”)；return(bt
37、)；结束 BiTreeint JudgeComplete(BiTree bt)判断二叉树是否是完全二叉树，如是，返回 1，否则，返回 0int tag=0；BiTree P=bt，Q ；Q 是队列，元素是二叉树结点指针，容量足够大if(P=null)return(1)；QueueInit(Q)；QueueIn(Q，P)；初始化队列，根结点指针入队while(!QueueEmpty(Q)P=QueueOut(Q)；出队if(p 一lchild!tag)QueueIn(Q，p-lchild) ；左子女人队elseif(p 一 lchild)return 0；前边已有结点为空，本结点不空 else
38、tag=1；首次出现结点为空if(p 一rchild&!tag)Queueln(Q ，p-rchild)；右子女人队else if(p-rchild)return 0；else tag=1； whilereturn 1；JudgeC0mplete【试题解析】 此问题考查的知识点是二叉树的建立算法。二叉树是递归定义的，以递归方式建立最简单。判定是否是完全二叉树，可以使用队列，在遍历中利用完全二叉树“若某结点无左子女就不应有右子女”的原则进行判断。完全二叉树证明还有很多方法。判断时易犯的错误是证明其左子树和右子数都是完全二叉树，由此推出整棵二叉树必是完全二叉树的错误结论。【知识模块】 树与二叉树4
39、5 【正确答案】 int Depth(Ptree t)求以双亲表示法为存储结构的树的深度int maxdepth=0；for(i=1；i0)temp+；f=t nodesf parent； 深度加 1，并取新的双亲if(tempmaxdepth)maxdepth=temp；最大深度更新return(maxdepth)；返回树的深度结束 Depth【试题解析】 此问题考查的知识点是树的不同形式的存储结构，求树的高度。由于以双亲表示法作树的存储结构，找结点的双亲容易。因此我们可求出每一结点的层次，取其最大层次就是树有深度。对每一结点，找其双亲，双亲的双亲，直至(根)结点双亲为 0 为止。【知识模块
40、】 树与二叉树46 【正确答案】 二叉树高度可递归计算如下：若二叉树为空，则高度为 0，否则，二叉树的高度等于左右子树高度的大者加 1。这里二叉树为空的标记不是 null 而是0。设根结点层号为 1，则每个结点的层号等于其双亲层号加 1。二叉树的存储结构定义如下：typedefstruct nodeint L；编号为 i 的结点的左儿子int R；编号为 i 的结点的右儿子int D；编号为 i 的结点的层号int i；存储结点的顺序号(下标)tnode；(1)int Height(tnode t，int i)求二叉树高度，调用时 i=1int lh，rh；if(i=0)return(0)；e
41、lse1h=Height(t，tLi)；rh=Height(t，tRi)；if(1hrh)return(1h+1)；else return(rh+1) ；结束 Height求最大宽度可采用层次遍历的方法，记下各层结点数，每层遍历完毕，若结点数大于原先最大宽度，则修改最大宽度。(2)int Width(BiTree bt)求二叉树 bt 的最大宽度if(bt=null)return(0)；空二叉树宽度为 0elseBiTree Q；Q 是队列，元素为二叉树结点指针，容量足够大front=1；rear=1 ；last=1 ；front 队头指针，rear 队尾指针，last 同层最右结点在队列中的
42、位置temp=0；maxw=0；temp 记局部宽度，maxw 记最大宽度Qrear=bt；根结点人队列while(frontlchild!=null)Q+rear=p 一lchild；左子女人队if(p-rchild!=null)Q+rear=p 一rchild；右子女人队if(frontlast)一层结束last=rear；if(tempmaxw)maxw=temp；last 指向下层最右元素，更新当前最大宽度temp=0； ifwhilereturn(maxw)；结束 width【知识模块】 树与二叉树47 【正确答案】 void Ancestor(ElemType A，int n，in
43、t i，int j)二叉树顺序存储在数组 An中，求下标分别为 i 和 j 的结点的最近公共祖先结点的值。while(i!=j)if(ij)i=i 2；下标为 i 的结点的双亲结点的下标else j=j2 ；下标为 J 的结点的双亲结点的下标printf(“所查结点的最近公共祖先的下标是d，值是d” ，i ，Ai)；设元素类型整型 Ancestor【试题解析】 此问题考查的知识点是二叉树顺序存储相应算法。该题是按完全二叉树的格式存储，利用完全二叉树双亲结点与子女结点编号间的关系，求下标为 i和 j 的两结点的双亲，双亲的双亲，等等，直至找到最近的公共祖先。【知识模块】 树与二叉树48 【正确答
44、案】 void Search(BiTree bt，ElemType x) 在二叉树 bt 中，查找值为 x 的结点，并打印其所有祖先 typedef structBiTree t； int tag； stack ；tag标志 stack S；栈容量足够大 top=0； while(bt!=null top0) while(bt!=null&bt-data!=X) S+topt=bt ；Stoptag=0；bt=bt-lchild；结点入栈，沿左分支向下 if(bt 一data=x)printf(”所查结点的所有祖先结点的值为：n”)；找到 x for(i=1；idata)；return；输出祖先值后结束 while(top!=0&Stoptag=1)top-；退栈(空遍历) if(top!=0)stoptag=1；bt=Stopt-rchild； 沿右分支向下遍历 while(bt!=null top0) 结束 Search 因为查找的过程就是后序遍历的过程，使用的栈的深度不超过树的深度，算法复杂度为 O(log2n)。【试题解析】 此问题考查的知识点是后序遍历的思想。后序遍历最后访问根结点，当访问到值为 x 的结点时，栈中所有元素均为该结点的祖先。【知识模块】 树与二叉树
