41. n 層的二元樹最多有多少個節點？
(A) 2n+1
(B) 2n+1 -1
(C) 2n
(D) n2

答案：登入後查看
統計： A(6), B(93), C(13), D(3), E(0) #3113660

詳解 (共 2 筆)

#6085124


(共 1 字，隱藏中）
前往觀看
4
0
#6422358

在二元樹中，討論最大節點數通常會區分「層數」（level）或「高度」（height）的定義方式。

定義一：以層數計算 (Levels, starting from 1) 如果「n 層」指的是樹的層數，且根節點位於第 1 層：

  • 第 1 層：最多有 20=1 個節點
  • 第 2 層：最多有 21=2 個節點
  • 第 3 層：最多有 22=4 個節點
  • ...
  • 第 n 層：最多有 2n−1 個節點

一個具有 n 層的滿二元樹（或完全二元樹的最大節點數），其總節點數是各層節點數的總和： 1+2+4+…+2n−1=∑i=0n−1​2i=2n−1

定義二：以高度計算 (Height, starting from 0) 如果「n 層」指的是樹的高度，且單一節點（根節點）的高度為 0：

  • 高度為 0（1 層）：最多有 21−1=1 個節點
  • 高度為 1（2 層）：最多有 22−1=3 個節點
  • 高度為 2（3 層）：最多有 23−1=7 個節點
  • ...
  • 高度為 n：最多有 2n+1−1 個節點
1
0