第九章查找※教學(xué)內(nèi)容：

靜態(tài)查找表(順序表,有序表,索引順序表)；動態(tài)查找表(二叉排序樹,平衡二叉樹,B-樹)的建立和查找；哈希表的建立，查找及分析順序查找，折半查找和索引查找的方法；二叉排序樹的構(gòu)造方法；二叉平衡樹的旋轉(zhuǎn)平衡方法；B-樹的建立過程；哈希表的構(gòu)造方法；計算各種查找方法在等概率情況下查找成功時和失敗時的平均查找長度※教學(xué)難點：

二叉平衡樹的旋轉(zhuǎn)平衡方法※教學(xué)重點：

何謂查找表？

查找表是由同一類型的數(shù)據(jù)元素(或記錄)構(gòu)成的集合。

由于“集合”中的數(shù)據(jù)元素之間存在著松散的關(guān)系，因此查找表是一種應(yīng)用靈便的結(jié)構(gòu)。對查找表經(jīng)常進(jìn)行的操作:1)查詢某個“特定的”數(shù)據(jù)元素是否在查找表中；2)檢索某個“特定的”數(shù)據(jù)元素的各種屬性；3)在查找表中插入一個數(shù)據(jù)元素；4)從查找表中刪去某個數(shù)據(jù)元素。

僅作查詢和檢索操作的查找表為靜態(tài)查找表。靜態(tài)查找表

有時在查詢之后，還需要將“查詢”結(jié)果為“不在查找表中”的數(shù)據(jù)元素插入到查找表中；或者，從查找表中刪除其“查詢”結(jié)果為“在查找表中”的數(shù)據(jù)元素,此類表為動態(tài)查找表。動態(tài)查找表查找表可分為兩類:關(guān)鍵字

用來標(biāo)識一個數(shù)據(jù)元素（或記錄）的某個數(shù)據(jù)項的值，稱為關(guān)鍵字。主關(guān)鍵字若此關(guān)鍵字可唯一地標(biāo)識一個記錄，則稱此關(guān)鍵字是主關(guān)鍵字；幾個概念:次關(guān)鍵字反之，用以識別若干記錄的關(guān)鍵字是次關(guān)鍵字。

根據(jù)給定的某個值，在查找表中確定一個其關(guān)鍵字等于給定值的數(shù)據(jù)元素或(記錄)。

查找

若查找表中存在這樣一個記錄，則稱“查找成功”。查找結(jié)果給出整個記錄的信息，或指示該記錄在查找表中的位置；

否則稱“查找不成功”。查找結(jié)果給出“空記錄”或“空指針”。關(guān)鍵字

用來標(biāo)識一個數(shù)據(jù)元素（或記錄）的某個數(shù)據(jù)項的值，稱為關(guān)鍵字。

由于查找表中的數(shù)據(jù)元素之間不存在明顯的組織規(guī)律，因此不便于查找。為了提高查找的效率，需要在查找表中的元素之間人為地附加某種確定的關(guān)系，換句話說，用另外一種結(jié)構(gòu)來表示查找表。如何進(jìn)行查找？

查找的方法取決于查找表的結(jié)構(gòu),即表中數(shù)據(jù)元素是依何種關(guān)系組織在一起的。9.1靜態(tài)查找表9.2動態(tài)查找樹表9.3哈希表第九章查找練習(xí)9.1靜態(tài)查找表數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系R：D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。

數(shù)據(jù)元素同屬一個集合。ADTStaticSearchTable{……基本操作P：}ADTStaticSearchTable抽象數(shù)據(jù)類型靜態(tài)查找表的定義：構(gòu)造一個含n個數(shù)據(jù)元素的靜態(tài)查找表ST。

Create(&ST,n);操作結(jié)果：銷毀表ST。Destroy(&ST);初始條件：操作結(jié)果：靜態(tài)查找表ST存在；基本操作P：若ST中存在其關(guān)鍵字等于

key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。

