第九章 鏈表和二叉樹

第九章鏈表和二叉樹9.1鏈表9.2二叉樹9.1鏈表9.1.1鏈表的概念9.1.2鏈表的操作9.1.3循環(huán)鏈表9.1.1鏈表的概念1.線性表一個(gè)線性表LIST是由n(n≥0)個(gè)同類型數(shù)據(jù)元素a1,a2,a3,……，an組成的有限序列，記作LIST=(a1,a2,a3,……，an)a1為“起始結(jié)點(diǎn)”，an為“終止結(jié)點(diǎn)”n為線性表的長度。當(dāng)n=0時(shí)為空表。ai的前驅(qū)為ai-1，后續(xù)為ai+1。9.1.1鏈表的概念線性表的存儲(chǔ)結(jié)構(gòu)有兩種：順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。其中順序存儲(chǔ)結(jié)構(gòu)是用一組連續(xù)的存儲(chǔ)單元依次存放它的各個(gè)數(shù)據(jù)元素。9.1.1鏈表的概念2.鏈表鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的別稱。其存儲(chǔ)特點(diǎn)是用一組任意的存儲(chǔ)單元存儲(chǔ)數(shù)據(jù)元素，這組存儲(chǔ)單元可以是連續(xù)的，也可以是不連續(xù)的。9.1.1鏈表的概念2.鏈表每個(gè)元素除需存儲(chǔ)自身信息外，還需存儲(chǔ)其后續(xù)元素的信息。每個(gè)元素的存儲(chǔ)映像稱為結(jié)點(diǎn)。存儲(chǔ)后續(xù)結(jié)點(diǎn)的存儲(chǔ)位置的域稱為指針域，存儲(chǔ)數(shù)據(jù)元素信息的域稱為數(shù)據(jù)域。用指針相連的結(jié)點(diǎn)序列稱為鏈表。9.1.1鏈表的概念鏈表中每個(gè)結(jié)點(diǎn)可以包含若干個(gè)數(shù)據(jù)域和指針域。只有一個(gè)指針域的鏈表稱為單鏈表。本章中若沒有特別指出，所有的鏈表均指單鏈表。表中每一行作為一個(gè)結(jié)點(diǎn)，結(jié)點(diǎn)有六個(gè)數(shù)據(jù)域：學(xué)號(hào)，姓名，語文，數(shù)學(xué)，英語，計(jì)算機(jī)，總分；另外還要有一個(gè)指針域（link）。structCJ{charxh[8];charxm[6];

intyw;intsx;intyy;intjsj;intzf;

structCJ*link;};假設(shè)有n個(gè)人，每個(gè)人的數(shù)據(jù)域分別用a1，a2，……an表示。首指針head指示鏈表第一個(gè)結(jié)點(diǎn)的存儲(chǔ)位置。線性表中最后一個(gè)結(jié)點(diǎn)的指針為“空”（NULL）。當(dāng)head為NULL時(shí)，head所指向的鏈表為空表。為操作方便，給鏈表增加一個(gè)頭結(jié)點(diǎn)，頭結(jié)點(diǎn)的數(shù)據(jù)域無意義，而指針域指向線性表的第一個(gè)結(jié)點(diǎn)，并且首指針head指向頭結(jié)點(diǎn)，當(dāng)頭結(jié)點(diǎn)的指針域?yàn)椤翱铡保∟ULL）時(shí)，表示該鏈表為空表。9.1.1鏈表的概念

