完全二叉樹各種計算公式總結

完全二叉樹的葉子節點數公式為：

設葉子節點數為n0， 度為1的節點數為n1，度為2的節點數為n2，總節點為n。

1、當n為奇數時（即度為1的節點為0個），n0= (n+1)/2。

2、當n為偶數（即度為1的節點為1個）， n0= n/2。

n1，n2，都可以求。

特殊類型：

1、滿二叉樹：如果一棵二叉樹只有度為0的結點和度為2的結點，並且度為0的結點在同一層上，則這棵二叉樹為滿二叉樹。

2、完全二叉樹：深度為k，有n個結點的二叉樹若且唯若其每一個結點都與深度為k的滿二叉樹中編號從1到n的結點一一對應時，稱為完全二叉樹。

3、完全二叉樹的特點是葉子結點只可能出現在層序最大的兩層上，並且某個結點的左分支下子孫的最大層序與右分支下子孫的最大層序相等或大1。

相關術語：

1、結點：包含一個數據元素及若干指向子樹分支的信息。

2、結點的度：一個結點擁有子樹的數目稱為結點的度。

3、葉子結點：也稱為終端結點，沒有子樹的結點或者度為零的結點。

4、結點的層次：從根結點開始，假設根結點為第1層，根結點的子節點為第2層，依此類推，如果某一個結點位於第L層，則其子節點位於第L+1層。

5、樹的深度：也稱為樹的高度，樹中所有結點的層次最大值稱為樹的深度。