Search(ST,key);初始條件：操作結(jié)果：靜態(tài)查找表ST存在，key為和查找表中元素的關(guān)鍵字類型相同的給定值；按某種次序?qū)T的每個元素調(diào)用函數(shù)Visit()一次且僅一次，一旦Visit()失敗，則操作失敗。Traverse(ST,Visit());初始條件：操作結(jié)果：靜態(tài)查找表ST存在，Visit是對元素操作的應(yīng)用函數(shù)；typedefstruct{

//數(shù)據(jù)元素存儲空間基址，

//建表時按實際長度分配，0號單元留空

intlength;//表的長度}SSTable;假設(shè)靜態(tài)查找表的順序存儲結(jié)構(gòu)為ElemType*elem;數(shù)據(jù)元素類型的定義為:typedefstruct{keyTypekey;

//關(guān)鍵字域

……

//其它屬性域}

ElemType;宏定義（對兩個關(guān)鍵字的比較約定）

//對數(shù)值型關(guān)鍵字

#defineEQ(a,b)((a)==(b))#defineLT(a,b)((a)<(b))#defineLQ(a,b)((a)<=(b))

//對字符串型關(guān)鍵字

#defineEQ(a,b)(!strcmp((a),(b)))#defineLT(a,b)(strcmp((a),(b))<0)#defineLQ(a,b)(strcmp((a),(b))<=0)一、順序查找表二、有序查找表三、靜態(tài)查找樹表四、索引順序表一、順序查找表二、有序查找表三、索引順序表9.1靜態(tài)查找表

順序查找表是從頭開始，順序比較的查找表，可以以順序表或線性鏈表表示靜態(tài)查找表。我們以順序表為例說明順序查找表的查找方法。一、順序查找表ST.elem（1）回顧順序表的查找過程：假設(shè)給定值e=64,要求ST.elem[k]=e,問:k=?kkkintlocation(SqListL,ElemType&e,Status(*compare)(ElemType,ElemType)){k=1;p=L.elem;

while(k<=L.length

&&

!(*compare)(*p++,e))

k++;if(k<=L.length)returnk;

elsereturn0;}//location（2）從前往后查的算法觀察循環(huán)條件，判斷算法能改進(jìn)嗎？ST.elemiST.elemi60ikey=64key=60i64intSearch_Seq(SSTableST,KeyTypekey){//在順序表ST中順序查找其關(guān)鍵字等于key的數(shù)據(jù)元素。

//若找到，則函數(shù)值為該元素在表中的位置，否則為0

ST.elem[0].key=key;

//“哨兵”

for(i=ST.length;ST.elem[i].key!=key;

--i);

//從后往前找

returni;

//找不到時，i為0}//Search_Seq（3）從后往前查的算法

從后往前查的算法中，查找之前，把第0個元素設(shè)為查找元素key。這樣避免在查找過程中每一步都要檢測整個表是否查找完畢。ST.elem[0]起到了監(jiān)視哨的作用。上述程序技巧上的改進(jìn)，在查找表的長度>1000時，查找所需的平均時間減少一半。監(jiān)視哨也可設(shè)在高下標(biāo)處。

查找算法的平均查找長度ASL

(AverageSearchLength)（4）分析順序查找的時間性能

為確定記錄在表中的位置，需和給定值進(jìn)行比較的關(guān)鍵字次數(shù)的期望值稱為查找算法在查找成功時的平均查找長度。查找成功時的比較次數(shù)取決于關(guān)鍵字在表中的位置n+1。

查找不成功時的比較次數(shù)為：

對于含有n個數(shù)據(jù)元素的表,查找成功時的平均查找長度為:

nASL=ΣPiCi

i=1其中:Pi為查找第i個數(shù)據(jù)元素的概率,且

Ci為查到第i個數(shù)據(jù)元素時,需要進(jìn)行的比較次數(shù)在等概率查找的情況下，對順序表而言，Ci取決于所查元素所處的位置：ASL=nP1+(n-1)P2+…+2Pn-1+Pn1nn-i+1查找記錄是A[n]時,僅需比較

次;（從后往前查）查找記錄是A[1]時,要比較

次;查找記錄是A[i]時,要比較次.順序表查找成功的平均查找長度為：

若查找概率無法事先測定，則查找過程采取的改進(jìn)辦法是，采用調(diào)換技術(shù)，在每次查找之后，與后一個互換或直接移至表尾的位置上。在不等概率情況下，ASLss

取極小值的條件：≥PnPn-1

···

P2

P1≥≥≥

若順序查找采用鏈表結(jié)構(gòu)，時間性能與順序表相同，但只能從前往后查。順序查找表的優(yōu)點：

查找算法簡單，適用面廣，不要求有序，如果要插入可插在表尾。順序查找表的缺點：平均查找長度較大，n很大時效率比較低一、順序查找表二、有序查找表三、索引順序表9.1靜態(tài)查找表

順序查找表的查找算法簡單，但平均查找長度較大，特別不適用于表長較大的查找表。二、有序查找表

若以有序表表示靜態(tài)查找表，用順序查找時不用比較到表尾，但比較成功時的ASL與順序查找表相同，查找不成功時要好于順序表查找。這種方法稱為折半查找或二分查找如果查找表中的數(shù)據(jù)元素按關(guān)鍵字有序(假設(shè)遞增有序),則在查找時不必逐個順序比較,而采用跳躍的方式,逐漸縮小查找范圍先與“中間位置”的記錄關(guān)鍵字值比較,若相等則查找成功;若給定值大于“中間位置”的關(guān)鍵字值,則在后半部繼續(xù)進(jìn)行查找;否則在前半部進(jìn)行查找。ST.elemST.length例如:key=64

的查找過程如下：lowhighmidlow

mid

high

midlow

指示查找區(qū)間的下界high

指示查找區(qū)間的上界mid=(low+high)/2（對下取整）（2）折半查找算法設(shè)待查元素所在區(qū)域的下界為low,上界為hig,則中間位置mid=(low+hig)DIV2若中間位置元素值等于給定值,則查找成功;若中間位置元素值大于給定值,則在區(qū)域

[low，mid-1]進(jìn)行折半查找若中間位置元素值小于給定值,則在區(qū)域

[mid+1，hig]內(nèi)進(jìn)行折半查找intSearch_Bin(SSTableST,KeyTypekey){

low=1;high=ST.length;

//置區(qū)間初值

while(low<=high){mid=(low+high)/2;

if（EQ(key,ST.elem[mid].key))

returnmid;

//找到待查元素

elseif(LT(key,ST.elem[mid].key))

high=mid-1;//繼續(xù)在前半?yún)^(qū)間進(jìn)行查找

else

low=mid+1;

}//繼續(xù)在后半?yún)^(qū)間進(jìn)行查找

return0;

//順序表中不存在待查元素}//Search_Bin折半查找迭代算法(3)分析折半查找的時間性能（ASL)6391425781011上述查找過程可用二叉樹（判定樹）來描述。12233334444

判定樹中每個園結(jié)點（內(nèi)部結(jié)點）代表表中的一個記錄，園結(jié)點中的值代表該記錄在表中的位置。方形結(jié)點（外部結(jié)點）是人為增加的，表示查找不成功的情況。查找成功時的比較次數(shù)不超過判定樹的深度。比較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。查找不成功的過程是走了從根結(jié)點到外部結(jié)點的路徑（即樹的深度）。比較次數(shù)等于該路徑上結(jié)點個數(shù)。不超過

log2n」

+1判定樹中每個園結(jié)點（內(nèi)部結(jié)點）代表表中的一個記錄，園結(jié)點中的值代表該記錄在表中的位置。方形結(jié)點（外部結(jié)點）是人為增加的，表示查找不成功的情況。查找成功時的比較次數(shù)不超過判定樹的深度。比較次數(shù)等于該路徑上內(nèi)部結(jié)點的個數(shù)。查找不成功的過程是走了從根結(jié)點到外部結(jié)點的路徑（即樹的深度）。比較次數(shù)等于該路徑上結(jié)點個數(shù)。不超過log2n」

+1n個結(jié)點的判定樹的深度與n個結(jié)點的完全二叉樹的深度相同。

假設(shè)n=2h-1并且查找概率相等(Pi=1/n),則判定樹的深度為h的滿二叉樹。層次為h的結(jié)點有2h-1個。則查找成功時平均查找長度ASL為：在n>50時，可得近似結(jié)果折半查找的優(yōu)點：

顯然，折半查找效率比順序查找高。折半查找的缺點：

需要預(yù)先排序，只適合有序的順序表，不能是鏈表三、靜態(tài)查找樹表(╳)

當(dāng)有序表中各記錄的查找概率相等時，折半查找其性能最優(yōu)。在不等概率查找的情況下，折半查找情況如何？四索引順序表關(guān)鍵字:ABCDEPi:0.20.30.050.30.15Ci:23123

在不等概率查找的情況下，折半查找不是有序表最好的查找方法。例如:假設(shè)有序表中含5個記錄，并且已知各記錄的查找概率不等，此時ASL=20.2+30.3+10.05+20.3+30.15=2.4若改變Ci的值21323則ASL=20.2+10.3+30.05+20.3+30.15=1.9

這就說明，當(dāng)有序表中各記錄的查找概率不等時，折半查找性能未必是最優(yōu)的。那么，描述此類查找過程的判定樹為何類二叉樹時，其查找性能最佳？

如果只考慮查找成功的情況，則使查找性能達(dá)到最佳的判定樹是其帶權(quán)內(nèi)路徑長度之和PH值

nPH=∑wihi

i=1取最小值的二叉樹。其中：n為二叉樹上結(jié)點的個數(shù)；

hi為第i個結(jié)點在二叉樹上的層次數(shù)(比較次數(shù))wi為結(jié)點的權(quán)，且wi=cpi(i=1,2,…,n)

pi為結(jié)點的查找概率，c為某個常量稱PH值取最小的二叉樹為靜態(tài)最優(yōu)查找樹。

構(gòu)造靜態(tài)最優(yōu)查找樹花費的時間代價較高，在此不做討論，僅介紹構(gòu)造近似最優(yōu)查找樹——次優(yōu)查找樹的有效算法。

已知一個按關(guān)鍵字有序的記錄序列（rl,rl+1,…,rh)其中rl.key<ri+1