鏈表也是一種非直接存取的存儲(chǔ)結(jié)構(gòu)，因?yàn)槊恳粋€(gè)結(jié)點(diǎn)的存儲(chǔ)位置都被包含在其前驅(qū)結(jié)點(diǎn)的指針域的指針中。必須從首指針開始，沿指針鏈向后找到要存取的結(jié)點(diǎn)。由于head的指針域?yàn)?1，首先找到該鏈表的第一個(gè)結(jié)點(diǎn)即存儲(chǔ)地址為31的結(jié)點(diǎn)a1，再通過a1的指針域可得其后續(xù)元素的存儲(chǔ)地址為1即(a2)，依次類推，可以找到a3，a4。9.1.2鏈表的操作鏈表是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)，所占用的存儲(chǔ)空間是在程序的執(zhí)行的過程中得到當(dāng)鏈表需要增加一個(gè)結(jié)點(diǎn)時(shí)，要為結(jié)點(diǎn)向系統(tǒng)申請(qǐng)一個(gè)存儲(chǔ)空間。當(dāng)鏈表刪除一個(gè)結(jié)點(diǎn)時(shí)，要將已刪除的結(jié)點(diǎn)的存儲(chǔ)空間釋放，歸還給系統(tǒng)。9.1.2鏈表的操作例如，p為指向結(jié)點(diǎn)的指針變量，

CJ*p;這時(shí)，p所指向的結(jié)點(diǎn)還不存在，需要為p申請(qǐng)一個(gè)結(jié)點(diǎn)，方法為p=newCJ;同樣，當(dāng)p所指向結(jié)點(diǎn)不再需要時(shí)，要釋放該結(jié)點(diǎn)空間，方法為

free(p);9.1.2鏈表的操作1.建立鏈表建立一個(gè)有n個(gè)結(jié)點(diǎn)并帶頭結(jié)點(diǎn)的鏈表，最直接的方法是：首先生成一個(gè)結(jié)點(diǎn)p，將其作為頭結(jié)點(diǎn)，然后依次建立新的結(jié)點(diǎn)q，將其數(shù)據(jù)域置入相應(yīng)的值，指針域賦“空”（NULL），并將其鏈接到鏈表的尾部，且p始終指向鏈表最后一個(gè)結(jié)點(diǎn)。#include<stdio.h> CJ*head,*p,*q;voidcreate(intn){inti;p=newCJ;//分配存儲(chǔ)單元head=p;for(i=1;i<=n;i++){q=newCJ;scanf(“%s”,q->xh);//輸入各項(xiàng)值

