CSP-J 2020 第一轮 第 12 题：61个结点的完全二叉树的高度

题目

独根树的高度为 $1$。具有 $61$ 个结点的完全二叉树的高度为（ ）。

选项

• A. 7
• B. 8
• C. 5
• D. 6

答案

D

题解

答案是 D. 6。

完全二叉树按从上到下、从左到右的顺序填充结点，每层最多有 \(1,2,4,8,\dots\) 个结点。

• 前 \(5\) 层填满，共有 \(1+2+4+8+16=31\) 个结点。
• 前 \(6\) 层填满，共有 \(31+32=63\) 个结点。

因为 \(31<61\le63\)，所以第 \(6\) 层有结点，但不需要第 \(7\) 层，树的高度为 6。