.key<…<rh

.key與每個記錄相應(yīng)的權(quán)值為

wl,wi+1,…,wh現(xiàn)構(gòu)造一棵二叉樹，使這棵二叉樹的帶權(quán)路徑長度PH值在所有具有同樣權(quán)值的二叉樹中近似為最小，稱這類二叉樹為次優(yōu)查找樹。次優(yōu)查找樹首先取第i（l≤i≤h）個記錄構(gòu)造根結(jié)點ri使得達(dá)最小然后分別對子序列{rl,rl+1,…,ri-1}

和{ri+1,…,rh}

構(gòu)造兩棵次優(yōu)查找樹，并分別設(shè)為根結(jié)點ri的左子樹和右子樹。次優(yōu)查找樹的構(gòu)造方法：為便于計算，引入累計權(quán)值和并設(shè)wl-1=0和swl-1=0，則推導(dǎo)可得023811151823例如:lh211812431018h9608EC21Ah53lhG3013ECGABDF所得次優(yōu)查找樹如下所示:

查找比較“總次數(shù)”

=3

2+41+25+33

+14+33+25=52

查找比較“總次數(shù)”

=3

2+21+35+13

+34+23+35=59和折半查找相比較DBACFEGStatusSecondOptimal(BiTree&T,ElemTypeR[],

floatsw[],intlow,inthigh){

//由有序表R[low..high]及其累計權(quán)值表sw//遞歸構(gòu)造次優(yōu)查找樹T。

選擇最小的ΔPi值

if(!(T=(BiTree)malloc(sizeof(BiTNode))))

returnERROR;

T->data=

R[i];

//生成結(jié)點構(gòu)造次優(yōu)查找樹的算法if

(i==low)T->lchild=NULL;

//左子樹空else

SecondOptimal(T->lchild,R,sw,low,i-1);

//構(gòu)造左子樹

if

(i==high)T->rchild=NULL;

//右子樹空

else

SecondOptimal(T->rchild,R,sw,i+1,high);

//構(gòu)造右子樹

returnOK;}//SecondOptimal次優(yōu)查找樹采用二叉鏈表的存儲結(jié)構(gòu)StatusCreateSOSTre(SOSTree&T,SSTableST){

//由有序表ST構(gòu)造一棵次優(yōu)查找樹T//ST的數(shù)據(jù)元素含有權(quán)域weight

if(ST.length=0)T=NULL;

else{FindSW(sw,ST);

//按照有序表ST中各數(shù)據(jù)元素

//的weight值求累計權(quán)值表

SecondOpiamal(T,ST.elem,sw,1,ST.length);

}

returnOK;}//CreatSOSTree一、順序查找表二、有序查找表三、索引順序表9.1靜態(tài)查找表三、索引順序表（分塊查找）（1）表中數(shù)據(jù)元素的特點若把所有n個數(shù)據(jù)元素分成m塊,第一塊中任一元素的關(guān)鍵字都小于第二塊中任一元素的關(guān)鍵字,第二塊中任一元素的關(guān)鍵字都小于第三塊中的任一元素的關(guān)鍵字...,第m-1塊中任一元素的關(guān)鍵字都小于第m塊中的任一元素的關(guān)鍵字,而每一塊中元素的關(guān)鍵字不一定是有序的。213343851782119433740313322256178735585索引順序查找示例將17,8,21,19,31,33,22,25,43,37,40,61,78,73,55,85分為4塊:[17,8,21,19],[31,33,22,25],[43,37,40],[61,78,73,55,85]以每塊中最大關(guān)鍵字作為該塊所有元素的索引指針指向塊起始地址索引表按關(guān)鍵字有序，包含兩項內(nèi)容：（1）索引關(guān)鍵字----其值為該子表（塊）內(nèi)的最大關(guān)鍵字（2）指針項----指示該子表的第一個記錄在表中的位置22488617132212138920334244382448605874498653索引表表最大關(guān)鍵字起始地址（2）索引順序查找算法①先抽出各塊中最大關(guān)鍵字構(gòu)成一個索引表；②查找分兩步進(jìn)行:(a)先對索引表進(jìn)行折半查找或順序查找,確定待查記錄在哪一塊。

(b)在已確定的那一塊中進(jìn)行順序查找。

可見，索引順序查找的過程是一個“縮小區(qū)間”的查找過程。索引順序表的查找過程：1）由索引確定記錄所在區(qū)間（塊）；2）在順序表的某個區(qū)間（塊）內(nèi)進(jìn)行查找。可見，

索引順序查找的過程也是一個“縮小區(qū)間”的查找過程。索引順序查找的平均查找長度=

查找“索引表”的平均查找長度Lb

