資料結構（一）：二叉樹

定義

二叉樹( binary tree )是有限節點集合構成的結構，其結構的遞歸定義為：

• 三個不相交的節點集合構成，一個作為根節點，一個節點集構成的二叉樹作為根節點的左子樹，另一個節點集構成的二叉樹作為根節點的右子樹
• 當節點數為零時，表示二叉樹為空

是以節點個數為零的空樹也是二叉樹，二叉樹根節點的左、右子樹也是二叉樹，其結構同樣符合以上定義，當左子樹為空樹時，表示根節點沒有左子節點。且二叉樹區分左、右子樹，以下兩個二叉樹為不同的二叉樹。

one

another one

結構特性

首先說明下幾個概念：

• 根節點： 沒有父節點的節點；
• 葉子節點： 沒有子節點的節點；
• 節點的度 ：節點的分支個數，二叉樹每個節點的分支個數為 0~2；
• 路徑：連接配接節點和後代子節點之間的不重複邊；
• 節點的深度：從根節點到該節點的路徑長；
• 節點的高度：從該節點到葉子節點的最大路徑長；
• 節點的層數：父節點的層數加一；
• 樹的高度：根節點高度。
• 樹的深度：葉子節點深度的最大值。

關于高度和深度的起始值 0 或 1 的個人看法：

對于深度、高度和層數的起點值，可能有些地方基數是從1開始計算的。對于這個起點值的設定，個人覺得如果你高興，從10086開始也無妨，因為在應用中，這些資料量隻是為了友善計算，起作用的隻是相對值而已。

為了友善了解，這裡設定基數為0，深度可以認為是從水準面，也就是0深度，往下有幾層，深度就是幾；高度類似了解，地平面是0，往上有幾層，高度就是幾。

參考下圖：

圖檔來源：

What is the difference between tree depth and height?

滿二叉樹、完全二叉樹、完美(理想)二叉樹

關于完全二叉樹和滿二叉樹的定義，因為最初翻譯的不同，已經混淆很久了，是以已經屬于一個曆史問題了。這裡盡量不去分辨哪一種定義是正确的，隻按照個人的了解去描述。

• 滿二叉樹( Full Binary Tree )：

  每個節點的度為 0 或 2，即除了葉子節點，每個節點都有兩個子節點。

示例：

Full Binary Tree

• 完全二叉樹( Complete Binary Tree )：

  除深度最大的一層外，其他每層上的節點都是填充滿的，且深度最大的一層節點分布從左向右是連續無間隔的。

Complete Binary Tree

• 完美/理想二叉樹( Perfect Binary Tree )：

  除葉子節點外，每個節點度都為 2，且葉子節點在同一層。

Perfect Binary Tree

以上概念參考：

• Binary tree
• Binary Tree | Set 3 (Types of Binary Tree)

二叉樹資料量

下面介紹二叉樹幾個資料量之間的關系，變量聲明如下：

：樹的高度

：節點總數

：度為 0 的節點個數，即葉子節點個數

：度為 1 的節點個數

：度為 2 的節點個數

：第

層上節點個數

• 完美二叉樹中，第

  

  層上節點個數為：

  

  proof：

  1.第 0 層上，隻有根節點，是以 0 層節點個數為：

  

  ;

  2.每層節點度都為 2 ，是以下一層的節點個數為：

  

  ；

  3.是以第

  

  層節點個數為：

  

  。
• 深度為

  

  的完美二叉樹，節點總數為：

  

  1.每層的節點個數

  

  構成等比數列，公比為：

  

  2.第 0 層節點個數

  

  ，是以總節點個數為：

  

• 

  的完美二叉樹，非葉子節點和葉子節點的個數有：

  

  ，節點總數與葉子節點個數有：

  

  

  的完美二叉樹，則

  

  層節點即為葉子節點，即：

  

  ，由以上結論可知，深度為

  

  的完美二叉樹，葉子節點個數為

  

  ，總節點個數為

  

  ，是以非葉子節點個數為：

  

  ，即：

  

  ，

  

• 對于普通的非空二叉樹，葉子節點個數

  

  與度為 2 的節點個數

  

  關系為：

  

  1.設度為 1 的節點個數為

  

  ，則節點總數

  

  2.設二叉樹中邊的個數為

  

  ，有如下關系：

  【1】樹中除根節點外，每個節點都存在該節點到其父節點的一條邊，即除根節點外，每個節點都對應着一條邊，則有關系：

  

  【2】樹中每個節點度，表示該節點的子節點個數，也表示着該節點對應的邊的個數，則有關系：

  

  根據【1】【2】可知，有關系：

  

  ，根據 1 中

  

  ，則有：

  

  

  ，二叉樹中葉子節點個數為度為 2 的節點個數加 1。

github

連結： 二叉樹