構(gòu)建二叉樹的二叉鏈表存儲結(jié)構(gòu)

文章編號：1672-5913(2008)06-0066-03

摘要：本文根據(jù)筆者多年的教學(xué)經(jīng)驗，介紹了四種構(gòu)建二叉樹的二叉鏈表存儲結(jié)構(gòu)的方法。

關(guān)鍵詞：二叉樹；鏈表；存儲結(jié)構(gòu)；遞歸

中圖分類號：G642

文獻標識碼：B

1引言

《高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范》中將“計算機科學(xué)與技術(shù)”專業(yè)名稱下的人才培養(yǎng)規(guī)格歸納為三種類型、四個不同的專業(yè)方向：科學(xué)型(計算機科學(xué)專業(yè)方向)、工程型(包括計算機工程專業(yè)方向和軟件工程專業(yè)方向)、應(yīng)用型(信息技術(shù)專業(yè)方向)?！皵?shù)據(jù)結(jié)構(gòu)”課程出現(xiàn)在四個專業(yè)方向的核心課程中，而樹型結(jié)構(gòu)同樣無一例外的出現(xiàn)在了四個專業(yè)方向的核心知識單元中。

樹型結(jié)構(gòu)描述的是研究對象之間一對多的關(guān)系。在存儲樹時，如果用指針來描述元素之間的父子關(guān)系，則由于對每個元素的孩子數(shù)量沒有限制(最小可以是0，最多可以是樹的度d)，若結(jié)點的結(jié)構(gòu)定義為一個數(shù)據(jù)域data和d個指針域，則可以證明，有n個結(jié)點、度為d的樹的多重鏈表存儲結(jié)構(gòu)中，有n*(d-1)+1個空鏈域，采用這樣的存儲將造成很大的浪費。

二叉樹是樹型結(jié)構(gòu)的一種特殊情況，對于它的操作和存儲要比樹簡單的多，且樹和森林可以用二叉鏈表做媒介同二叉樹進行相互轉(zhuǎn)換，所以對二叉樹的研究就顯得特別重要。

二叉樹的二叉鏈表存儲是二叉樹的一種重要的存儲結(jié)構(gòu)，在每一本“數(shù)據(jù)結(jié)構(gòu)”教材中都占據(jù)了一定的篇幅，但對于怎樣建立一棵二叉樹的二叉鏈表存儲結(jié)構(gòu)，卻很少提及。筆者從事“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)已二十余年，總結(jié)出了以下四種構(gòu)建方法，希望能對同仁和學(xué)數(shù)據(jù)結(jié)構(gòu)的學(xué)生有所幫助。通過本文的學(xué)習(xí)，學(xué)生將會對二叉鏈表和遞歸有更深入的理解。

2二叉樹的二叉鏈表存儲結(jié)構(gòu)構(gòu)建方法

假設(shè)有關(guān)二叉樹的二叉鏈表存儲的類型定義如下：

typedef structBiTNode{ // 結(jié)點結(jié)構(gòu)

ElemTypedata ；//數(shù)據(jù)域

structBiTNode*Lchild ；//左孩子指針

structBiTNode*Rchild；//右孩子指針

} BiTNode ，*BiTree ；

說明：ElemType為二叉樹的元素值類型，根據(jù)具體情況進行定義，本文假設(shè)為char型；BiTNode為結(jié)點類型；BiTree為指向BiTNode的指針類型。下面的算法均用類C描述。

2.1利用擴展二叉樹的先序序列構(gòu)建

只根據(jù)二叉樹的先序序列是不能唯一確定一棵二叉樹的。針對這一問題，可做如下處理：對二叉樹中每個結(jié)點的空指針引出一個虛結(jié)點，設(shè)其值為#，表示為空，把這樣處理后的二叉樹稱為原二叉樹的擴展二叉樹。擴展二叉樹的先序序列可唯一確定這棵二叉樹。如圖1所示，給出了一棵二叉樹的擴展二叉樹，以及該擴展二叉樹的先序序列。

