对于一棵具有 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 个。