二叉樹

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

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

(1)空二叉樹

(2)只有一個根結點的二叉樹

(3)只有左子樹

(4)只有右子樹

(5)完全二叉樹

注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。

(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。

(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。

(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL演演算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。

二叉樹不是樹的一種特殊情形，儘管其與樹有許多相似之處，但樹和二叉樹有兩個主要差別：

1. 樹中結點的最大度數沒有限制，而二叉樹結點的最大度數為2；

2. 樹的結點無左、右之分，而二叉樹的結點有左、右之分。

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

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

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

④分支結點：也稱為非終端結點，度不為零的結點稱為非終端結點。

⑤樹的度：樹中所有結點的度的最大值。

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

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

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

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

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

(1) 在非空二叉樹中，第i層的結點總數不超過, i>=1；

(2) 深度為h的二叉樹最多有個結點(h>=1)，最少有h個結點；

(3) 對於任意一棵二叉樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1；

(4) 具有n個結點的完全二叉樹的深度為（註：[ ]表示向下取整）

(5)有N個結點的完全二叉樹各結點如果用順序方式存儲，則結點之間有如下關係：

若I為結點編號則 如果I>1，則其父結點的編號為I/2；

如果2*I<=N，則其左孩子（即左子樹的根結點）的編號為2*I；若2*I>N，則無左孩子；

如果2*I+1<=N，則其右孩子的結點編號為2*I+1；若2*I+1>N，則無右孩子。

(6)給定N個節點，能構成h(N)種不同的二叉樹。

h(N)為卡特蘭數的第N項。h(n)=C(2*n，n)/(n+1)。

(7)設有i個枝點，I為所有枝點的道路長度總和，J為葉的道路長度總和J=I+2i

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

設L、D、R分別表示遍歷左子樹、訪問根結點和遍歷右子樹，則對一棵二叉樹的遍歷有三種情況：DLR（稱為先根次序遍歷），LDR（稱為中根次序遍歷），LRD （稱為後根次序遍歷）。

首先訪問根，再先序遍歷左（右）子樹，最後先序遍歷右（左）子樹，C語言代碼如下：

首先中序遍歷左（右）子樹，再訪問根，最後中序遍歷右（左）子樹，C語言代碼如下

首先後序遍歷左（右）子樹，再後序遍歷右（左）子樹，最後訪問根，C語言代碼如下

即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同）

線索二叉樹(保留遍歷時結點在任一序列的前驅和後繼的信息)：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild指示其後繼。還需在結點結構中增加兩個標誌域LTag和RTag。LTag=0時，lchild域指示結點的左孩子，LTag=1時，lchild域指示結點的前驅；RTag=0時，rchild域指示結點的右孩子，RTag=1時，rchild域指示結點的後繼。以這種結點結構構成的二叉線索鏈表，鏈表作為二叉樹的存儲結構，叫做其中指向結點前驅和後繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鏈表稱為為中序線索鏈表。線索二叉樹是一種物理結構。在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。

在後序線索樹中找到結點的後繼分三種情況：

若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。

範例二叉樹：

A

B C

D E

此樹的順序結構為：ABCDE