[科普中國(guó)]-二叉樹

在計(jì)算機(jī)科學(xué)中，二叉樹是每個(gè)結(jié)點(diǎn)最多有兩個(gè)子樹的樹結(jié)構(gòu)。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用于實(shí)現(xiàn)二叉查找樹和二叉堆。

一棵深度為k，且有2^k-1個(gè)節(jié)點(diǎn)的二叉樹，稱為滿二叉樹。這種樹的特點(diǎn)是每一層上的節(jié)點(diǎn)數(shù)都是最大節(jié)點(diǎn)數(shù)。而在一棵二叉樹中，除最后一層外，若其余層都是滿的，并且最后一層或者是滿的，或者是在右邊缺少連續(xù)若干節(jié)點(diǎn)，則此二叉樹為完全二叉樹。具有n個(gè)節(jié)點(diǎn)的完全二叉樹的深度為floor(log2n)+1。深度為k的完全二叉樹，至少有2k-1個(gè)葉子節(jié)點(diǎn)，至多有2k-1個(gè)節(jié)點(diǎn)。

定義二叉樹是一個(gè)連通的無環(huán)圖，并且每一個(gè)頂點(diǎn)的度不大于3。有根二叉樹還要滿足根結(jié)點(diǎn)的度不大于2。有了根結(jié)點(diǎn)之后，每個(gè)頂點(diǎn)定義了唯一的父結(jié)點(diǎn)，和最多2個(gè)子結(jié)點(diǎn)。然而，沒有足夠的信息來區(qū)分左結(jié)點(diǎn)和右結(jié)點(diǎn)。如果不考慮連通性，允許圖中有多個(gè)連通分量，這樣的結(jié)構(gòu)叫做森林。1

基本概念二叉樹是遞歸定義的，其結(jié)點(diǎn)有左右子樹之分，邏輯上二叉樹有五種基本形態(tài)：

(1)空二叉樹——如圖(a)；

(2)只有一個(gè)根結(jié)點(diǎn)的二叉樹——如圖(b)；

(3)只有左子樹——如圖(c)；

(4)只有右子樹——如圖(d)；

(5)完全二叉樹——如圖(e)。

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

類型(1)完全二叉樹——若設(shè)二叉樹的高度為h，除第 h 層外，其它各層 (1～h-1) 的結(jié)點(diǎn)數(shù)都達(dá)到最大個(gè)數(shù)，第h層有葉子結(jié)點(diǎn)，并且葉子結(jié)點(diǎn)都是從左到右依次排布，這就是完全二叉樹。

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

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

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

1. 樹中結(jié)點(diǎn)的最大度數(shù)沒有限制，而二叉樹結(jié)點(diǎn)的最大度數(shù)為2；

2. 樹的結(jié)點(diǎn)無左、右之分，而二叉樹的結(jié)點(diǎn)有左、右之分。

相關(guān)術(shù)語樹的結(jié)點(diǎn)（node）：包含一個(gè)數(shù)據(jù)元素及若干指向子樹的分支；

孩子結(jié)點(diǎn)（child node）：結(jié)點(diǎn)的子樹的根稱為該結(jié)點(diǎn)的孩子；

雙親結(jié)點(diǎn)：B 結(jié)點(diǎn)是A 結(jié)點(diǎn)的孩子，則A結(jié)點(diǎn)是B 結(jié)點(diǎn)的雙親；

兄弟結(jié)點(diǎn)：同一雙親的孩子結(jié)點(diǎn)； 堂兄結(jié)點(diǎn)：同一層上結(jié)點(diǎn)；

祖先結(jié)點(diǎn): 從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)

子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫

結(jié)點(diǎn)層：根結(jié)點(diǎn)的層定義為1；根的孩子為第二層結(jié)點(diǎn)，依此類推；

樹的深度：樹中最大的結(jié)點(diǎn)層

結(jié)點(diǎn)的度：結(jié)點(diǎn)子樹的個(gè)數(shù)

樹的度： 樹中最大的結(jié)點(diǎn)度。

葉子結(jié)點(diǎn)：也叫終端結(jié)點(diǎn)，是度為 0 的結(jié)點(diǎn)；

分枝結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)；

有序樹：子樹有序的樹，如：家族樹；

無序樹：不考慮子樹的順序；

二叉樹性質(zhì)(1) 在非空二叉樹中，第i層的結(jié)點(diǎn)總數(shù)不超過, i>=1；

(2) 深度為h的二叉樹最多有個(gè)結(jié)點(diǎn)(h>=1)，最少有h個(gè)結(jié)點(diǎn)；

(3) 對(duì)于任意一棵二叉樹，如果其葉結(jié)點(diǎn)數(shù)為N0，而度數(shù)為2的結(jié)點(diǎn)總數(shù)為N2，則N0=N2+1；

(4) 具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為（注：[ ]表示向下取整）

(5)有N個(gè)結(jié)點(diǎn)的完全二叉樹各結(jié)點(diǎn)如果用順序方式存儲(chǔ)，則結(jié)點(diǎn)之間有如下關(guān)系：

