二叉樹檢視原始碼討論檢視歷史
| 二叉樹 |
二叉樹（Binary tree）是指計算機科學中每個結點最多有兩個子樹的樹結構，其子樹被稱作「左子樹」（left subtree）和「右子樹」（right subtree），常被用於實現二叉查找樹和二叉堆。
在二叉樹中，一個元素也稱作一個結點。當集合為空時，稱該二叉樹為空二叉樹。
目錄
定義
基本概念
相關術語
二叉樹性質
二叉樹遍歷
線索二叉樹
示例
定義
二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根結點的度不大於2。有了根結點之後，每個頂點定義了唯一的父結點，和最多2個子結點。然而，沒有足夠的信息來區分左結點和右結點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林。
基本概念
二叉樹是遞歸定義的，其結點有左右子樹之分，邏輯上二叉樹有五種基本形態：
(1)空二叉樹——如圖(a)；
(2)只有一個根結點的二叉樹——如圖(b)；
(3)只有左子樹——如圖(c)；
(4)只有右子樹——如圖(d)；
(5)完全二叉樹——如圖(e)。
注意：儘管二叉樹與樹有許多相似之處，但二叉樹不是樹的特殊情形。
類型
(1)完全二叉樹——若設二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結點數都達到最大個數，第h層有葉子結點，並且葉子結點都是從左到右依次排布，這就是完全二叉樹。
(2)滿二叉樹——除了葉結點外每一個結點都有左右子葉且葉子結點都處在最底層的二叉樹。
(3)平衡二叉樹——平衡二叉樹又被稱為AVL樹（區別於AVL算法），它是一棵二叉排序樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二叉樹。
辨析
二叉樹是樹的一種特殊情形，是一種更簡單而且應用更加廣泛的樹。
相關術語
樹的結點（node）：包含一個數據元素及若干指向子樹的分支；
孩子結點（child node）：結點的子樹的根稱為該結點的孩子；
雙親結點：B 結點是A 結點的孩子，則A結點是B 結點的雙親；
兄弟結點：同一雙親的孩子結點； 堂兄結點：同一層上結點；
祖先結點: 從根到該結點的所經分支上的所有結點
子孫結點：以某結點為根的子樹中任一結點都稱為該結點的子孫
結點層：根結點的層定義為1；根的孩子為第二層結點，依此類推；
樹的深度：樹中最大的結點層
結點的度：結點子樹的個數
樹的度： 樹中最大的結點度。
葉子結點：也叫終端結點，是度為 0 的結點；
分枝結點：度不為0的結點；[1]
有序樹：子樹有序的樹，如：家族樹；
無序樹：不考慮子樹的順序；
二叉樹性質
(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語言代碼如下：
void XXBL(tree *root){
//DoSomethingwithroot
if(root->lchild!=NULL)
XXBL(root->lchild);
if(root->rchild!=NULL)
XXBL(root->rchild);
}
中序遍歷
首先中序遍歷左（右）子樹，再訪問根，最後中序遍歷右（左）子樹，C語言代碼如下：
void ZXBL(tree *root) {
if(root->lchild!=NULL)
ZXBL(root->lchild);
//Do something with root
if(root->rchild!=NULL)
ZXBL(root->rchild);
}
後序遍歷
首先後序遍歷左（右）子樹，再後序遍歷右（左）子樹，最後訪問根，C語言代碼如下：
void HXBL(tree *root){
if(root->lchild!=NULL)
HXBL(root->lchild);
if(root->rchild!=NULL)
HXBL(root->rchild);
//Do something with root
}
層次遍歷
即按照層次訪問，通常用隊列來做。訪問根，訪問子女，再訪問子女的子女（越往後的層次越低）（兩個子女的級別相同）
線索二叉樹
線索二叉樹(保留遍歷時結點在任一序列的前驅和後繼的信息)：若結點有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅；若結點有右子樹，則其rchild域指示其右孩子，否則令rchild指示其後繼。還需在結點結構中增加兩個標誌域LTag和RTag。LTag=0時，lchild域指示結點的左孩子，LTag=1時，lchild域指示結點的前驅；RTag=0時，rchild域指示結點的右孩子，RTag=1時，rchild域指示結點的後繼。以這種結點結構構成的二叉線索鍊表，鍊表作為二叉樹的存儲結構，叫做其中指向結點前驅和後繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹。對二叉樹以某種次序遍歷使其變為線索二叉樹的過程叫做線索化。
若對二叉樹進行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鍊表稱為為中序線索鍊表。線索二叉樹是一種物理結構。在中序線索樹找結點後繼的規律是：若其右標誌為1，則右鏈為線索，指示其後繼，否則遍歷其右子樹時訪問的第一個結點（右子樹最左下的結點）為其後繼；找結點前驅的規律是：若其左標誌為1，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。
在後序線索樹中找到結點的後繼分三種情況：
若結點是二叉樹的根，則其後繼為空；若結點是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其後繼即為雙親結點；若結點是其雙親的左孩子，且其雙親有右子樹，則其後繼為雙親右子樹上按後序遍歷列出的第一個結點。
示例
範例二叉樹：
D E
此樹的順序結構為：ABCDE
int main() {
node* p = newnode; node* p = head; head = p; string str; cin >> str; creat(p, str, 0)//默认根结点在str下标0的位置 return 0;
} //p為樹的根結點（已開闢動態內存）,str為二叉樹的順序存儲數組ABCD##E或其他順序存儲數組，r當前結點所在順序存儲數組位置 void creat(node* p, string str, int r) {
p->data = str[r];
if (str[r * 2 + 1] == '#' || r * 2 + 1 > str.size() - 1)p->lch = NULL;
else
{
p->lch = newnode;
creat(p->lch, str, r * 2 + 1);
}
if (str[r * 2 + 2] == '#' || r * 2 + 2 > str.size() - 1)p->rch = NULL;
else
{
p->rch = newnode;
creat(p->rch, str, r * 2 + 2);
}