+查找“順序子表”的平均查找長度Lw（3）索引順序表查找性能分析由此可見，索引順序表的平均查找長度與表長n和塊中記錄數(shù)s有關(guān)。當(dāng)s取時，ASL取最小值

假設(shè)長度為n的表均勻分成b塊，每塊含有s個記錄，即b=「n/s。假定每條記錄的查找概率相等，則每塊查找的概率為1/b，塊中每個記錄查找的概率為1/s,采用順序查找索引表+順序查找被確定的塊,其平均查找長度為:nASL=Lb+Lw=(b+1)/2+(s+1)/2=(n/s+s)/2+1n+1五、三種查找方法比較順序查找折半查找分塊查找ASL最大等概率最小次小表的結(jié)構(gòu)有序表、無序表均可僅適用于有序表表中元素逐段有序表的存儲結(jié)構(gòu)順序、鏈?zhǔn)浇Y(jié)構(gòu)均可僅適用于順序存儲順序、鏈?zhǔn)骄桑饕眄樞虼鎯?/p>

若有10000個記錄，順序查找大約比較5000次，折半查找大約比較14次，分塊查找大約比較101次。五、四種查找方法比較順序查找折半查找靜態(tài)樹表查找分塊查找平均查找長度最大等概率查找最小不等概率查找最小次小表的結(jié)構(gòu)有序表、無序表均可僅適用于有序表僅適用于有序表表中元素逐段有序表的存儲結(jié)構(gòu)順序、鏈?zhǔn)浇Y(jié)構(gòu)均可僅適用于順序存儲僅適用于順序存儲順序、鏈?zhǔn)骄桑饕眄樞虼鎯?/p>

(n)

(1)

(n)

(1)

(nlogn)綜合上一節(jié)討論的幾種查找表的特性：查找插入刪除無序順序表無序線性鏈表有序順序表有序線性鏈表靜態(tài)查找樹表

(n)

(n)

(logn)

(n)

(logn)

(1)

(1)

(n)

(1)

(nlogn)

(n)

(1)

(n)

(1)綜合上面討論的幾種查找表的特性：查找插入刪除無序順序表無序線性鏈表有序順序表有序線性鏈表

(n)

(n)

(logn)

(n)

(1)

(1)

(n)

(1)1)從查找性能看，最好情況能達(dá)

(logn)，此時要求表有序；2)從插入和刪除的性能看，最好情況能達(dá)

(1)，此時要求存儲結(jié)構(gòu)是鏈表。可得如下結(jié)論：9.2動態(tài)查找樹表動態(tài)查找表的特點：

表結(jié)構(gòu)本身是在查找過程中動態(tài)生成的，即對于給定值key，若表中存在其關(guān)鍵字等于key的記錄，則查找成功返回。否則，插入關(guān)鍵字等于key的記錄。ADTDynamicSearchTable{抽象數(shù)據(jù)類型動態(tài)查找表的定義如下：數(shù)據(jù)對象D：數(shù)據(jù)關(guān)系R：

數(shù)據(jù)元素同屬一個集合。D是具有相同特性的數(shù)據(jù)元素的集合。每個數(shù)據(jù)元素含有類型相同的關(guān)鍵字，可唯一標(biāo)識數(shù)據(jù)元素。InitDSTable(&DT)基本操作P：DestroyDSTable(&DT)SearchDSTable(DT,key);InsertDSTable(&DT,e);DeleteDSTable(&DT,key);TraverseDSTable(DT,Visit());}ADTDynamicSearchTable操作結(jié)果：構(gòu)造一個空的動態(tài)查找表DT。InitDSTable(&DT)銷毀動態(tài)查找表DT。DestroyDSTable(&DT)初始條件：操作結(jié)果：動態(tài)查找表DT存在；若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則函數(shù)值為該元素的值或在表中的位置，否則為“空”。SearchDSTable(DT,key)初始條件：操作結(jié)果：動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；動態(tài)查找表DT存在，e

為待插入的數(shù)據(jù)元素；InsertDSTable(&DT,e)初始條件：操作結(jié)果：若DT中不存在其關(guān)鍵字等于e.key

的數(shù)據(jù)元素，則插入e到DT。動態(tài)查找表DT存在，key為和關(guān)鍵字類型相同的給定值；DeleteDSTable(&DT,key)初始條件：操作結(jié)果：若DT中存在其關(guān)鍵字等于key的數(shù)據(jù)元素，則刪除之。動態(tài)查找表DT存在，Visit是對結(jié)點操作的應(yīng)用函數(shù)；TraverseDSTable(DT,Visit())初始條件：操作結(jié)果：按某種次序?qū)T的每個結(jié)點調(diào)用函數(shù)Visit()一次且至多一次。一旦Visit()失敗，則操作失敗。一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹9.2動態(tài)查找樹表四、B+樹一、二叉排序樹（二叉查找樹）二、二叉平衡樹三、B-樹四、B+樹五、鍵樹一、二叉排序樹(二叉查找樹)1．定義2．查找算法3．插入算法4．刪除算法5．查找性能的分析

(1)若它的左子樹不空，則左子樹上所有結(jié)點的值均小于根結(jié)點的值；1.二叉排序樹(BST樹)定義：

二叉排序樹或者是一棵空樹；或者是具有如下特性的二叉樹：

(3)它的左、右子樹也都分別是二叉排序樹。

(2)若它的右子樹不空，則右子樹上所有結(jié)點的值均大于根結(jié)點的值；503080209010854035252388例如:是二叉排序樹。66不

通常，取二叉鏈表作為二叉排序樹的存儲結(jié)構(gòu)typedefstruct

BiTNode

{

//結(jié)點結(jié)構(gòu)

structBiTNode*lchild,*rchild;

//左右孩子指針}BiTNode,*BiTree;TElemTypedata;2．二叉排序樹的查找算法：若給定值等于根結(jié)點的關(guān)鍵字，則查找成功；

2)

若給定值小于根結(jié)點的關(guān)鍵字，則

若二叉排序樹為空，則查找不成功；否則，

繼續(xù)在左子樹上進(jìn)行查找；3)若給定值大于根結(jié)點的關(guān)鍵字，則

繼續(xù)在右子樹上進(jìn)行查找。50308020908540358832例如:二叉排序樹查找關(guān)鍵字==50,505035,503040355090,50809095從上述查找過程可見，在查找過程中，生成了一條查找路徑：

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至關(guān)鍵字等于給定值的結(jié)點;或者

