具有n个结点且高度为n的二叉树的数目为（ ）。

A. log₂n B. n/2 C. n D. 2ⁿ⁻¹

[tag_link]

correct answer: D

结论

高度等于结点数时每个非根结点都可独立选左或右孩子，共2ⁿ⁻¹种。

推导

高度等于结点数时每个非根结点都可独立选左或右孩子，共2ⁿ⁻¹种。

易错点

注意区分完全二叉树与满二叉树，并核对高度按层计数。