建立二叉鏈表的算法如下：

voidCreate(BiTreeT)

{//輸入擴展二叉樹的先序序列，構(gòu)建二叉鏈表

scanf(ch); //輸入一個元素

if (ch=='# ')T = NULL;

else

{ T= (BiTree)malloc(sizeof(BiTNode))；

//申請根結(jié)點

T->data =ch; // 給根結(jié)點數(shù)據(jù)域賦值

Create(T->Lchild);//建左子樹

Create(T->Rchild);//建右子樹

}

} // Create

2.2利用二叉樹的先序序列和中序序列

容易證明：由一棵二叉樹的先序序列和中序序列可唯一確定一棵二叉樹。

基本思想：先根據(jù)先序序列的第一個元素建立根結(jié)點；然后在中序序列中找到該元素，確定根結(jié)點的左、右子樹的中序序列；根據(jù)左、右子樹的中序序列確定左、右子樹中結(jié)點的個數(shù)；再根據(jù)結(jié)點個數(shù)在先序序列中確定左、右子樹的先序序列；最后由左子樹的先序序列與中序序列建立左子樹，由右子樹的先序序列與中序序列建立右子樹。

顯然，這是一個遞歸過程。假設(shè)先序序列放在數(shù)組pre[0..n-1]中，中序序列放在數(shù)組mid[0..n-1]中，n是二叉樹中元素的個數(shù)，其算法如下：

int Find(ElemType *P， int L2 ，int H2， ElemTypex)

{//在數(shù)組P的區(qū)間L2..H2內(nèi)確定x的位置

i=L2;

while(P[i]!=x) i++;

return i;

}// Find

void Create (BiTree T， int L1， int H1， int L2， int H2)

{//已知先序序列pre[L1..H1]，

//中序序列mid[L2..H2]構(gòu)建二叉鏈表

if (L2>H2)T=NULL; //建空樹

else

{ T =(BiTree)malloc(sizeof(BiTNode));

//創(chuàng)建根結(jié)點T

T ->data=pre[L1]; //給根數(shù)據(jù)域賦值

k=Find(mid， L2， H2， pre[L1]);

//找根在中序序列的位置

Create (T ->Lchild， L1+1，k+L1-L2， L2，k-1);

//創(chuàng)建左子樹

Create(T->Rchild，k+L1-L2+1，H1，k+1， H2);

//創(chuàng)建右子樹

}

}// Create

2.3利用擴展完全二叉樹的順序存儲

約定對二叉樹上的結(jié)點從根結(jié)點起，自上而下，自左而右進行連續(xù)編號，根結(jié)點的編號為1。深度為k的，有n個結(jié)點的二叉樹，當且僅當其每個結(jié)點的編號都與深度為k的滿二叉樹中編號為1至n中的結(jié)點一一對應(yīng)時，稱其為完全二叉樹。

如果一棵二叉樹不是完全二叉樹，可以用添加虛結(jié)點的方式將其擴展為一棵完全二叉樹。虛結(jié)點的值設(shè)為#，表示該結(jié)點不存在，把這樣處理后的二叉樹稱為原二叉樹的擴展完全二叉樹。如圖2中的(a)不是完全二叉樹，(b)為(a)的擴展完全二叉樹。

完全二叉樹的性質(zhì)：如果一棵完全二叉樹有n個結(jié)點，則有1)編號為i的結(jié)點如果有左孩子，則左孩子的編號為2i；2)如果有右孩子，則右孩子的編號為2i+1。

基本思想：

1) 將二叉樹擴展為一棵完全二叉樹；

2) 根據(jù)編號將結(jié)點的值依次放在數(shù)組s的s[1..n]中；

3) 根據(jù)完全二叉樹的性質(zhì)，構(gòu)造二叉樹的二叉鏈表存儲結(jié)構(gòu)。這里n為擴展完全二叉樹的結(jié)點個數(shù)，如圖2中的n為11。