從根結(jié)點出發(fā)，沿著左分支或右分支逐層向下直至指針指向空樹為止。

——查找成功

——查找不成功算法描述如下：StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){

//在根指針

T

所指二叉排序樹中遞歸地查找其

//關(guān)鍵字等于key的數(shù)據(jù)元素，若查找成功，

//則返回指針

p

所指該數(shù)據(jù)元素的結(jié)點，并返回

//函數(shù)值為

TRUE;

}//SearchBST

…………

否則表明查找不成功，返回

//指針

p所指查找路徑上訪問的最后一個結(jié)點，

//并返回函數(shù)值為FALSE,指針

f

指向當(dāng)前訪問

//的結(jié)點的雙親，其初始調(diào)用值為NULLif(!T)elseif(EQ(key,T->data.key))

elseif

(LT(key,T->data.key))

else{p=f;returnFALSE;}

//查找不成功{p=T;returnTRUE;}//查找成功SearchBST(T->lchild,key,T,p);

//在左子樹中繼續(xù)查找SearchBST(T->rchild,key,T,p);

//在右子樹中繼續(xù)查找30201040352523fT設(shè)key=48fTfT22pfTfTTTTfffp

根據(jù)動態(tài)查找表的定義，“插入”操作在查找不成功時才進(jìn)行；3．二叉排序樹的插入算法

若二叉排序樹為空樹，則新插入的結(jié)點為新的根結(jié)點；否則，新插入的結(jié)點必為一個新的葉子結(jié)點，其插入位置由查找過程得到。StatusInsertBST(BiTree&T,ElemTypee){

//當(dāng)二叉排序樹中不存在關(guān)鍵字等于e.key的

//數(shù)據(jù)元素時，插入元素值為e的結(jié)點，并返

//回TRUE;否則，不進(jìn)行插入并返回FALSE

}//InsertBST……if

(!SearchBST(T,e.key,NULL,p))

{

}elsereturnFALSE;s=(BiTree)malloc(sizeof(BiTNode));

//為新結(jié)點分配空間s->data=e;s->lchild=s->rchild=NULL;if

(!p)T=s;

//插入s為新的根結(jié)點elseif(

LT(e.key,p->data.key))p->lchild=s;

//插入*s為*p的左孩子else

p->rchild=s;

//插入*s為*p的右孩子returnTRUE;

//插入成功(1)被刪除的結(jié)點是葉子；(2)被刪除的結(jié)點只有左子樹或者只有右子樹；(3)被刪除的結(jié)點既有左子樹，也有右子樹。4．二叉排序樹的刪除算法可分三種情況討論：

和插入相反，刪除在查找成功之后進(jìn)行，并且要求在刪除二叉排序樹上某個結(jié)點之后，仍然保持二叉排序樹的特性。50308020908540358832(1)被刪除的結(jié)點是葉子結(jié)點例如:被刪關(guān)鍵字=2088其雙親結(jié)點中相應(yīng)指針域的值改為“空”50308020908540358832(2)

被刪除的結(jié)點只有左子樹或者只有右子樹

其雙親結(jié)點的相應(yīng)指針域的值改為“指向被刪除結(jié)點的左子樹或右子樹”。被刪關(guān)鍵字=408050308020908540358832(3)被刪除的結(jié)點既有左子樹，也有右子樹4040以其中序前驅(qū)替代之，然后再刪除該前驅(qū)結(jié)點被刪結(jié)點前驅(qū)結(jié)點被刪關(guān)鍵字=50StatusDeleteBST(BiTree&T,KeyTypekey){

//若二叉排序樹T中存在其關(guān)鍵字等于key的

//數(shù)據(jù)元素，則刪除該數(shù)據(jù)元素結(jié)點，并返回

//函數(shù)值TRUE，否則返回函數(shù)值FALSEif(!T)returnFALSE;

//不存在關(guān)鍵字等于key的數(shù)據(jù)元素

else{}}//DeleteBST算法描述如下：

……if(EQ(key,T->data.key))

//找到關(guān)鍵字等于key的數(shù)據(jù)元素elseif(LT(key,T->data.key))

else{Delete(T);returnTRUE;}

DeleteBST(T->lchild,key);

//繼續(xù)在左子樹中進(jìn)行查找DeleteBST(T->rchild,key);

//繼續(xù)在右子樹中進(jìn)行查找voidDelete(BiTree&p){

//從二叉排序樹中刪除結(jié)點p，重接它左子樹或右子樹

if(!p->rchild){q=p;p=p->lchild;free(q);}//P只有左孩子

elseif(!p->lchild){q=p;p=p->rchild;free(q);}//P只有右孩子

else{}//P有左、右孩子

returnTRUE;}//Delete其中刪除操作過程如下所描述：……

//右子樹為空樹則只需重接它的左子樹q=p;p=p->lchild;free(q);pp//左子樹為空樹只需重接它的右子樹q=p;p=p->rchild;free(q);ppq=p;s=p->lchild;while(s->rchild){q=s;s=s->rchild;}//轉(zhuǎn)左，然后向右到盡頭，指向被刪結(jié)點P的直接前驅(qū)S//左右子樹均不空p->data=s->data;//直接前驅(qū)替代結(jié)點pssqp…q

if(q!=p)q->rchild=s->lchild;//重接*q的右子樹elseq->lchild=s->lchild;

//q=p表明P的左孩子S沒有右孩子，則p的左孩子

S就是p的直接前驅(qū)。重接*q的左子樹free(s);

s

q結(jié)論：⑴一個無序序列（10，18，3，8，12，2，7，3）可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程；⑵每次插入的新結(jié)點都是二叉排序樹的葉子結(jié)點，在進(jìn)行插入操作時，不必移動其它結(jié)點，僅需修改某個結(jié)點的指針由空變?yōu)榉强占纯伞＿@就相當(dāng)于在一個有序序列上插入一個元素而沒有移動其它元素。這個特性告訴我們，對于需要經(jīng)常插入和刪除記錄的有序表采用二叉排序樹結(jié)構(gòu)更為合適。5．查找性能的分析

