樹，其中每個節點有兩個孩子的節點的數量的節點

Question

我已經具有以下形式的樹：

在第一張照片中，樹的高度爲1和有3個節點。 2爲下一個7和3爲15爲最後一個。我怎樣才能確定這種形式的樹的高度將有多少個樹節點？此外，什麼樣的樹（特別是什麼東西？）？

Answer 1

這是一個perfect binary tree

你可以考慮這個遞歸計算策略節點的數量：

n(0) = 1 
n(l+1) = n(l) + 2^l 

所以

n(l) = 2^(l+1) - 1 

Answer 2

節點的一棵完整的樹的數量..

n = 2 ^（h + 1） - 1.

Answer 3

深度'd'處的完整二叉樹是嚴格二叉樹，其中所有葉子都處於d級。

• 爲FIG1，d = 1
• 爲fig2，d = 2
• 爲圖三，d = 3

所以，假設深度d的二進制樹T。然後在最

2(d+1)-1節點 n可以有在T.

• 爲FIG1，d = 1; 2(1+1)-1 = 2(2)-1 = 4-1 = 3
• 對於圖2，d = 2; 2(2+1)-1 = 2(3)-1 = 8-1 = 7
• 圖3 d = 3; 2(3+1)-1 = 2(4)-1 = 16-1 = 15

的高度（h）和深度的樹（從根部到葉節點的最長路徑的長度）的（d）在數值上是相等的。

這是answer詳細說明如何計算深度和高度。

Answer 4

您所描述的內容聽起來像「完美的二叉樹」。 「一棵二叉樹是一棵樹數據結構，其中每個節點至多有兩個孩子」 http://en.wikipedia.org/wiki/Binary_tree 一棵完美的樹是「一棵二叉樹，所有葉節點都在同一深度。「 http://xlinux.nist.gov/dads//HTML/perfectBinaryTree.html

高度完美的二進制樹中的節點的最大數目 = 2 ^（高度+ 1）-1

數量的節點到最小高度 = CEILING（LOG（節點+ 1,2） -1,1）與二叉樹相關

定義可以在前面提到的維基百科中找到。

Answer 5

這也可以被理解是這樣的。

在完美二進制樹的情況下 葉節點的總數爲2 1 H（H =樹的高度）

和內部節點的總數爲2 1 H - 1

因此，如其他人所述，節點的總數將是2^H + 2^H-1，其爲2 ^（H + 1）-1。

希望這會有所幫助。