對于第3)步，s[1]是二叉樹的根結(jié)點，如果2<=n則s[2]是s[1]的左孩子，否則左孩子為空；如果3<=n，則s[3]是s[1]的右孩子，否則右孩子為空；一般的，對于s[i]：

if (s[i]== '#' ) then 建空樹;

else { if (2i<=n) thens[2i]是s[i]的左孩子else 左孩子為空；

if (2i+1<=n) thens[2i+1]是s[i]的右孩子; else 右孩子為空; }

顯然，這是一個遞歸過程。其算法如下：

void Create (Bitree T ， ElemType *s， int i， int n)

{//創(chuàng)建一棵以s[i]值為根的值的二叉樹的二

//叉鏈表，樹的根為T

if(s[i]=='#')T =NULL;

else

{T =(BiTree)malloc(*sizeof(BiTNode));

//申請根結(jié)點

T ->data=s[i];

// 給根結(jié)點的數(shù)據(jù)域賦值

j=2*i;

if (j<=n)//創(chuàng)建左子樹

Create (T->Lchild ， s， j， n);

elseT->Lchild=NULL;

j++;

if(j<=n) //創(chuàng)建右子樹

Create (T ->Rchild ， s， j， n);

elseT ->Rchild=NULL;

}

}// Create

2.4利用二叉排序樹的性質(zhì)

基本思想：從一棵空二叉樹出發(fā)，按照先序序列依次插入各結(jié)點。假設(shè)先序列放在pre[1..n]中，中序序列放在mid[1..n]中，這里n是二叉樹的結(jié)點個數(shù)。pre[1]是樹的根，pre[i](i=2，3，…n)究竟插在左子樹上還是右子樹上，則要看pre[i]在中序序列中的位置，如果pre[i]在pre[1]的之前，則插入到左子樹上，否則插在右子樹上。為此可定義一個函數(shù)Find來確定結(jié)點在中序序列中的位置。

Find：pre[1..n]à1..n定義如下：

如果pre[i]=mid[j] 則 Find(pre[i])=j ；

這樣，對于pre[1..n]中的每個元素(即樹上的每個結(jié)點)都賦予了一個值，根據(jù)pre[1..n]和賦予每個元素pre[i](i=1，2…n)的Find(pre[i])值，按照構(gòu)造二叉排序樹的方法依次插入各結(jié)點，建立二叉樹。其算法如下：

int Find (ElemType *mid ， intn， ElemType x)

{//求x在中序序列中的位置

for( j=1;j<=n ; j++)

if(x==mid[j]) return j;

}// Find

void Insert_Node(Bitree T ， Bitrees)

{//將s插在以T為根的二叉樹的合適位置上

if (T==NULL) T=s; //在空樹上插入s

else

{ if(Find(T->data)>Find(s->data))

//將s所指結(jié)點插在左子樹上

Insert_Node(T->Lchild，s);

else //將s所指結(jié)點插在右子樹上

Insert_Node(T->Rchild，s);

}// Insert_Node

void Create (Bitree T， int n)

{//建有n個結(jié)點的二叉樹的二叉鏈表

T=NULL; //先建立一棵空樹

for(j=1;j<=n;j++)

{ //依次產(chǎn)生結(jié)點和插入結(jié)點

s= (BiTree)malloc(*sizeof(BiTNode));

s ->data=pre[j];

s->Lchild=NULL;

s->Rchild=NULL;

Insert_Node(T，s);//插入s

}

}// Create

參考文獻

[1] 教育部高等學(xué)校計算機科學(xué)與技術(shù)教學(xué)指導(dǎo)委員會. 高等學(xué)校計算機科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報告暨專業(yè)規(guī)范[R]. 北京:高等教育出版社，2006.

[2] 嚴蔚敏，吳偉民. 數(shù)據(jù)結(jié)構(gòu)(C語言版)[M]. 北京:清華大學(xué)出版社，1997：124-125，136.