scanf(“%s”,q->xm);scanf(“%d”,&q->yw);scanf(“%d”,&q->sx);scanf(“%d”,&q->yy);scanf(“%d”,&q->jsj);scanf(“%d”,&q->zf);q->link=NULL;p->link=q;p=q;}}執(zhí)行create(3)后，若輸入的信息依次為04253101，李緋，85，90，78，92，345，04253102，王小霞，56，85，45，93，278，04253132，張海濤，76，48，83，65，272，得到的鏈表下圖所示。9.1.2鏈表的操作2.插入結(jié)點(diǎn)假設(shè)我們要在鏈表的兩個(gè)數(shù)據(jù)元素a，b之間插入一個(gè)數(shù)據(jù)元素x，已知p為鏈表存儲(chǔ)結(jié)構(gòu)中指向結(jié)點(diǎn)a的指針。如圖9.5所示。假設(shè)s為指向結(jié)點(diǎn)x的指針，則語句描述為s->link=p->link;p->link=s9.1.2鏈表的操作同理，如果要在成績管理系統(tǒng)中第2條和第3條記錄之間插入一條記錄。分配存儲(chǔ)單元給要插入記錄（設(shè)為指針s）然后查找xh為04253102這條記錄（p），并修改s的指針域，使其為p->link然后再修改p的指針域，使其指向s即可CJ*head,*p,*s;voidinsert(inti){intj;p=head;j=1;while((p!=NULL)&&(j<i)){p=p->link;j++;}//尋找第i-1個(gè)結(jié)點(diǎn)if(p==NULL)printf("已到表尾！");{s=newCJ;scanf(“%s”,s->xh);scanf(“%s”,s->xm);scanf(“%d”,&s->yw);scanf(“%d”,&s->sx);scanf(“%d”,&q->yy);scanf(“%d”,&s>jsj);scanf(“%d”,&s->zf);s->link=p->link;p->link=s;}}9.1.2鏈表的操作3.刪除結(jié)點(diǎn)假定在如圖(a)所示線性表中，要?jiǎng)h除b所在的結(jié)點(diǎn)，刪除的方法是：使指針p指向要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)；將p的指針域指向要?jiǎng)h除的結(jié)點(diǎn)的后繼結(jié)點(diǎn)；將要?jiǎng)h除的結(jié)點(diǎn)釋放。刪除過程如下：q=p->link;p->link=q->link;free(q);9.1.2鏈表的操作以成績管理系統(tǒng)為例假設(shè)要?jiǎng)h除xh為04253102記錄，如圖所示?？梢韵炔檎襵h為04253102的前驅(qū)記錄，并修改其指針域，使其指向04253102的后續(xù)記錄，然后釋放空間。CJ*head,*p,*q;delete_link(inti){CJ*p,*q;intj;p=head;j=1;while((p!=NULL)&&(j<i)){p=p->link;j++;}//尋找第i-1個(gè)結(jié)點(diǎn)if(p==NULL)printf("鏈表中沒有要?jiǎng)h除的結(jié)

點(diǎn)");else{q=p->link;p->link=q->link;free(q);//刪除指定結(jié)點(diǎn)q}}9.1.3循環(huán)鏈表如果將鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中第一個(gè)結(jié)點(diǎn)的地址值，就使整個(gè)鏈表構(gòu)成一個(gè)環(huán)形，這樣的鏈表稱為循環(huán)鏈表。循環(huán)鏈表中所有的結(jié)點(diǎn)鏈接成一個(gè)環(huán)，從表的任何一個(gè)結(jié)點(diǎn)出發(fā)都能訪問到表中的所有結(jié)點(diǎn)，也可以給表增加一個(gè)特殊頭結(jié)點(diǎn)。其邏輯結(jié)構(gòu)如圖所示：9.1.3循環(huán)鏈表循環(huán)鏈表的操作和線性鏈表基本一致，差別僅在于算法中的循環(huán)結(jié)束條件不是p或者p->link是否為NULL，而是它們是否等于首指針。有時(shí)在循環(huán)鏈表中設(shè)立尾指針而不設(shè)立首指針，可以簡化某些操作。9.1.3循環(huán)鏈表例如，將兩個(gè)循環(huán)鏈表合并成一個(gè)，僅需將兩個(gè)表的表尾指針交換即可。設(shè)合并的鏈表由指針a和b分別指向各自尾結(jié)點(diǎn)，且都帶有頭結(jié)點(diǎn)。合并過程及合并方法如下：p=a->link;q=b->link;a->link=q->link;b->link=p;free(q);9.2二叉樹單鏈表實(shí)際上是線性結(jié)構(gòu)，即除首元素和尾元素以外，每個(gè)元素有惟一的前驅(qū)和后續(xù)元素。而二叉樹是一種重要的非線性結(jié)構(gòu)，它所討論的是層次和分支關(guān)系，即除了有一個(gè)根元素沒有前驅(qū)以外，每個(gè)元素都有惟一的前驅(qū)元素；另外，每一個(gè)元素都有零個(gè)或多個(gè)后續(xù)元素。9.2二叉樹9.2.1樹及二叉樹的概念9.2.2二叉樹的建立9.2.3二叉樹的遍歷9.2.1樹及二叉樹的概念1.樹的定義現(xiàn)實(shí)生活中存在著許多用樹結(jié)構(gòu)描述的實(shí)際問題。例如，一家族血統(tǒng)關(guān)系。假設(shè)李大民有三個(gè)孩子：李一楊、李一力和李一軍，而李一楊有一個(gè)孩子李輝，李一力有兩個(gè)孩子李曉和李亮。這種關(guān)系可很自然的用樹結(jié)構(gòu)來表示。如圖所示。9.2.1樹及二叉樹的概念1.樹的定義上圖很像一棵倒畫的樹，樹的定義如下：

樹(tree)是n(n>0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵樹中：有且僅有一個(gè)特定的稱為根(root)的結(jié)點(diǎn)；當(dāng)n>1時(shí)，其余結(jié)點(diǎn)可分為m(m>0)個(gè)互個(gè)相交的有限集T1，T2，…，Tm，其中每個(gè)集合本身又是一棵樹，并且稱為根的子樹(subtree)。9.2.1樹及二叉樹的概念(a)是只有一個(gè)根結(jié)點(diǎn)的樹；(b)是有13個(gè)結(jié)點(diǎn)的樹，其中A根，其余結(jié)點(diǎn)分成3個(gè)互不相交的子集：T1={B，E，F(xiàn)，K，L}，T2={C，G}，T3={D，H，I，J，M}；T1、T2和T3都是根A的子樹，且本身也是一棵樹。例如T1，其根為B，其余結(jié)點(diǎn)分為兩個(gè)互不相交的子集：T11={E，K，L}，T12={F}。T11、T12都是B的子樹。而T11中E是根，{K}和{L}是E的兩棵互不相交的子樹，其本身又是只有一個(gè)根結(jié)點(diǎn)的樹。9.2.1樹及二叉樹的概念樹的一些基本術(shù)語：結(jié)點(diǎn)：是包含一個(gè)數(shù)據(jù)元素的若干指向其子樹的分支。結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。例如，在圖9.11(b)中，A的度為3，C的度為1，E的度為2，K的度為0。葉子：度為0的結(jié)點(diǎn)。又稱為終端結(jié)點(diǎn)。圖9.11(b)中的結(jié)點(diǎn)K，L，F(xiàn)，G，M，I，J都是樹的葉子。分支結(jié)點(diǎn)：度不為0的結(jié)點(diǎn)。又稱為非終端結(jié)點(diǎn)。圖9.11(b)中的結(jié)點(diǎn)A，B，C，D，E，H都是樹的分支結(jié)點(diǎn)。9.2.1樹及二叉樹的概念樹的一些基本術(shù)語：內(nèi)部結(jié)點(diǎn)：除根結(jié)點(diǎn)之外的所有分支結(jié)點(diǎn)。樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。圖9.11(b)的樹的度為3。孩子結(jié)點(diǎn)：結(jié)點(diǎn)的子樹的根結(jié)點(diǎn)。相應(yīng)地，該結(jié)點(diǎn)稱為孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。在圖9.11(b)中，D為A的子樹T3的根，則D是A的孩子結(jié)點(diǎn)，而A則是D的雙親結(jié)點(diǎn)。兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子結(jié)點(diǎn)之間互稱為兄弟。例，H，I和J互為兄弟。9.2.1樹及二叉樹的概念樹的一些基本術(shù)語：祖先結(jié)點(diǎn)：從根到該結(jié)點(diǎn)的所經(jīng)分支上的所有結(jié)點(diǎn)。例如M的祖先結(jié)點(diǎn)為A，D和H。子孫結(jié)點(diǎn)：以某結(jié)點(diǎn)為根的子樹中任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。例如B的子孫結(jié)點(diǎn)有E，F(xiàn)，K，L。結(jié)點(diǎn)的層次：從根開始定義起，根為第一層，根的孩子為第二層，再下一層為第三層，依次類推。若某結(jié)點(diǎn)在第i層，則其子樹的根就在第i+1層。9.2.1樹及二叉樹的概念樹的一些基本術(shù)語：樹的深度：樹中結(jié)點(diǎn)的最大層次。又稱樹的高度。在圖9.11(b)所示的樹的深度為4。有序樹：樹中結(jié)點(diǎn)的各子樹看成從左至右是有次序的，則稱該樹為有序樹。在有序樹中最左邊的子樹的根稱為第一個(gè)孩子，最右邊的稱為最后一個(gè)孩子。無序樹：樹中結(jié)點(diǎn)的各子樹沒有次序的，孩子結(jié)點(diǎn)的順序可以調(diào)整。9.2.1樹及二叉樹的概念1.二叉樹的概念二叉樹是另一種樹型結(jié)構(gòu)，它的特點(diǎn)是每個(gè)結(jié)點(diǎn)至多有兩棵子樹（即二叉樹中不存在度大于2的結(jié)點(diǎn)），并且二叉樹的子樹有左右之分，其次序不能任意顛倒。二叉樹是n(n≥0)個(gè)結(jié)點(diǎn)的有限集，當(dāng)n>1時(shí)，有而僅有一個(gè)結(jié)點(diǎn)為根結(jié)點(diǎn)，其余結(jié)點(diǎn)構(gòu)成為2個(gè)互不相交的子集T1、T2，其中每一個(gè)子集又是一棵二叉樹，分別稱作為根結(jié)點(diǎn)的左子樹和右子樹。9.2.1樹及二叉樹的概念1.二叉樹的概念很顯然，這也是一個(gè)遞歸定義，值得注意的是：二叉樹不是度為2的樹，在度為2的樹中，當(dāng)一個(gè)結(jié)點(diǎn)的度為1時(shí)，其子樹是不考慮序的；而在二叉樹中，當(dāng)一個(gè)結(jié)點(diǎn)的度為1時(shí)，其子樹要考慮序，即是作為雙親的左子樹還是作為雙親的右子樹。另外，樹不允許為空樹，但二叉樹允許為空。9.2.1樹及二叉樹的概念1.二叉樹的概念由二叉樹的遞歸定義可知，二叉樹有五種基本形態(tài)，如圖9.13所示。9.2.1樹及二叉樹的概念和普通樹相比，二叉樹具有下列重要性質(zhì)：當(dāng)i=1時(shí)，只有一個(gè)根結(jié)點(diǎn)，2i-1=20=1，由于二叉樹的每一個(gè)結(jié)點(diǎn)的度最多為2，因此當(dāng)i≥2時(shí)，第i層上的結(jié)點(diǎn)數(shù)最多為上一層的2倍，所以第2層最多有2×1=21個(gè)結(jié)點(diǎn)，第3層最多有2×21=22個(gè)，依次類推，第i層最多有2×2i-1=2i個(gè)。性質(zhì)1：在二叉樹的第i層上的結(jié)點(diǎn)數(shù)最多為2i-1。9.2.1樹及二叉樹的概念和普通樹相比，二叉樹具有下列重要性質(zhì)：由性質(zhì)1可知，深度為k的二叉樹的最大結(jié)點(diǎn)數(shù)為1+2+4+……2k-1=i-1=2k-1性質(zhì)2：在深度為k的二叉樹中至多有2k-1個(gè)結(jié)點(diǎn)(k≥1)。9.2.1樹及二叉樹的概念和普通樹相比，二叉樹具有下列重要性質(zhì)：設(shè)在二叉樹中，度為1的結(jié)點(diǎn)為n1，樹的結(jié)點(diǎn)數(shù)n=n0+n1+n2。除根結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)有惟一的雙親結(jié)點(diǎn)指向該結(jié)點(diǎn)，所以度為1的結(jié)點(diǎn)指向一個(gè)后續(xù)，而度為2的結(jié)點(diǎn)指向兩個(gè)后續(xù)，根結(jié)點(diǎn)沒有指向的它雙親結(jié)點(diǎn)，因此，二叉樹結(jié)點(diǎn)數(shù)n=n1+2*n2+1。n=n0+n1+n2=n1+2*n2+1

可得n0=n2+1。性質(zhì)3：對(duì)于任何一個(gè)二叉樹T，若其葉子結(jié)點(diǎn)數(shù)為n0，度為2的結(jié)點(diǎn)數(shù)為n2，則n0=n2+1。9.2.1樹及二叉樹的概念在二叉樹中有兩種特殊的二叉樹——滿二叉樹和完全二叉樹。滿二叉樹：一棵深度為k的二叉樹，若其有2k-1個(gè)結(jié)點(diǎn)，則稱為滿二叉樹。在滿二叉樹中只有度為0和度為2的結(jié)點(diǎn)，并且在每一層上的結(jié)點(diǎn)數(shù)都是該層所能取結(jié)點(diǎn)的最大值。如圖9.14(a)所示為一個(gè)深度為4的滿二叉樹。9.2.1樹及二叉樹的概念在二叉樹中有兩種特殊的二叉樹——滿二叉樹和完全二叉樹。完全二叉樹：一個(gè)深度為k的二叉樹，其結(jié)點(diǎn)數(shù)n<2k-1，并且這n個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹，與一個(gè)深度為k的滿二叉樹的前n個(gè)結(jié)點(diǎn)的位置相同，則該樹是一棵深度為k的完全二叉樹。如圖9.14(b)為一個(gè)深度為4，結(jié)點(diǎn)數(shù)為10的完全二叉樹。9.2.1樹及二叉樹的概念完全二叉樹有兩個(gè)重要性質(zhì)：證明：假設(shè)深度為k，則根據(jù)性質(zhì)2和完全二叉樹的定義有2k-1-1<n≤2k-1或2k-1≤n<2k即k-1≤log2n<k由于k為整數(shù)，所有k=[log2n]+1.性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為[log2n]+1。9.2.1樹及二叉樹的概念完全二叉樹有兩個(gè)重要性質(zhì)：性質(zhì)5：如果對(duì)一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹（深度為[log2n]+1）的結(jié)點(diǎn)按順序標(biāo)號(hào)，標(biāo)號(hào)的順序從根開始，按層次自上而下，在第一層上從左至右，如圖9.14(b)所示的完全二叉樹，就是按此規(guī)則標(biāo)號(hào)，對(duì)于樹中任意標(biāo)號(hào)為I的結(jié)點(diǎn)有以下特性：i≠1時(shí)，i的雙親結(jié)點(diǎn)是[i/2]。若2i≤n，則i的左孩子是標(biāo)號(hào)為2i的結(jié)點(diǎn)；若2i>n，則該結(jié)點(diǎn)不存在左孩子。若2i+1≤n，則i的右孩子是標(biāo)號(hào)為2i+1的結(jié)點(diǎn)；若2i+1>n，則該結(jié)點(diǎn)不存在右孩子。9.2.2二叉樹的建立1.二叉樹的存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)和線性一樣，有兩種方式：順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)。(1)順序結(jié)構(gòu)可以設(shè)想把二叉樹中的各結(jié)點(diǎn)按一定次序排列成線性序，而且結(jié)點(diǎn)在這個(gè)序列中的相對(duì)位置能反映出結(jié)點(diǎn)之間的邏輯關(guān)系。然后分配一塊連續(xù)的存儲(chǔ)單元來存儲(chǔ)二叉樹。這種存儲(chǔ)方法對(duì)于滿二叉樹和完全二叉樹是非常適合的。9.2.2二叉樹的建立例如，對(duì)于圖9.15(a)的完全二叉樹，按層給結(jié)點(diǎn)編號(hào)可用圖9.15(c)的順序結(jié)構(gòu)來存儲(chǔ)。9.2.2二叉樹的建立對(duì)于圖9.15(b)的一般二叉樹，則可用圖9.15(d)所示的順序結(jié)構(gòu)來存儲(chǔ)。其中“0”表示該結(jié)點(diǎn)不存在。根據(jù)二叉樹性質(zhì)5，結(jié)點(diǎn)的編號(hào)（對(duì)應(yīng)順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)存放位置序號(hào)）中蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。例如，結(jié)點(diǎn)D（序號(hào)為4）的雙親為B（序號(hào)為4/2=2），左孩子為H（序號(hào)為4*2=8），右孩子為I（序號(hào)為4*2+1=9）。9.2.2二叉樹的建立例如，對(duì)于圖9.15(a)的完全二叉樹，按層給結(jié)點(diǎn)編號(hào)可用圖9.15(c)的順序結(jié)構(gòu)來存儲(chǔ)。對(duì)于圖9.15(b)的一般二叉樹，則可用圖9.15(d)所示的順序結(jié)構(gòu)來存儲(chǔ)。其中“0”表示該結(jié)點(diǎn)不存在。根據(jù)二叉樹性質(zhì)5，結(jié)點(diǎn)的編號(hào)（對(duì)應(yīng)順序存儲(chǔ)結(jié)構(gòu)中結(jié)點(diǎn)存放位置序號(hào)）中蘊(yùn)含著結(jié)點(diǎn)之間的關(guān)系。例如，結(jié)點(diǎn)D（序號(hào)為4）的雙親為B（序號(hào)為4/2=2），左孩子為H（序號(hào)為4*2=8），右孩子為I（序號(hào)為4*2+1=9）。9.2.2二叉樹的建立顯然，對(duì)于完全二叉樹，采用順序結(jié)構(gòu)存儲(chǔ)可節(jié)省空間。而對(duì)于一般二叉樹，則會(huì)造成空間的極大浪費(fèi)。可采用另一種有效的存儲(chǔ)結(jié)構(gòu)。9.2.2二叉樹的建立(2)二叉樹的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)定義兩種結(jié)點(diǎn)形式：二叉結(jié)點(diǎn)，有一個(gè)數(shù)據(jù)域和兩個(gè)分別指向左、右孩子的指針域；三叉結(jié)點(diǎn)，在二叉結(jié)點(diǎn)的基礎(chǔ)上，增加一個(gè)指向其雙親的指針域即一個(gè)數(shù)據(jù)域和三個(gè)指針域。對(duì)于二叉結(jié)點(diǎn)可描述如下：structbitree{charch;structbitree*lchild,*rchild;}三叉結(jié)點(diǎn)的結(jié)構(gòu)如下：structbitree{charch;srtuctbitree*lchild,*rchild,*parent;}9.2.2二叉樹的建立定義了二叉結(jié)點(diǎn)和三叉結(jié)點(diǎn)之后，相應(yīng)地可用二叉鏈表和三叉鏈表存儲(chǔ)、表示圖9.17(a)的二叉樹，如圖9.17(b)和圖9.17(c)所示。9.2.2二叉樹的建立用二叉鏈表存儲(chǔ)表示樹結(jié)構(gòu)時(shí)，由任一結(jié)點(diǎn)可方便地找到子孫，但難以直接找到其雙親。而用三叉鏈表存儲(chǔ)表示樹結(jié)構(gòu)卻可以方便地找到雙親結(jié)點(diǎn)，但卻需要額外的空間。實(shí)際應(yīng)用中主要用二叉鏈表結(jié)構(gòu)來存儲(chǔ)二叉樹。9.2.2二叉樹的建立2、二叉樹的建立在使用二叉樹之前必須先建立二叉樹，可以采用先序遍歷的順序進(jìn)行創(chuàng)建，并輸入數(shù)據(jù)，由鍵盤輸入每個(gè)節(jié)點(diǎn)的數(shù)據(jù)，假設(shè)當(dāng)輸入為“.”時(shí)，當(dāng)前操作的節(jié)點(diǎn)指針為NULL，采用先左子樹后右子樹的順序函數(shù)根據(jù)輸入數(shù)據(jù)的形式，生成相應(yīng)的二叉樹結(jié)構(gòu)。建立二叉樹的遞歸算法如下：建立二叉樹：voidcreat_tree(bitree&T,charch){charch;scanf(“%c”,&ch);if(ch=='.')T=NULL;else{T=newbitnode;T->data=ch;creat_tree(T->lchild,ch);creat_tree(T->rchild,ch);}}9.2.3二叉樹的遍歷由二叉樹的遞歸定義可知，二叉樹是由三個(gè)基本單元組成，即根結(jié)點(diǎn)、左子樹和右子樹。因此，若能依次遍歷出這三部分，便是遍歷了整個(gè)二叉樹。若以L，T，R分別表示遍歷左子樹、訪問根和遍歷右子樹，則可有六種遍歷方案：9.2.3二叉樹的遍歷六種遍歷方案：TLR，LTR，LRT，TRL，RTL，RLT。通常限定先遍歷左子樹，后遍歷右子樹。所以，二叉樹的遍歷主要指前三種，分別稱為先序遍歷、中序遍歷和后序遍歷。9.2.3二叉樹的遍歷二叉樹遍歷的遞歸定義。1.先序遍歷（TLR）算法先序遍歷（也可以稱為前序遍歷）二叉樹的操作定義為：若二叉為空，則空操作返回，否則：訪問根結(jié)點(diǎn)；先序遍歷左子樹；先序遍歷右子樹。先序遍歷的算法如下：voidprev(bitreeT){if(T!=NULL){printf(“%c”,T->data);prev(T->lchild);prev(T->rchi