二叉樹

二叉樹（binary tree）是指樹中節點的度不大於2的有序樹，它是一種最簡單且最重要的樹。二叉樹的遞歸定義為：二叉樹是一棵空樹，或者是一棵由一個根節點和兩棵互不相交的，分別稱作根的左子樹和右子樹組成的非空樹；左子樹和右子樹又同樣都是二叉樹 ^[2]  。

二叉樹是遞歸定義的，其節點有左右子樹之分，邏輯上二叉樹有五種基本形態： ^[3] 

1、空二叉樹——如圖1（a） ^[3]  ；

2、只有一個根節點的二叉樹——如圖1（b） ^[3]  ；

3、只有左子樹——如圖1（c） ^[3]  ；

4、只有右子樹——如圖1（d） ^[3]  ；

5、完全二叉樹——如圖1（e） ^[3]  。

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

2、完全二叉樹：深度為k，有n個節點的二叉樹當且僅當其每一個節點都與深度為k的滿二叉樹中編號從1到n的節點一一對應時，稱為完全二叉樹 ^[4]  。

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

①節點：包含一個數據元素及若干指向子樹分支的信息 ^[5]  。

②節點的度：一個節點擁有子樹的數目稱為節點的度 ^[5]  。

③葉子節點：也稱為終端節點，沒有子樹的節點或者度為零的節點 ^[5]  。

④分支節點：也稱為非終端節點，度不為零的節點稱為非終端節點 ^[5]  。

⑤樹的度：樹中所有節點的度的最大值 ^[5]  。

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

⑦樹的深度：也稱為樹的高度，樹中所有節點的層次最大值稱為樹的深度 ^[5]  。

⑧有序樹：如果樹中各棵子樹的次序是有先後次序，則稱該樹為有序樹 ^[5]  。

⑨無序樹：如果樹中各棵子樹的次序沒有先後次序，則稱該樹為無序樹 ^[5]  。

⑩森林：由m（m≥0）棵互不相交的樹構成一片森林。如果把一棵非空的樹的根節點刪除，則該樹就變成了一片森林，森林中的樹由原來根節點的各棵子樹構成 ^[5]  。

性質1：二叉樹的第i層上至多有2^i-1（i≥1）個節點 ^[6]  。

性質2：深度為h的二叉樹中至多含有2^h-1個節點 ^[6]  。

性質3：若在任意一棵二叉樹中，有n₀個葉子節點，有n₂個度為2的節點，則必有n₀=n₂+1 ^[6]  。

性質4：具有n個節點的滿二叉樹深為log2n+1。

性質5：若對一棵有n個節點的完全二叉樹進行順序編號（1≤i≤n），那麼，對於編號為i（i≥1）的節點： ^[6] 

當i=1時，該節點為根，它無雙親節點 ^[6]  。

當i>1時，該節點的雙親節點的編號為i/2 ^[6]  。

若2i≤n，則有編號為2i的左節點，否則沒有左節點 ^[6]  。

若2i+1≤n，則有編號為2i+1的右節點，否則沒有右節點 ^[6]  。

遍歷是對樹的一種最基本的運算，所謂遍歷二叉樹，就是按一定的規則和順序走遍二叉樹的所有節點，使每一個節點都被訪問一次，而且只被訪問一次。由於二叉樹是非線性結構，因此，樹的遍歷實質上是將二叉樹的各個節點轉換成為一個線性序列來表示 ^[7]  。

按照某種遍歷方式對二叉樹進行遍歷，可以把二叉樹中所有節點排列為一個線性序列。在該序列中，除第一個節點外，每個節點有且僅有一個直接前驅節點；除最後一個節點外，每個節點有且僅有一個直接後繼節點。但是，二叉樹中每個節點在這個序列中的直接前驅節點和直接後繼節點是什麼，二叉樹的存儲結構中並沒有反映出來，只能在對二叉樹遍歷的動態過程中得到這些信息。為了保留節點在某種遍歷序列中直接前驅和直接後繼的位置信息，可以利用二叉樹的二叉鏈表存儲結構中的那些空指針域來指示。這些指向直接前驅節點和指向直接後繼節點的指針被稱為線索（thread），加了線索的叉樹稱為線索二叉樹 ^[8]  。

線索二叉樹將為二叉樹的遍歷提供許多便利 ^[8]  。