二叉樹:定義,基本概念,類型,辨析,相關術語,二叉樹性質,存儲結構,順序存儲方式,

在計算機科學中，二叉樹是每個結點最多有兩個子樹的樹結構。通常子樹被稱作“左子樹”（left subtree）和“右子樹”（right subtree）。二叉樹常被用於實現二叉查找樹和二叉堆。

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

基本介紹

中文名：二叉樹
外文名：Binary Tree
概述：計算機中數據結構的一種
簡介：每個結點最多有兩個子樹的樹結構
套用學科：計算機科學
存儲方式：順序存儲、鏈式存儲

定義,基本概念,類型,辨析,相關術語,二叉樹性質,存儲結構,順序存儲方式,鍊表存儲方式,二叉樹遍歷,先序遍歷,中序遍歷,後序遍歷,層次遍歷,線索二叉樹,示例,

定義

二叉樹是一個連通的無環圖，並且每一個頂點的度不大於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，並且左右兩個子樹都是一棵平衡二叉樹。

辨析

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

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

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

二叉樹性質

(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

存儲結構

順序存儲方式

typenode=recorddata:datatypel,r:integer;end;vartr:array[1..n]ofnode;

鍊表存儲方式

typebtree=^node；node=recorddata:datatye;lchild,rchild:btree;end;

二叉樹遍歷

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

設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，則左鏈為線索，指示其前驅，否則遍歷左子樹時最後訪問的一個結點（左子樹中最右下的結點）為其前驅。

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

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

示例

範例二叉樹：

B C

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);    }}

二叉樹