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

1、構(gòu)建二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)文獻(xiàn)標(biāo)識(shí)碼：B1 引言高等學(xué)校計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)發(fā)展戰(zhàn)略研究報(bào)告暨專業(yè)規(guī)范中將“計(jì)算機(jī)科學(xué)與技術(shù)”專業(yè)名稱下的人才培養(yǎng)規(guī)格歸納為三種類型、四個(gè)不同的專業(yè)方向：科學(xué)型（計(jì)算機(jī)科學(xué)專業(yè)方向）、工程型（包括計(jì)算機(jī)工程專業(yè)方向和軟件工程專業(yè)方向）、應(yīng)用型（信息技術(shù)專業(yè)方向）。“數(shù)據(jù)結(jié)構(gòu)”課程出現(xiàn)在四個(gè)專業(yè)方向的核心課程中，而樹(shù)型結(jié)構(gòu)同樣無(wú)一例外的出現(xiàn)在了四個(gè)專業(yè)方向的核心知識(shí)單元中。樹(shù)型結(jié)構(gòu)描述的是研究對(duì)象之間一對(duì)多的關(guān)系。在存儲(chǔ)樹(shù)時(shí)，如果用指針來(lái)描述元素之間的父子關(guān)系，則由于對(duì)每個(gè)元素的孩子數(shù)量沒(méi)有限制（最小可以是0，最多可以是樹(shù)的度d），若結(jié)點(diǎn)的結(jié)構(gòu)定義為一個(gè)數(shù)據(jù)域d

2、ata和d個(gè)指針域，則可以證明，有n個(gè)結(jié)點(diǎn)、度為d的樹(shù)的多重鏈表存儲(chǔ)結(jié)構(gòu)中，有n*（d-1）+1個(gè)空鏈域，采用這樣的存儲(chǔ)將造成很大的浪費(fèi)。二叉樹(shù)是樹(shù)型結(jié)構(gòu)的一種特殊情況，對(duì)于它的操作和存儲(chǔ)要比樹(shù)簡(jiǎn)單的多，且樹(shù)和森林可以用二叉鏈表做媒介同二叉樹(shù)進(jìn)行相互轉(zhuǎn)換，所以對(duì)二叉樹(shù)的研究就顯得特別重要。二叉樹(shù)的二叉鏈表存儲(chǔ)是二叉樹(shù)的一種重要的存儲(chǔ)結(jié)構(gòu)，在每一本“數(shù)據(jù)結(jié)構(gòu)”教材中都占據(jù)了一定的篇幅，但對(duì)于怎樣建立一棵二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)，卻很少提及。筆者從事“數(shù)據(jù)結(jié)構(gòu)”課程教學(xué)已二十余年，總結(jié)出了以下四種構(gòu)建方法，希望能對(duì)同仁和學(xué)數(shù)據(jù)結(jié)構(gòu)的學(xué)生有所幫助。通過(guò)本文的學(xué)習(xí)，學(xué)生將會(huì)對(duì)二叉鏈表和遞歸有更深入的理

3、解。2 二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)構(gòu)建方法假設(shè)有關(guān)二叉樹(shù)的二叉鏈表存儲(chǔ)的類型定義如下：typedefstructBiTNode/結(jié)點(diǎn)結(jié)構(gòu)ElemTypedata；/數(shù)據(jù)域structBiTNode*Lchild；/左孩子指針structBiTNode*Rchild；/右孩子指針BiTNode，*BiTree；說(shuō)明：ElemType為二叉樹(shù)的元素值類型，根據(jù)具體情況進(jìn)行定義，本文假設(shè)為char型；BiTNode為結(jié)點(diǎn)類型；BiTree為指向BiTNode的指針類型。下面的算法均用類C描述。2.1 利用擴(kuò)展二叉樹(shù)的先序序列構(gòu)建只根據(jù)二叉樹(shù)的先序序列是不能唯一確定一棵二叉樹(shù)的。針對(duì)這一問(wèn)題，可做如下處

4、理：對(duì)二叉樹(shù)中每個(gè)結(jié)點(diǎn)的空指針引出一個(gè)虛結(jié)點(diǎn)，設(shè)其值為#，表示為空，把這樣處理后的二叉樹(shù)稱為原二叉樹(shù)的擴(kuò)展二叉樹(shù)。擴(kuò)展二叉樹(shù)的先序序列可唯一確定這棵二叉樹(shù)。如圖1所示，給出了一棵二叉樹(shù)的擴(kuò)展二叉樹(shù)，以及該擴(kuò)展二叉樹(shù)的先序序列。建立二叉鏈表的算法如下：voidCreate(BiTree&T)/輸入擴(kuò)展二叉樹(shù)的先序序列，構(gòu)建二叉鏈表scanf(&ch);/輸入一個(gè)元素if(ch='#')T=NULL;elseT=(BiTree)malloc(sizeof(BiTNode)；/申請(qǐng)根結(jié)點(diǎn)T->data=ch;/給根結(jié)點(diǎn)數(shù)據(jù)域賦值Create(T->Lchi