若I為結(jié)點(diǎn)編號(hào)則 如果I>1，則其父結(jié)點(diǎn)的編號(hào)為I/2；

如果2*IN，則無左孩子；

如果2*I+1N，則無右孩子。

(6)給定N個(gè)節(jié)點(diǎn)，能構(gòu)成h(N)種不同的二叉樹。

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

(7)設(shè)有i個(gè)枝點(diǎn)，I為所有枝點(diǎn)的道路長(zhǎng)度總和，J為葉的道路長(zhǎng)度總和J=I+2i2

存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)方式typenode=recorddata:datatypel,r:integer;end;vartr:array[1..n]ofnode;鏈表存儲(chǔ)方式typebtree=^node；node=recorddata:datatye;lchild,rchild:btree;end;二叉樹遍歷遍歷是對(duì)樹的一種最基本的運(yùn)算，所謂遍歷二叉樹，就是按一定的規(guī)則和順序走遍二叉樹的所有結(jié)點(diǎn)，使每一個(gè)結(jié)點(diǎn)都被訪問一次，而且只被訪問一次。由于二叉樹是非線性結(jié)構(gòu)，因此，樹的遍歷實(shí)質(zhì)上是將二叉樹的各個(gè)結(jié)點(diǎn)轉(zhuǎn)換成為一個(gè)線性序列來表示。

設(shè)L、D、R分別表示遍歷左子樹、訪問根結(jié)點(diǎn)和遍歷右子樹， 則對(duì)一棵二叉樹的遍歷有三種情況：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}層次遍歷即按照層次訪問，通常用隊(duì)列來做。訪問根，訪問子女，再訪問子女的子女（越往后的層次越低）（兩個(gè)子女的級(jí)別相同）

線索二叉樹線索二叉樹(保留遍歷時(shí)結(jié)點(diǎn)在任一序列的前驅(qū)和后繼的信息)：若結(jié)點(diǎn)有左子樹，則其lchild域指示其左孩子，否則令lchild域指示其前驅(qū)；若結(jié)點(diǎn)有右子樹，則其rchild域指示其右孩子，否則令rchild指示其后繼。還需在結(jié)點(diǎn)結(jié)構(gòu)中增加兩個(gè)標(biāo)志域LTag和RTag。LTag=0時(shí)，lchild域指示結(jié)點(diǎn)的左孩子，LTag=1時(shí)，lchild域指示結(jié)點(diǎn)的前驅(qū)；RTag=0時(shí)，rchild域指示結(jié)點(diǎn)的右孩子，RTag=1時(shí)，rchild域指示結(jié)點(diǎn)的后繼。以這種結(jié)點(diǎn)結(jié)構(gòu)構(gòu)成的二叉線索鏈表，鏈表作為二叉樹的存儲(chǔ)結(jié)構(gòu)，叫做其中指向結(jié)點(diǎn)前驅(qū)和后繼的指針叫做線索，加上線索的二叉樹稱為線索二叉樹。對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過程叫做線索化。若對(duì)二叉樹進(jìn)行中序遍歷，則所得的線索二叉樹稱為中序線索二叉樹，線索鏈表稱為為中序線索鏈表。線索二叉樹是一種物理結(jié)構(gòu)。在中序線索樹找結(jié)點(diǎn)后繼的規(guī)律是：若其右標(biāo)志為1，則右鏈為線索，指示其后繼，否則遍歷其右子樹時(shí)訪問的第一個(gè)結(jié)點(diǎn)（右子樹最左下的結(jié)點(diǎn)）為其后繼；找結(jié)點(diǎn)前驅(qū)的規(guī)律是：若其左標(biāo)志為1，則左鏈為線索，指示其前驅(qū)，否則遍歷左子樹時(shí)最后訪問的一個(gè)結(jié)點(diǎn)（左子樹中最右下的結(jié)點(diǎn)）為其前驅(qū)。

在后序線索樹中找到結(jié)點(diǎn)的后繼分三種情況：

若結(jié)點(diǎn)是二叉樹的根，則其后繼為空；若結(jié)點(diǎn)是其雙親的右孩子，或是其雙親的左孩子且其雙親沒有右子樹，則其后繼即為雙親結(jié)點(diǎn)；若結(jié)點(diǎn)是其雙親的左孩子，且其雙親有右子樹，則其后繼為雙親右子樹上按后序遍歷列出的第一個(gè)結(jié)點(diǎn)。

示例范例二叉樹：

A

B C

D E

此樹的順序結(jié)構(gòu)為：ABCDE3

int main(){ node* p = newnode; node* p = head; head = p; string str; cin >> str; creat(p, str, 0)//默認(rèn)根節(jié)點(diǎn)在str下標(biāo)0的位置 return 0;}//p為樹的根節(jié)點(diǎn)（已開辟動(dòng)態(tài)內(nèi)存）,str為二叉樹的順序存儲(chǔ)數(shù)組ABCD##E或其他順序存儲(chǔ)數(shù)組，r當(dāng)前結(jié)點(diǎn)所在順序存儲(chǔ)數(shù)組位置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); }}本詞條內(nèi)容貢獻(xiàn)者為:

王偉 - 副教授 - 上海交通大學(xué)