對于每一棵特定的二叉排序樹，均可按照平均查找長度的定義來求它的ASL值，顯然，由值相同的n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的值不同，甚至可能差別很大。由關(guān)鍵字序列3，1，2，5，4構(gòu)造而得的二叉排序樹，由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，例如：2134535412ASL=（1+2+3+4+5）/5=3ASL=（1+2+3+2+3）/5=2.2

下面討論平均情況:

不失一般性，假設(shè)長度為

n

的序列中有k

個關(guān)鍵字小于第一個關(guān)鍵字，則必有n-k-1

個關(guān)鍵字大于第一個關(guān)鍵字,由它構(gòu)造的二叉排序樹n-k-1k的平均查找長度是n

和k的函數(shù)P(n,k)(0kn-1)。

假設(shè)n個關(guān)鍵字中任何一個出現(xiàn)在第一個位置的可能性相同，則含n個關(guān)鍵字的二叉排序樹的平均查找長度：在等概率查找的情況下，n-k-1k由此可類似于解差分方程，此遞歸方程有解：結(jié)論：⑴一個無序序列可以通過構(gòu)造一棵二叉排序樹而變成一個有序序列，構(gòu)造樹的過程即為對無序序列進(jìn)行排序的過程；⑵每次插入的新結(jié)點都是BST樹的葉子結(jié)點，插入時，不必移動其它結(jié)點，僅需修改指針即可。因此，對于需要經(jīng)常插入和刪除記錄的有序表采用二叉排序樹結(jié)構(gòu)更為合適。

(3)為避免構(gòu)成二叉樹時出現(xiàn)單枝情況，在生成過程中需要進(jìn)行平衡化處理二、二叉平衡樹1、何謂“二叉平衡樹”？3、二叉平衡樹的查找性能分析2、如何構(gòu)造“二叉平衡樹”?1、二叉平衡樹概念

又稱AVL樹。它或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：它的左子樹或右子樹都是平衡二叉樹，且左子樹和右子樹的深度之差的絕對值不超過1。平衡因子

二叉樹上任一結(jié)點的左子樹深度減去右子樹深度的差值，稱為此結(jié)點的平衡因子。

（2）特點：二叉平衡樹是二叉查找樹的另一種形式，其特點為：

樹中每個結(jié)點的左、右子樹深度之差的絕對值不大于1，即。例如:548254821是平衡樹不是平衡樹1100-110-1010-10010-100100平衡二叉樹不平衡的二叉樹2-2

構(gòu)造二叉平衡（查找）樹的方法是：在插入過程中，采用平衡旋轉(zhuǎn)技術(shù)。例如:依次插入的關(guān)鍵字為5,4,2,8,6,95424258665842向右旋轉(zhuǎn)一次先向右旋轉(zhuǎn)再向左旋轉(zhuǎn)2、構(gòu)造“二叉平衡樹”426589642895向左旋轉(zhuǎn)一次繼續(xù)插入關(guān)鍵字9

平衡旋轉(zhuǎn)處理只對最小不平衡子樹進(jìn)行。設(shè)a為插入結(jié)點而失去平衡的最小子樹根結(jié)點的指針（即a是離插入結(jié)點最近，并且平衡因子絕對值超過1的祖先結(jié)點）。

平衡旋轉(zhuǎn)的規(guī)律如下：（1）單向右旋轉(zhuǎn)平衡處理：在*a的左子樹根結(jié)點的左子樹上插入結(jié)點。642（2）單向左旋轉(zhuǎn)平衡處理：在*a的右子樹根結(jié)點的右子樹上插入結(jié)點。（3）雙向旋轉(zhuǎn)--先左后右--平衡處理：在*a的左子樹根結(jié)點的右子樹上插入結(jié)點。（4）雙向旋轉(zhuǎn)--先右后左--平衡處理：在*a的右子樹根結(jié)點的左子樹上插入結(jié)點。689596271010697152練習(xí)一下吧：建立平衡二叉樹（90，60，20，50，40，30，10，110，100，105）11010030402010105905060906020602090504090502060403060305040209010110100100603050402010901101051101006030402010105905090，60，20，50，40，30，10，110，100，105

在平衡樹上進(jìn)行查找的過程和二叉排序樹相同，因此，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的個數(shù)不超過平衡樹的深度。3、平衡樹的查找性能分析：

問：含n

個關(guān)鍵字的二叉平衡樹可能達(dá)到的最大深度是多少？n=0空樹最大深度為

0n=1最大深度為

1n=2最大深度為

2n=4最大深度為

3n=7最大深度為4先看幾個具體情況:反過來問，深度為

h

的二叉平衡樹中所含結(jié)點的最小值Nh

是多少？h=0N0=0h=1h=2h=3一般情況下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用歸納法可證得Nh=Fh+2-1而Fh≈

h／5其中=（1+5）／2

因此，在二叉平衡樹上進(jìn)行查找時，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的次數(shù)和log(n)

相當(dāng)。

由此推得，深度為

h

的二叉平衡樹中所含結(jié)點的最小值

Nh=

h+2/5-1。

反之，含有n

個結(jié)點的二叉平衡樹能達(dá)到的最大深度hn=log

(5(n+1))-2。

反過來問，深度為

h

的二叉平衡樹中所含結(jié)點的最小值Nh

是多少？h=0N0=0h=1h=2h=3一般情況下N1=1N2=2N3=4Nh=Nh-1+Nh-2+1利用歸納法可得

含有n

個結(jié)點的二叉平衡樹能達(dá)到的最大深度hn

≈log

n

因此，在二叉平衡樹上進(jìn)行查找時，查找過程中和給定值進(jìn)行比較的關(guān)鍵字的次數(shù)和log(n)

相當(dāng)。

BST樹和AVL樹適用于組織內(nèi)存中小規(guī)模的目錄，對于較大的存在外存上的數(shù)據(jù)，用它們組織索引是不合適的，例如當(dāng)文件記錄數(shù)為100000時，最多訪外17次。另外，雖然AVL樹不受輸入影響始終能保持O(

log(n))效率，但為保持平衡，在插入和刪除時導(dǎo)致太多調(diào)整樹結(jié)構(gòu)的操作。

能否樹又平衡，又不需要太多調(diào)整，又能降低樹高呢？小結(jié)三、B-樹1．定義2．查找過程3．插入操作4．刪除操作5．查找性能的分析1．B-樹的定義B-樹是一種平衡的多路查找樹，它在文件系統(tǒng)中很有用。

