数据结构树真题

• 遍历子树 $b$：无左子树，先访问右子树 $d$，再访问 $b$，序列为 $d, b$；
• 访问右子树 $c$；
• 最后访问根结点 $a$。
  因此，后序遍历序列为：$d, b, c, a$。

对照各选项图形特征，符合 $d$ 的右线索指向 $b$、$b$ 的左线索指向 $d$、$c$ 的左线索指向 $b$、$c$ 的右线索指向 $a$ 的是 。

【答案】D

【2010年真题】第5题 在一棵度数为 $4$ 的树 $T$ 中，若有 $20$ 个度为 $4$ 的结点，$10$ 个度为 $3$ 的结点，$1$ 个度为 $2$ 的结点， 个度为 的结点，则树 的叶结点个数是（ ）。

• A. 41
• B. 82
• C. 113
• D. 122

【解析】

1. 设结点数与度数关系：

   • 设树中叶结点（度为 $0$ 的结点）个数为 $n_0$。
   • 树的总结点数 $N$ 等于各度数结点数之和： $N = n_0 + n_1 + n_2 + n_3 + n_4$ 代入已知数据：

【答案】B

【2010年真题】第6题 对 $n\ (n \ge 2)$ 个权值均不相同的字符构成赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是（ ）。

• A. 该树一定是一棵完全二叉树
• B. 树中一定没有度为 1 的结点
• C. 树中两个权值最小的结点一定是兄弟结点
• D. 树中任一非叶结点的权值一定不小于下一层任一结点的权值

【解析】

• A 项错误： 赫夫曼树（最优二叉树）只保证带权路径长度（$WPL$）最短，树的形态通常是不平衡的，甚至可能退化为单支倾斜结构，并不保证满足完全二叉树的定义。
• B 项正确： 赫夫曼树构造过程中每次都是选取两棵权值最小的子树合并为一棵新二叉树，新生成的根结点度一定为 $2$，原叶结点度为 $0$，因此赫夫曼树中只有度为 $0$ 和度为 $2$ 的结点，不存在度为 $1$ 的结点（属于正则二叉树/严格二叉树）。
• C 项正确： 根据赫夫曼算法，最开始合并的一定是初始字符中权值最小的两个结点，它们合并后作为新结点的左右孩子，因此必为兄弟结点。
• D 项正确： 赫夫曼树中任意非叶结点的权值等于其左右孩子权值之和。而每次合并均选取当前最小的权值进行合并，自底向上构建，因此上层非叶结点的权值必然不小于其下一层任意结点的权值。

【答案】A

心得笔记

我不知道的事情：结点数等于分支总数+1 。

题目

一棵树共有 $n$ 个结点，其中所有分支结点的度均为 $k$，则该树中的叶结点数为 $(nk-n+1)/k$。

利用树的度数与结点数关系推导： 树中的叶结点数为 $n_0$，树中的分支结点（非叶结点）数为 $m$。由题意可知总结点数：$m = n - n_0$

每个分支结点的度均为 $k$，叶结点的度为 $0$，因此树中所有结点的度数之和（即总分支数 $B$）为： $B = m \cdot k$

• 在任意一棵包含 $n$ 个结点的树中，除根结点外，每个结点上方都有且仅有一条边与之对应，故总边数满足： $B = n - 1$

3. 联立求解 $n\_0$：

   • 由 $m \\cdot k = n - 1$，将 $m = n - n\_0$ 代入得： $$

D