先序和中序遍历序列还原树也不会操作。
2010 年
【2010年真题】 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
【解析】
- 后序遍历序列：访问顺序为“左子树 右子树 根结点”。遍历序列为：。
【答案】D
【2010年真题】第5题 在一棵度数为 的树 中，若有 个度为 的结点， 个度为 的结点， 个度为 的结点， 个度为 的结点，则树 的叶结点个数是（ ）。
408计算机考研数据结构树真题——选择题
更新于 2026-10-16
— 4292 字
先序和中序遍历序列还原树也不会操作。
【2010年真题】 下列线索二叉树中（用虚线表示线索），符合后序线索树定义的是（ ）。
【解析】
【答案】D
【2010年真题】第5题 在一棵度数为 的树 中，若有 个度为 的结点， 个度为 的结点， 个度为 的结点， 个度为 的结点，则树 的叶结点个数是（ ）。
【解析】
设树中度为 的结点数分别为 ，树中结点总数为 ，则树中各结点的度之和等于 ，即 根据题设中的数据，即可得到
【答案】B
【2010年真题】第6题 对 个权值均不相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（ ）。
【解析】
【答案】A
【2011年真题 第4题】若一棵完全二叉树有768个结点，则该二叉树中叶结点的个数是（ ）。
A. 257 B. 258 C. 384 D. 385
解析：
根据完全二叉树的性质，最后一个分支结点的序号为，故叶子结点的个数为 。
【另解 1】由二叉树的性质 和 可知，，，显然 ，，则 。
【另解 2】完全二叉树的叶子结点只可能出现在最下两层，由题可计算完全二叉树的高度为10。第 10 层的叶子结点数为 ；第 10 层的叶子结点在第 9 层共有个父结点，第 9 层的叶子结点数为，则叶子结点的总数为 。
第5题：
若一棵二叉树的前序遍历序列和后序遍历序列分别为1, 2, 3, 4和4, 3, 2, 1，则该二叉树的中序遍历序列不会是（ ）。
A. 1, 2, 3, 4 B. 2, 3, 4, 1
C. 3, 2, 4, 1 D. 4, 3, 2, 1
前序序列为 NLR，后序序列为 LRN，由于前序序列和后序序列刚好相反，故不可能存在一个结点同时存在左右孩子，即二叉树的高度为 4。1 为根结点，由于根结点只能有左孩子（或右孩子），因此，在中序序列中，1 或在序列首或在序列尾，ABCD 皆满足要求。仅考虑以 1 的孩子结点2 为根结点的子树，它也只能有左孩子（或右孩子），因此，在中序序列中，2 或在序列首或序列尾，ABD 皆满足要求。
第6题：
已知一棵有2011个结点的树，其叶结点个数为116，该树对应的二叉树中无右孩子的结点的个数是（ ）。
A. 115 B. 116 C. 1895 D. 1896
解析：树转换为二叉树时，树中每一个分支结点的所有子结点中的最右子结点无右孩子，根结点转换后也没有右孩子，因此，对应的二叉树中无右孩子的结点个数 = 分支结点数。通常本题应采用特殊法解，设题意中的树是如右图所示的结构，则对应的二叉树中仅有前 115 个叶结点有右孩子，故无右孩子的结点个数 。
【2012年真题3】若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点______。 A. 只有 e B. 有 e、b C. 有 e、c D. 无法确定
前序序列和后序序列不能唯一确定一棵二叉树，但可以确定二叉树中结点的祖先关系：当两个结点的前序序列为 XY 与后序序列为 YX 时，则 X 为 Y 的祖先。考虑前序序列 a, e, b, d, c、后序序列 b, c, d, e, a，可知 a 为根结点，e 为 a 的孩子结点。此外，a 的孩子结点的前序序列 e, b, d, c、后序序列 b, c, d, e，可知 e 是 bcd 的祖先，故根结点的孩子结点只有 e。故选 A。
【排除法】显然 a 为根结点，且确定 e 为 a 的孩子结点，排除 D。各种遍历算法中左右子树的遍历次序是固定的，若 b 也为 a 的孩子结点，则在前序序列和后序序列中 e、b 的相对次序应是不变的，故排除 B，同理排除 C。
【特殊法】前序序列和后序序列对应着多棵不同的二叉树树形，我们只需画出满足该条件的任一棵二叉树即可，任意一棵二叉树必定满足正确选项的要求。
【2013真题第4题】已知三叉树 T 中6个叶结点的权分别是 2, 3, 4, 5, 6, 7，T 的带权（外部）路径长度最小是____。
A.27 B.46 C.54 D.56
【2013真题第5题】 若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是____。
A.X 的父结点
B.以 Y 为根的子树的最左下结点
C.X 的左兄弟结点 Y
D.以 Y 为根的子树的最右下结点
答案：A
【2014年真题 第5题】 将森林F转换为对应的二叉树T，F中叶结点的个数等于____。
A. T中叶结点的个数
B. T中度为1的结点个数
C. T中左孩子指针为空的结点个数
D. T中右孩子指针为空的结点个数
【2014年真题 第6题】 5个字符有如下4种编码方案，不是前缀编码的是____。
A. 01, 0000, 0001, 001, 1
B. 011, 000, 001, 010, 1
C. 000, 001, 010, 011, 100
D. 0, 100, 110, 1110, 1100
先序序列为 a, b, c, d 的不同二叉树的个数是____。 A. 13 B. 14 C. 15 D. 16
下列选项给出的是从根分别到达两个叶结点路径上的权值序列，能属于同一棵哈夫曼树的是____。 A. 24, 10, 5 和 24, 10, 7 B. 24, 10, 5 和 24, 12, 7 C. 24, 10, 10 和 24, 14, 11 D. 24, 10, 5 和 24, 14, 6
现有一棵无重复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是____。 A. 根结点的度一定为 2 B. 树中最小元素一定是叶结点 C. 最后插入的元素一定是叶结点 D. 树中最大元素一定是无左子树
可以从字符出现频率入手，先统计每个字符出现次数，让高频字符用短编码。
路径长度 =>一个字符的编码长度
权值 => 字符出现次数
带权路径长度 => 每个字符的编码长度乘以出现字符出现次数（只乘叶子结点的权）
树的带权路径长度 => 所有叶子结点的带权路径长度之和，即字符串编码后的总比特数
以哈夫曼编码为线索，理解哈夫曼树中的 WPL 这个概念。哈夫曼编码的目标是使全文总比特数最少。这个编码后的全文总比特数，用哈夫曼树中的 WPL 来表示。首先，叶子结点对应待编码的各个字符，用权值表示字符出现的频次，用从根到叶子的边数（路径长度）表示该字符编码后的比特位数，则结点的带权路径长度就是该字符在全文中所占的总比特数。将所有叶子结点的带权路径长度相加，即为全文编码后的总比特数。而哈夫曼树的构造方法，保证了WPL最小，在哈夫曼编码这个应用场景中，就确保了编码后占用的存储空间最小。
（度数与结点数关系）一棵树共有 个结点，其中所有分支结点的度均为 ，则该树中的叶结点数为 。
树中的叶结点数为 ，则分支结点（非叶结点）数为 。树中所有结点的度数之和（即总分支数）为： ，又总分支数 （在任意一棵包含 个结点的树中，除根结点外，每个结点上方都有且仅有一条边与之对应），联立求解得：
更新于2026-11-04
更新于2026-11-04