5、ld);/建左子樹(shù)Create(T->Rchild);/建右子樹(shù)/Create2.2 利用二叉樹(shù)的先序序列和中序序列容易證明：由一棵二叉樹(shù)的先序序列和中序序列可唯一確定一棵二叉樹(shù)?；舅枷耄合雀鶕?jù)先序序列的第一個(gè)元素建立根結(jié)點(diǎn)；然后在中序序列中找到該元素，確定根結(jié)點(diǎn)的左、右子樹(shù)的中序序列；根據(jù)左、右子樹(shù)的中序序列確定左、右子樹(shù)中結(jié)點(diǎn)的個(gè)數(shù)；再根據(jù)結(jié)點(diǎn)個(gè)數(shù)在先序序列中確定左、右子樹(shù)的先序序列；最后由左子樹(shù)的先序序列與中序序列建立左子樹(shù)，由右子樹(shù)的先序序列與中序序列建立右子樹(shù)。顯然，這是一個(gè)遞歸過(guò)程。假設(shè)先序序列放在數(shù)組pre0.n-1中，中序序列放在數(shù)組mid0.n-1中，n是二叉樹(shù)中元素

6、的個(gè)數(shù)，其算法如下：intFind(ElemType*P,intL2,intH2,ElemTypex)在數(shù)組P的區(qū)間L2.H2內(nèi)確定x的位置i=L2;while(Pi!=x)i+;returni;/FindvoidCreate(BiTree&T,intL1,intH1,intL2,intH2)/已知先序序列preL1.H1，/中序序列midL2.H2構(gòu)建二叉鏈表if(L2>H2)T=NULL;/建空樹(shù)elseT=(BiTree)malloc(sizeof(BiTNode);/創(chuàng)建根結(jié)點(diǎn)TT->data=preL1;/給根數(shù)據(jù)域賦值k=Find(mid,L2,H2,preL1

7、);/找根在中序序列的位置Create(T->Lchild,L1+1,k+L1-L2,L2,k-1);/創(chuàng)建左子樹(shù)Create(T->Rchild,k+L1-L2+1,H1,k+1,H2);/Create2.3 利用擴(kuò)展完全二叉樹(shù)的順序存儲(chǔ)約定對(duì)二叉樹(shù)上的結(jié)點(diǎn)從根結(jié)點(diǎn)起，自上而下，自左而右進(jìn)行連續(xù)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1。深度為k的，有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，當(dāng)且僅當(dāng)其每個(gè)結(jié)點(diǎn)的編號(hào)都與深度為k的滿二叉樹(shù)中編號(hào)為1至n中的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱其為完全二叉樹(shù)。如果一棵二叉樹(shù)不是完全二叉樹(shù)，可以用添加虛結(jié)點(diǎn)的方式將其擴(kuò)展為一棵完全二叉樹(shù)。虛結(jié)點(diǎn)的值設(shè)為#，表示該結(jié)點(diǎn)不存在，把這樣處理后的二叉樹(shù)稱

8、為原二叉樹(shù)的擴(kuò)展完全二叉樹(shù)。如圖2中的(a)不是完全二叉樹(shù)，(b)為(a)的擴(kuò)展完全二叉樹(shù)。完全二叉樹(shù)的性質(zhì)：如果一棵完全二叉樹(shù)有n個(gè)結(jié)點(diǎn)，則有1) 編號(hào)為i的結(jié)點(diǎn)如果有左孩子，則左孩子的編號(hào)為2i；2)如果有右孩子，則右孩子的編號(hào)為2i+1?；舅枷耄?) 將二叉樹(shù)擴(kuò)展為一棵完全二叉樹(shù)；2) 根據(jù)編號(hào)將結(jié)點(diǎn)的值依次放在數(shù)組s的s1.n中；3) 根據(jù)完全二叉樹(shù)的性質(zhì)，構(gòu)造二叉樹(shù)的二叉鏈表存儲(chǔ)結(jié)構(gòu)。這里n為擴(kuò)展完全二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)，如圖2中的n為11。對(duì)于第3)步，s1是二叉樹(shù)的根結(jié)點(diǎn)，如果2/創(chuàng)建一棵以si值為根的值的二叉樹(shù)的二/ 叉鏈表，樹(shù)的根為 Tif(si='#')T=N

9、ULL;elseT=(BiTree)malloc(*sizeof(BiTNode);/申請(qǐng)根結(jié)點(diǎn)T->data=si;/給根結(jié)點(diǎn)的數(shù)據(jù)域賦值j=2*i;if(jLchild,s,j,n);elseT->Lchild=NULL;j+;if(jRchild,s,j,n);elseT->Rchild=NULL;/Create2.4 利用二叉排序樹(shù)的性質(zhì)基本思想：從一棵空二叉樹(shù)出發(fā)，按照先序序列依次插入各結(jié)點(diǎn)。假設(shè)先序列放在pre1.n中，中序序列放在mid1.n中，這里n是二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù)。pre1是樹(shù)的根，prei(i=2,3,-n)究竟插在左子樹(shù)上還是右子樹(shù)上，則要看prei在

10、中序序列中的位置，如果prei在pre1的之前，則插入到左子樹(shù)上，否則插在右子樹(shù)上。為此可定義一個(gè)函數(shù)Find來(lái)確定結(jié)點(diǎn)在中序序列中的位置。Find:pre1.na1.n定義如下：如果prei=midj則Find(prei)=j；這樣，對(duì)于pre1.n中的每個(gè)元素(即樹(shù)上的每個(gè)結(jié)點(diǎn))都賦予了一個(gè)值，根據(jù)pre1.n和賦予每個(gè)元素prei(i=1,2門(mén))的Find(prei)值，按照構(gòu)造二叉排序樹(shù)的方法依次插入各結(jié)點(diǎn)，建立二叉樹(shù)。其算法如下：intFind(ElemType*mid,intn,ElemTypex)/求x在中序序列中的位置for(j=1;jdata)>Find(s->data)/將s所指結(jié)點(diǎn)插在左子樹(shù)上Insert_Node(T->Lchild,s);else/將s所指結(jié)點(diǎn)插在右子樹(shù)上Insert_Node(T->Rch