一棵m階的B-樹，或為空樹，或為滿足下列特性的m叉樹：①樹中每個結(jié)點至多有m棵子樹；②若根結(jié)點不是葉子結(jié)點，則至少有兩棵子樹；（至少含1個關(guān)鍵字）③除根之外的所有非終端結(jié)點至少有

m/2棵子樹。（至少含m/2-1個關(guān)鍵字）

④所有的非終端結(jié)點中包含下列信息數(shù)據(jù)

(n,A0,K1,A1,K2,A2,…,Kn,An)其中：Ki(i=1,2,…,n)為關(guān)鍵字，且Ki<Ki+1(i=1,…,n-1);

Ai(i=0,…,n)為指向子樹根結(jié)點的指針，且指針Ai-1所指子樹中所有結(jié)點的關(guān)鍵字均小于Ki(i=1,…,n),An所指子樹中所有結(jié)點的關(guān)鍵字均大于Kn,

n(m/2-1≤n≤m-1)為關(guān)鍵字的個數(shù)(或n+1為子樹個數(shù))。⑤所有的葉子結(jié)點都出現(xiàn)在同一層次上，并且不帶信息(查找失敗的結(jié)點，指向這些結(jié)點的指針為空)。

如圖所示為一棵4階的B-樹，其深度為3(不包括失敗結(jié)點）。

在

m

階的B-樹上，每個非終端結(jié)點可能含有：

n

個關(guān)鍵字Ki（1≤i≤n）n<m

n

個指向記錄的指針Di（1≤i≤n）

n+1

個指向子樹的指針Ai（0≤i≤n）多叉樹的特性B-樹的特性非葉結(jié)點中的多個關(guān)鍵字均自小至大有序排列，即：K1<K2<…<Kn；

Ai-1所指子樹上所有關(guān)鍵字均小于Ki；

Ai所指子樹上所有關(guān)鍵字均大于Ki；查找樹的特性平衡樹的特性

樹中所有葉子結(jié)點均不帶信息，且在樹中的同一層次上；

根結(jié)點或為葉子結(jié)點，或至少含有兩棵子樹（至少含1個關(guān)鍵字）；其余所有非葉子結(jié)點均至少含有

m/2

棵子樹（至少含

m/2

-1個關(guān)鍵字），至多含有m

棵子樹（最多含m-1個關(guān)鍵字）

；typedefstructBTNode{int

keynum;

//結(jié)點中關(guān)鍵字個數(shù)，結(jié)點大小

structBTNode*parent;

//指向雙親結(jié)點的指針

KeyTypekey[m+1];

//關(guān)鍵字向量（0號單元不用）

structBTNode*ptr[m+1];

//子樹指針向量

Record*recptr[m+1];

//記錄指針向量(0號單元不用)}BTNode,*BTree;

//B-樹結(jié)點和B-樹的類型B-樹結(jié)構(gòu)的C語言描述如下:

從根結(jié)點出發(fā)，沿指針?biāo)阉鹘Y(jié)點和在結(jié)點內(nèi)進(jìn)行順序（或折半）查找

兩個過程交叉進(jìn)行(查找包含兩個操作：在B-樹中找結(jié)點、在結(jié)點中找關(guān)鍵字)。2.查找過程：

若查找成功，則返回指向被查關(guān)鍵字所在結(jié)點的指針和關(guān)鍵字在結(jié)點中的位置；

若查找不成功，則返回插入位置。

如圖所示為一棵4階的B-樹，其深度為3。

例如:查找84,p,i=290p,i=1ptypedefstruct{

BTNode*pt;

//指向找到的結(jié)點的指針

inti;

//1..m，在結(jié)點中的關(guān)鍵字序號

inttag;

//標(biāo)志查找成功(=1)或失敗(=0)}Result;

//在B樹的查找結(jié)果類型假設(shè)返回的是如下所述結(jié)構(gòu)的記錄：ResultSearchBTree(BTreeT,KeyTypeK){

//在m階的B-樹T中查找關(guān)鍵字K,返回

//查找結(jié)果

(pt,i,tag)。若查找成功，則

//特征值tag=1,指針pt所指結(jié)點中第i個

//關(guān)鍵字等于K；否則特征值tag=0,等于

//K的關(guān)鍵字應(yīng)插入在指針pt所指結(jié)點

//中第i個關(guān)鍵字和第i+1個關(guān)鍵字之間}//SearchBTree……p=T;q=NULL;found=FALSE;i=0;

while(p&&!found){n=p->keynum;

i=Search(p,K);

//在p->key[1..n]中查找i，p->key[i]<=K<p->key[i+1]

if(i>0&&p->key[i]==K)found=TRUE;

else{q=p;p=p->ptr[i];}

//q是p的雙親,順指針繼續(xù)找

}

if(found)return

(p,i,1//查找成功

elsereturn

(q,i,0);

//查找不成功566212012

在m階B-樹上查找不成功之后，需進(jìn)行插入。顯然，關(guān)鍵字插入的位置必定在最下層的非葉子結(jié)點，有下列幾種情況：3．插入1)

插入后，該結(jié)點的關(guān)鍵字個數(shù)n<m，

不修改指針;

如圖所示為一棵4階的B-樹。2)

插入后，該結(jié)點的關(guān)鍵字個數(shù)n=m，則需進(jìn)行“結(jié)點分裂”，令s=

m/2

，在原結(jié)點中保留

（A0，K1，……，Ks-1，As-1）；建新結(jié)點

（As，Ks+1，……，Kn，An）；

將（Ks，p）插入雙親結(jié)點；3)

若雙親為空，則建新的根結(jié)點。（算法見P244）例如:下列為3階B-樹50

20

40

80

插入關(guān)鍵字=

60,

60

80

90,

60

80

90

90

5080

60

30,

40

20

3050808030

50

和插入的考慮相反，首先必須找到待刪關(guān)鍵字所在結(jié)點，并且要求刪除之后，結(jié)點中關(guān)鍵字的個數(shù)不能小于

m/2

-1，否則，要從其左(或右)兄弟結(jié)點“借調(diào)”關(guān)鍵字，若其左和右兄弟結(jié)點均無關(guān)鍵字可借(結(jié)點中只有最少量的關(guān)鍵字)，則必須進(jìn)行結(jié)點的“合并”。4．刪除3階B-樹刪除關(guān)鍵字=

12,

