🏷️ 知识点：Ds.05.01.03
一棵有 n 个结点的树的所有结点的度数之和为（ ）。
A. n- 1 B. n C. n+1 D. 2n
[tag_link]
正确答案：A
结论
有 n 个结点的树恰有 n-1 条边。每条边恰好由其双亲结点贡献 1 个度，所以所有结点的度数之和为 n-1，选择 A。
推导
有 n 个结点的树恰有 n-1 条边。每条边恰好由其双亲结点贡献 1 个度，所以所有结点的度数之和为 n-1，选择 A。
易错点
结点的度数之和统计的是孩子边，不要把每条边按两个端点重复计算。
对于一棵具有 n 个结点、度为4的树来说，（ ）。
A. 树的高度至多是n-3 B. 树的高度至多是n-4 C. 第 i 层上至多有4(i-1)个结点 D. 至少在某一层上正好有4个结点
[tag_link]
正确答案：A
结论
树的度为 4，至少有一个结点拥有 4 个孩子。为让高度最大，其余结点排成单链，最少要为该四叉分支额外占用 3 个结点，因此高度至多为 n-3，选择 A。
推导
树的度为 4，至少有一个结点拥有 4 个孩子。为让高度最大，其余结点排成单链，最少要为该四叉分支额外占用 3 个结点，因此高度至多为 n-3，选择 A。
易错点
第 i 层上界应是 4^(i-1)，不是 4(i-1)；某层至少含那 4 个孩子，但还可能有其他结点，不能说恰好 4 个。
度为4、高度为h 的树， （ ）。
A. 至少有 h+3 个结点 B. 至多有4h-1 个结点 C. 至多有4h 个结点 D. 至少有 h+4 个结点
[tag_link]
正确答案：A
结论
高度为 h 且度为 4 时，为使结点最少，只让一个分支结点有 4 个孩子，其余层沿一个孩子延伸，共需 h+3 个结点，选择 A。
推导
高度为 h 且度为 4 时，为使结点最少，只让一个分支结点有 4 个孩子，其余层沿一个孩子延伸，共需 h+3 个结点，选择 A。
易错点
最大结点数是 1+4+4^2+…+4^(h-1)，不能写成 4h 或 4h-1。
假定一棵度为3的树中，结点数为50，则其最小高度为（ ）。
A. 3 B. 4 C. 5 D. 6
[tag_link]
正确答案：C
结论
三叉树前 4 层最多容纳 1+3+9+27=40 个结点，小于 50；第 5 层再放 10 个即可，所以最小高度为 5，选择 C。
推导
三叉树前 4 层最多容纳 1+3+9+27=40 个结点，小于 50；第 5 层再放 10 个即可，所以最小高度为 5，选择 C。
易错点
求最小高度要让上层尽可能满；不能把结点数直接除以树的度。
设有一棵度为3的树，其中度为3的结点数n₃=2，度为2的结点数n₂=1，叶结点数 no=6，则该树的结点总数为（ ）。
A. 12 B. 9 C. 10 D. ≥9 的任意整数
[tag_link]
正确答案：D
结论
设度为 1 的结点数为 n1，则总结点数 N=6+n1+1+2=n1+9。度数和为 n1+2×1+3×2=n1+8，恰等于 N-1，所以 n1 无法唯一确定，N 可取任意不小于 9 的整数，选择 D。
推导
设度为 1 的结点数为 n1，则总结点数 N=6+n1+1+2=n1+9。度数和为 n1+2×1+3×2=n1+8，恰等于 N-1，所以 n1 无法唯一确定，N 可取任意不小于 9 的整数，选择 D。
易错点
关系 n0=1+n2+2n3 只验证叶结点数；它会消去 n1，不能据此虚构唯一的总结点数。
含有n 个结点的三叉树的最小高度是多少？
[tag_link]
参考答案
设三叉树高度为 h（根为第 1 层）。高度为 h 的三叉树至多有 (3^h-1)/2 个结点，因此最小高度为 h=ceil(log_3(2n+1))。
推导过程
先令前 h-1 层全满，有 (3^(h-1)-1)/2 < n；再要求前 h 层容量覆盖 n，有 n <= (3^h-1)/2。合并得到 3^(h-1) < 2n+1 <= 3^h，所以 h=ceil(log_3(2n+1))。
评分要点
- 写出 h 层最大容量
- 建立严格的上下界
- 给出向上取整结果并说明根为第 1 层
已知一棵度为4的树中，度为0,1,2,3的结点数分别为14,4,3,2，求该树的结点总数n 和度为4的结点数，并给出推导过程。
[tag_link]
参考答案
度为 4 的结点数 n4=2，总结点数 n=25。
推导过程
按结点分类，n=14+4+3+2+n4=23+n4。按度数和加 1，n=1+1×4+2×3+3×2+4n4=17+4n4。联立得 23+n4=17+4n4，所以 n4=2，代回得 n=25。
评分要点
- 列出结点分类等式
- 列出度数和加 1 等式
- 联立求得 n4=2、n=25
已知一棵度为m 的树中，有n₁ 个度为1的结点，有n₂ 个度为2的结点……有nm 个度为 m 的结点，问该树有多少个叶结点？
[tag_link]
参考答案
叶结点数 n0=1+n2+2n3+…+(m-1)nm。
推导过程
一方面，总结点数 n=n0+n1+n2+…+nm；另一方面，树的边数等于所有结点的度数和，所以 n=1+n1+2n2+…+mnm。两式相减并整理，即得 n0=1+Σ(i-1)ni（i=2…m）。
评分要点
- 分别写出总结点数与度数和等式
- 两式相减消去 n 和 n1
- 写出一般式及求和范围