CSP-J 2021 第一轮 第 8 题：高度为5的完全二叉树有多少种形态

题目

如果一棵二叉树只有根结点，那么这棵二叉树高度为 $1$。请问高度为 $5$ 的完全二叉树有 （ ）种不同的形态？

选项

• A. 16
• B. 15
• C. 17
• D. 32

答案

A

题解

答案是 A. 16。

完全二叉树的特点是：除最后一层外，其余各层都满；最后一层的结点从左到右连续排列。

高度为 \(5\)，所以：

• 前 \(4\) 层必须填满，形态固定。
• 第 \(5\) 层最多有 \(2^{5-1}=16\) 个结点，最少有 \(1\) 个结点（否则高度就不是 \(5\)）。
• 第 \(5\) 层可以有 \(1,2,\ldots,16\) 个结点，每种数量都只对应一种形态，因为必须从左到右排列。

因此共有 \(\boxed{16}\) 种不同的形态。