45,53,245390374531261705010050536170361703732410061705090練習(xí)一下吧：試從空樹開始，建立3階B-樹（27，36，50，58，60，68，79）50273658686079（27，36，50，58，60，68，79）27365027503650585058605060273658606860687950273658686079刪58502736586860796068793660

在B-樹中進(jìn)行查找時，其查找時間花費在搜索結(jié)點（訪問外存）和在結(jié)點內(nèi)找關(guān)鍵字（訪問內(nèi)存）上，主要花費在搜索結(jié)點上。磁盤上查找結(jié)點的次數(shù)取決于B-樹的深度。即主要取決于B-樹的深度。5．查找性能的分析問：含N個關(guān)鍵字的m階B-樹可能達(dá)到的最大深度H

為多少？第2層先推導(dǎo)每一層所含最少結(jié)點數(shù)：第1層第H+1層第4層第3層反過來問:深度為H的m階B-樹中至少含有多少個結(jié)點？

……1個2個2

m/2

個2

(

m/2

)2個2

(

m/2

)H-1個root1538202643

假設(shè)m

階B-樹的深度為

H+1，由于第H+1層為葉子結(jié)點，而當(dāng)前樹中含有N

個關(guān)鍵字，則葉子結(jié)點必為

個，N+12(

m/2

)H-1由此可推得下列結(jié)果：N+1≥H-1≤log

m/2

((N+1)/2)H≤log

m/2

((N+1)/2)+1

在含N

個關(guān)鍵字的B-樹上進(jìn)行一次查找，需訪問的結(jié)點個數(shù)不超過

log

m/2

((N+1)/2)+1結(jié)論：是B-樹的一種變型四、B+樹1．B+樹的結(jié)構(gòu)特點：(1)

每個葉子結(jié)點中含有n

個關(guān)鍵字和n

個指向記錄的指針；(2)

每個非葉子結(jié)點可看成是索引部分，其中的關(guān)鍵字

Ki

即為其相應(yīng)指針

Ai所指子樹中關(guān)鍵字的最大值；(4)所有葉子結(jié)點包含了全部關(guān)鍵字信息，以及指向含這些關(guān)鍵字記錄的指針，都處在同一層次上，所有葉子結(jié)點彼此相鏈接構(gòu)成一個有序鏈表(按關(guān)鍵字從小到大）。每個葉子結(jié)點中關(guān)鍵字的個數(shù)均介于

m/2

和m之間。(3)有兩個頭指針，其一指向根結(jié)點，另一頭指針指向含最小關(guān)鍵字的葉子結(jié)點。

5096

1550627896

7178848996566220264350

3815sqroot指向記錄的指針哈希表4階B+樹示例：2．查找過程

(1)在B+樹上，既可以進(jìn)行隨機(jī)查找(從根指針起)，也可以順序查找(從最小關(guān)鍵字指針起)；

(2)在進(jìn)行查找時，不管成功與否，都必須查到葉子結(jié)點才能結(jié)束；(即非終端結(jié)點上的關(guān)鍵字等于給定值時不終止)

(3)若在結(jié)點內(nèi)查找時，給定值≤Ki，則應(yīng)繼續(xù)在Ai所指子樹中進(jìn)行查找。哈希表3．插入和刪除的操作

類似于B-樹進(jìn)行，插入與刪除僅在葉子結(jié)點進(jìn)行，必要時，也需要進(jìn)行結(jié)點的“分裂”或“歸并”。哈希表五、鍵樹（×）1.

鍵樹2.

.雙鏈樹3.Trie樹哈希表

鍵樹又稱數(shù)字查找樹，它是一棵度≥2的樹，樹中的每個結(jié)點中不是包含一個或幾個關(guān)鍵字，而是只含有組成關(guān)鍵字的符號。鍵樹表示集合、子集、元素之間的層次關(guān)系。例如，若關(guān)鍵字是數(shù)值，則結(jié)點中只包含一個數(shù)位；若關(guān)鍵字是單詞，則結(jié)點中只包含一個字母字符。1.

鍵樹(1)鍵樹的結(jié)構(gòu)特點：

（a）關(guān)鍵字中的各個符號分布在從根結(jié)點到葉子的路徑上(即根到葉子結(jié)點路徑上結(jié)點的字符組成的字符串為關(guān)鍵字)，葉子結(jié)點內(nèi)的符號為“結(jié)束”的標(biāo)志符$。因此，鍵樹的深度和關(guān)鍵字集合的大小無關(guān)；

（b）鍵樹被約定為是一棵有序樹，即同一層中兄弟結(jié)點之間依所含符號自左至右有序，并約定結(jié)束符‘$’小于任何其它符號。HAD$S$VE$E$R$E$IGH$S$例如:表示關(guān)鍵字集合{HAD,HAS,HAVE,HE,HER,HERE,HIGH,HIS}(2)鍵樹的存儲結(jié)構(gòu)鍵樹有兩種存儲結(jié)構(gòu)：以樹的孩子兄弟鏈表（二叉鏈表）表示鍵樹------稱為雙鏈樹(b)以樹的多重鏈表表示鍵樹------稱為

Trie樹2.雙鏈樹—以二叉鏈表作存儲結(jié)構(gòu)實現(xiàn)的鍵樹typedefenum{

LEAF,

BRANCH

}NodeKind;

//兩種結(jié)點：{葉子和

分支}（1）結(jié)點結(jié)構(gòu):first

symbol

next分支結(jié)點infoptr

symbol

next葉子結(jié)點指向孩子結(jié)點的指針指向兄弟結(jié)點的指針指向記錄的指針NULL

H

AD$HADE$R$$ES$GH$I

HEHERHEREHIGHHIS…T

葉子結(jié)點分支結(jié)點含關(guān)鍵字的記錄typedefstructDLTNode{charsymbol;

structDLTNode*next;

//指向兄弟結(jié)點的指針

NodeKindkind;

union{Record*infoptr;

//葉子結(jié)點內(nèi)的記錄指針

structDLTNode*first;

//分支結(jié)點內(nèi)的孩子鏈指針

}

}DLTNode,*DLTree;

//雙鏈樹的類型#defineMAXKEYLEN16

//關(guān)鍵字的最大長度typedefstruct{charch[MAXKEYLEN];//關(guān)鍵字

intnum;//關(guān)鍵字長度}KeysType;