數(shù)據(jù)結(jié)構(gòu)殷人昆培訓(xùn)課件

數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆1數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆2數(shù)據(jù)結(jié)構(gòu)清華大學(xué)殷人昆2樹的定義與基本概念二叉樹二叉樹遍歷二叉樹的計數(shù)線索二叉樹樹與樹的遍歷樹的應(yīng)用第4章樹與二叉樹樹的定義與基本概念第4章樹與二叉樹樹和森林的概念樹的定義

樹是由n(n＞0)個結(jié)點組成的有限集合：有一個特定的稱之為根(root)的結(jié)點；除根以外的其它結(jié)點劃分為m(m≥0)個互不相交的有限集合T1,T2,…,Tm，每個集合又是一棵樹，并且稱之為根的子樹。此定義是離散數(shù)學(xué)和圖論中給出的。它們把樹視為圖的一個極小連通子圖。有n個結(jié)點的樹有n-1條邊，而且不能有回路。樹和森林的概念樹的定義這種觀點的典型代表是

Knuth。他認(rèn)為圖至少有一個頂點，樹也必須至少有一個頂點。樹不能是空樹，但N叉樹可以是空樹。N叉樹是限制根的子樹最多不能超過N棵的樹。隨著對樹討論的深入，人們放寬了對樹結(jié)構(gòu)的限制。若把樹當(dāng)作層次結(jié)構(gòu)單獨對待，樹中允許結(jié)點個數(shù)為0。這樣，樹與N叉樹就沒有不可逾越的鴻溝了。從面向?qū)ο笥^點，N叉樹是樹的特殊實現(xiàn)：樹是父類，N叉樹是子類。N叉樹繼承了樹的特性，它還有自己增加的特性，例如這種觀點的典型代表是Knuth。他認(rèn)為圖至少有一個頂點，樹理論上樹不可是空樹，N叉樹可以是空樹；樹的子樹可以有序，也可以不要求有序，而N叉樹的子樹必須有序。N叉樹的定義也是遞歸的，遞歸到空樹終止；樹則遞歸到只有一個結(jié)點的子樹。樹的子樹棵數(shù)不限，而N叉樹中根的子樹最多N棵。樹可以區(qū)分為外向樹和內(nèi)向樹，而N叉樹一般是外向樹，即邊是有向的，從父指向子。樹可以用N叉樹實現(xiàn)。二叉樹、B樹等又都是N叉樹的特殊情形。理論上樹不可是空樹，N叉樹可以是空樹；樹的特點樹是分層結(jié)構(gòu)，又是遞歸結(jié)構(gòu)。每棵子樹的根結(jié)點有且僅有一個直接前驅(qū)，但可以有0個或多個直接后繼。1層2層4層3層depth=4height=4ACGBDEFKLHMIJ前驅(qū)后繼樹的特點樹是分層結(jié)構(gòu)，又是遞歸結(jié)構(gòu)。每棵子樹的根結(jié)點有且僅有1層2層4層3層depth=4height=4ACGBDEFKLHMIJ結(jié)點結(jié)點的度分支結(jié)點葉結(jié)點子女雙親兄弟祖先樹的度樹深度樹高度森林子孫結(jié)點層次結(jié)點深度結(jié)點高度1層2層4層3層depth=4ACGBDEFKLHMIJ注意，結(jié)點的深度和結(jié)點的高度是不同的。結(jié)點的深度即結(jié)點所處層次，是從根向下逐層計算的；結(jié)點的高度是從下向上逐層計算的：葉結(jié)點的高度為1,其他結(jié)點的高度是取它的所有子女結(jié)點最大高度加一。樹的深度與高度相等。 樹的深度按離根最遠(yuǎn)的 葉結(jié)點算，樹的高度按 根結(jié)點算，都是6。葉結(jié)點也稱為終端結(jié)點， 非葉結(jié)點也稱為非終端 結(jié)點。ABCDEFGHILKJ高度=4深度=3注意，結(jié)點的深度和結(jié)點的高度是不同的。結(jié)點的深度即結(jié)點所處層二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree)二叉樹的定義 一棵二叉樹是結(jié)點的一個有限集合，該集合或者為空，或者是由一個根結(jié)點加上兩棵分別稱為左子樹和右子樹的、互不相交的二叉樹組成。這個定義是遞歸的。二叉樹的五種不同形態(tài)LLRR二叉樹(BinaryTree二叉樹的性質(zhì)性質(zhì)1

若二叉樹的層次從1開始,則在二叉樹的第i層最多有2i-1

個結(jié)點。(i≥1)[證明用數(shù)學(xué)歸納法]i=1時，根結(jié)點只有1個，21-1=20=1；若設(shè)i=k

時性質(zhì)成立，即該層最多有2k-1

個結(jié)點，則當(dāng)i=k+1時，由于第k

層每個結(jié)點最多可有2個子女，第k+1層最多結(jié)點個數(shù)可有2*2k-1=2k

個，故性質(zhì)成立。二叉樹的性質(zhì)性質(zhì)1性質(zhì)2高度為h的二叉樹最多有2h

-1個結(jié)點。(h≥1)[證明用求等比級數(shù)前k項和的公式] 高度為h的二叉樹有h

層，各層最多結(jié)點個數(shù)相加，得到等比級數(shù)，求和得： 20+21+22+…+2h-1=2h-1

空樹的高度為0，只有根結(jié)點的樹的高度為1。性質(zhì)2性質(zhì)3

對任何一棵二叉樹,如果其葉結(jié)點有n0

個,度為2的非葉結(jié)點有n2

個,則有

n0＝n2＋1證明： 若設(shè)度為1的結(jié)點有n1個，總結(jié)點個數(shù)為n，總邊數(shù)為e，則根據(jù)二叉樹的定義，

n=n0+n1+n2e=2n2+n1=n-1 因此，有2n2+n1=n0+n1+n2-1 n2=n0-1n0=n2+1

引申：可用于判斷二叉樹各類結(jié)點個數(shù)。性質(zhì)34.1.2安全生產(chǎn)管理的基本知識、方法與安全生產(chǎn)，有關(guān)行業(yè)安全生4．注意眼神【案例】服務(wù)是一種行動，是做出來能夠使顧客感受得到的東西。提升服務(wù)者的心理素質(zhì)，使他們主動、積極、熱忱、開放，才能為客戶提供貼心服務(wù)。通過潛能激發(fā)訓(xùn)練可以提升服務(wù)者的心理素質(zhì)，包括觀念、心態(tài)和行為技術(shù)的改進(jìn)和提高。3.1經(jīng)評標(biāo)委員會評議認(rèn)定有下列情形之一的，屬于投標(biāo)人相互串通投標(biāo)：（4）本標(biāo)書第二章“前附表”中規(guī)定的其他驗收方式。4.7.3崗位安全操作規(guī)程，生產(chǎn)設(shè)備、安全裝置、勞動防護(hù)用品的性能及正確使用方法，事故案例27.4招標(biāo)代理機構(gòu)將按本須知第27.2條的內(nèi)容作開標(biāo)記錄，存檔備查。10.6在質(zhì)量保證期內(nèi)，如果發(fā)現(xiàn)由于賣方責(zé)任造成貨物的質(zhì)量或規(guī)格與合同不符，或證實貨物是有缺陷的，包括潛在的缺陷或使用不符合要求的材料等，或由于賣方技術(shù)文件錯誤或賣方人員在安裝、調(diào)試、試運行和驗收過程中錯誤指導(dǎo)而導(dǎo)致貨物損壞，買方可以根據(jù)本合同的規(guī)定以書面形式向賣方提出補救措施或索賠。32.1評標(biāo)委員會在初審時將檢查其報價是否有算術(shù)錯誤，對價格的算術(shù)錯誤按下述原則修正。修正后的結(jié)果對投標(biāo)人有約束力，如投標(biāo)人不接受修正后的結(jié)果，則其投標(biāo)將被拒絕，投標(biāo)保證金將不予退還。定義1

滿二叉樹(FullBinaryTree)定義2

完全二叉樹(CompleteBinaryTree)若設(shè)二叉樹的高度為h，則共有h

層。除第

h

層外，其它各層(1～h-1)的結(jié)點數(shù)都達(dá)到最大個數(shù)，第h

層從右向左連續(xù)缺若干結(jié)點，這就是完全二叉樹。4.1.2安全生產(chǎn)管理的基本知識、方法與安全生產(chǎn)，有關(guān)行業(yè)安性質(zhì)4 具有n(n≥0)個結(jié)點的完全二叉樹的高度為 log2(n+1)

證明：設(shè)完全二叉樹的高度為h，則有

2h-1-1＜n

≤2h-1

上面h-1層結(jié)點數(shù)

包括第h層的最大結(jié)點數(shù)變形 2h-1＜n+1≤2h

取對數(shù)

h-1＜log2(n+1)≤h

有 h=log2(n+1)

23-124-1性質(zhì)423-124-123-124-1注意：求高度的另一公式為log2n+1,此公式對于n=0不適用。若設(shè)完全二叉樹中葉結(jié)點有n0

個,則該二叉樹總的結(jié)點數(shù)為n=2n0,或n=2n0–1。若完全二叉樹的結(jié)點數(shù)為奇數(shù)，沒有度為1的結(jié)點；為偶數(shù)，有一個度為1的結(jié)點。右圖為理想平衡樹， 上層都是滿的，第

h層結(jié)點分布在各 處。23-124-1注意：性質(zhì)5

如將一棵有n個結(jié)點的完全二叉樹自頂向下，同一層自左向右連續(xù)給結(jié)點編號:0,1,2,…,n-1，則有以下關(guān)系：若i=0,則i無雙親； 若i>0,則i的雙親為(i-1)/2。若2*i+1<n,則

i

的左子女為2*i+1； 若2*i+2<n,則i的右子女為2*i+2。若i

為偶數(shù),且i!=0,則 其左兄弟為i-1； 若i

為 奇數(shù),且i!=n-1,

則其右兄弟為i+1。0123745689性質(zhì)50123745689注意：

如果完全二叉樹各層次結(jié)點從1開始編號：1,2,3,…,n，則有以下關(guān)系：若i=1,則i

無雙親； 若i>1,則i的雙親為i/2。若2*i<=n,則i的左子女為2*i； 若2*i+1<=n,則i的右子女為2*i+1若i

為奇數(shù),且i!=1,

則其左兄弟為i-1； 若i為偶數(shù),且i!=n,

則其右兄弟為i+1。12348567910注意：12348567910完全二叉樹一般二叉樹的順序表示的順序表示00123456789130123567811131378945620126537811491012二叉樹的順序表示完全二叉樹一般二叉樹00123402614300261430極端情形:只有右單支的二叉樹對于完全二叉樹，因結(jié)點編號連續(xù)，數(shù)據(jù)存儲密集，適于用順序表示；對于一般二叉樹，用鏈表表示較好；02614300261430極端情形:只有右單支的二叉樹對lchilddatarchilddatalchildrchild左子女指針右子女指針二叉樹的二叉鏈表表示使用二叉鏈表，找子女的時間復(fù)雜度為O(1)，找雙親的時間復(fù)雜度為O(log2i)～O(i)，其中，i

是該結(jié)點編號。lchilddatarchilddalchilddataparentrchildparentdatalchildrchild左子女指針雙親指針右子女指針二叉樹的三叉鏈表表示使用三叉鏈表，找子女、雙親的時間都是O(1)。lchilddataparentrAAABBBCCCDDDFFFEEErootrootroot二叉樹二叉鏈表三叉鏈表二叉樹鏈表表示的示例AAABBBCCCDDDFFF二叉樹的定義typedefcharTElemType; //樹結(jié)點數(shù)據(jù)類型typedefstructnode{ //樹結(jié)點定義

TElemType

data; //結(jié)點數(shù)據(jù)域

structnode*lchild,*rchild;

//子女指針域}BiTNode;typedefBiTNode*BinTree;

//樹定義，代表樹的根指針

二叉樹的定義typedefcharTElemType;二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點訪問一次且僅訪問一次。設(shè)訪問根結(jié)點記作V，遍歷根的左子樹記作L，遍歷根的右子樹記作R，則可能的遍歷次序有前序VLR鏡像VRL中序LVR鏡像RVL后序LRV鏡像RLV二叉樹遍歷樹的遍歷就是按某種次序訪問樹中的結(jié)點，要求每個結(jié)點20.3為買方方便而終止合同3．手部的修飾與保養(yǎng)4.1禁止敲擊，正確操作。充裝可燃?xì)怏w的氣瓶注意防止產(chǎn)生靜電，開關(guān)瓶閥時不得用鐵扳手等敲擊。高壓氣瓶開閥時應(yīng)緩慢開啟。(1)按“競爭性磋商響應(yīng)人競爭性磋商響應(yīng)前須知”注明的時間、地址送達(dá)；做好服務(wù)技巧的強化訓(xùn)練，要從以下幾個方面入手：9.4.4成交供應(yīng)商未按磋商文件要求交納履約保證金的；7.3競爭性磋商響應(yīng)幣種為人民幣10.1采購代理機構(gòu)應(yīng)當(dāng)在評審結(jié)束后2個工作日內(nèi)將評審報告送采購人確認(rèn)。5.1貨物交貨地點及時間見本標(biāo)書第二章“前附表”中的相關(guān)規(guī)定。7.3做好壓力容器和消防器材的定期檢驗工作，發(fā)現(xiàn)問題及時解決并向站長匯報。17.1如果本標(biāo)書第二章“前附表”中允許投標(biāo)人提交備選方案的，投標(biāo)人可以除按招標(biāo)文件規(guī)定提交主選方案外，再提交備選方案，且須注明主選方案與備選方案，如未注明則以開標(biāo)時唱出的第一個方案為主選方案。備選方案應(yīng)說明與主選方案的差異，與主選方案一樣完整，并實質(zhì)性響應(yīng)招標(biāo)文件的要求。10.1賣方應(yīng)保證合同項下所供貨物是全新的、未使用過的，技術(shù)水平是先進(jìn)的、成熟的，并完全符合合同規(guī)定的數(shù)量、質(zhì)量、工藝、設(shè)計、型式、規(guī)格和技術(shù)性能，滿足合同技術(shù)規(guī)范的要求。賣方還須保證，合同項下提供的全部貨物不存在設(shè)計、材料或工藝上的缺陷。貨物在其正確安裝、正常使用和保養(yǎng)條件下，在其使用壽命期內(nèi)應(yīng)具有滿意的性能。其次是選拔服務(wù)禮儀師，也可稱為行銷服務(wù)師或總講師進(jìn)行培訓(xùn)。他在分支機構(gòu)主管的管理下工作，進(jìn)行全員教育訓(xùn)練。服務(wù)禮儀師的存在是必要的，他往往能夠起到企業(yè)文化傳承的作用。中序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則中序遍歷左子樹(L)；訪問根結(jié)點(V)；中序遍歷右子樹(R)。遍歷結(jié)果

a+b*c-d-e/f中序遍歷(InorderTraversal)--/+*abcdef20.3為買方方便而終止合同中序遍歷二叉樹算法的框架是：二叉樹遞歸的中序遍歷算法voidInOrder(BiTNode*T){

if(T!=NULL){InOrder(T->lchild);visit(T->data);InOrder(T->rchild);

}}visit()是輸出數(shù)據(jù)值的操作，在實際使用時可用相應(yīng)的操作來替換。二叉樹遞歸的中序遍歷算法voidInOrder(BiT前序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則訪問根結(jié)點(V)；前序遍歷左子樹(L)；前序遍歷右子樹(R)。遍歷結(jié)果

-+a*b-cd/ef前序遍歷(PreorderTraversal)--/+*abcdef前序遍歷二叉樹算法的框架是：前序遍歷(PreorderT二叉樹遞歸的前序遍歷算法voidPreOrder(BiTNode*T){

if(T!=NULL){visit(T->data);PreOrder(T->lchild);PreOrder(T->rchild);

}}與中序遍歷算法相比，visit()操作放在兩個子樹遞歸前序遍歷的最前面。二叉樹遞歸的前序遍歷算法voidPreOrder(BiT后序遍歷二叉樹算法的框架是：若二叉樹為空，則空操作；否則后序遍歷左子樹(L)；后序遍歷右子樹(R)；訪問根結(jié)點(V)。遍歷結(jié)果

abcd-*+ef/-后序遍歷(PostorderTraversal)d--/+*abcdef后序遍歷二叉樹算法的框架是：后序遍歷(Postorder二叉樹遞歸的后序遍歷算法voidPostOrder(BiTNode*T){

if(T!=NULL){PostOrder(T->lchild);PostOrder(T->rchild);visit(T->data);

}}與中序遍歷算法相比，visit()操作放在兩個子樹遞歸前序遍歷的最后面。二叉樹遞歸的后序遍歷算法voidPostOrder(Bi計算二叉樹結(jié)點個數(shù)的遞歸算法應(yīng)用二叉樹遍歷的事例intCount(BiTNode*T){

if(T==NULL)return0;

else

return1+Count(T->lchild)+Count(T->rchild);}空二叉樹的結(jié)點個數(shù)為0，可直接計算；否則可分別計算左、右子樹的結(jié)點個數(shù)，再相加得到總結(jié)點個數(shù)。計算二叉樹結(jié)點個數(shù)的遞歸算法應(yīng)用二叉樹遍歷的事例intCo求二叉樹高度的遞歸算法intHeight(BiTNode*T){if(T==NULL)return0;

else{intm=

Height(T->lchild);intn=

Height(T->rchild));return(m>n)?m+1:n+1;

}空樹的高度為0；非空樹情形，先計算根結(jié)點左右子樹的高度，取大者再加一得到二叉樹高度。求二叉樹高度的遞歸算法intHeight(BiTNoabcecdcc訪問a進(jìn)棧c左進(jìn)b訪問b進(jìn)棧d左進(jìn)空退棧d訪問d左進(jìn)空退棧c訪問c左進(jìn)e訪問e左進(jìn)空退棧結(jié)束利用棧的前序遍歷的非遞歸算法ddcabcecdc訪問訪問退棧退棧訪問結(jié)束利用棧的前序遍voidPreOrder(BinTreeT){stackS;InitStack(S);

//遞歸工作棧

BiTNode*p=T;Push(S,NULL);

while(p!=NULL){visit(p->data);if(p->rchild!=NULL)Push(S,p->rchild);if(p->lchild!=NULL)p=p->lchild; //進(jìn)左子樹

elsePop(S,p); //左子樹空,進(jìn)右子樹

}}

voidPreOrder(BinTreeT){abcdebaadaa左空退棧訪問左空退棧訪問退棧訪問左空ec退棧訪問cc右空退棧訪問?？战Y(jié)束利用棧的中序遍歷的非遞歸算法abcdebada左空退棧左空退棧退棧左空e退棧訪問cc右空

voidInOrder(BinTreeT){stackS;InitStack(S);//遞歸工作棧

BiTNode*p=

T;

//初始化

do{

while(p!=NULL) //子樹非空找中序第一個

{Push(S,p);p=p->lchild;}//邊找邊進(jìn)棧

if(!StackEmpty(S)){

//棧非空

Pop(S,p);//子樹中序第一個退棧

visit(p->data);

//訪問之

p=p->rchild; //向右子樹走

}

}while(p!=NULL||!StackEmpty(S));}voidInOrder(BinTreeT)后序遍歷時使用的棧的結(jié)點定義

typedefstruct

{ BiTNode*ptr; //結(jié)點指針

enumtag{L,R};//該結(jié)點退棧標(biāo)記 }StackNode;

根結(jié)點的tag=L，表示從左子樹退出,訪問右子樹。tag=R,表示從右子樹退出,訪問根。ptrtag{L,R}

利用棧的后序遍歷的非遞歸算法后序遍歷時使用的棧的結(jié)點定義ptrtag{L,R這家醫(yī)院的每部電梯里都有相應(yīng)的指示地圖，這種服務(wù)讓病人對醫(yī)院的滿意度大為提高?！颈局v小結(jié)】14.3若上述變更不引起賣方履行合同義務(wù)的費用或時間的實質(zhì)性變化時，合同的價格或交貨時間將不予調(diào)整，但也需賣方書面確認(rèn)。7、其它資料。收款單位：法正項目管理集團(tuán)有限公司青海分公司②可以和醫(yī)生正面接觸。（2）投標(biāo)人未按招標(biāo)文件要求提供資格證明文件或提供的有關(guān)資格、資質(zhì)文件不真實；1.1為提高企業(yè)生產(chǎn)與質(zhì)量管理水平，確保使用科學(xué)、有效的統(tǒng)計方法，及時準(zhǔn)確地了解生產(chǎn)與質(zhì)量情況，為指導(dǎo)生產(chǎn)、改善經(jīng)營、預(yù)測決策提供可靠的依據(jù),特制訂本制度；【案例】(二)團(tuán)組織申報。擬進(jìn)行換屆的團(tuán)組織，向同級黨組織和上級團(tuán)委提出開展競爭上崗的申請，經(jīng)同意后按照領(lǐng)導(dǎo)小組辦公室的統(tǒng)一安排組織實施。15.1除了第14條的規(guī)定之外，不應(yīng)對合同條款進(jìn)行任何變更或修改，除非雙方同意并簽署書面的合同修改協(xié)議，成為本合同不可分割的組成部分，具有與本合同同樣的效力。5.1.2統(tǒng)計方法選定的原則abcdeaLbLaLbRaLdLbRaLdRbRaLbRaLaLaReLcLaReRcLaRcLaRcRaRaR這家醫(yī)院的每部電梯里都有相應(yīng)的指示地圖，這種服務(wù)讓病人對醫(yī)院利用棧的后序遍歷的非遞歸算法voidPostOrder(BinTreeT){stackS;InitStack(S);StackNode

w;BiTNode*p=T;

do{

while(p!=NULL){ //向左子樹走

w.ptr=p;w.tag=L;Push(S,w);

p=p->lchild; }

intsucc=1; //繼續(xù)循環(huán)標(biāo)記利用棧的后序遍歷的非遞歸算法voidPostOrder(B

while(succ&&!StackEmpty(S)){Pop(S,w);p=w.ptr;

switch(w.tag){

//判斷棧頂tag標(biāo)記

caseL:w.tag=R;Push(S,w); succ=0;

p=p->rchild;break; caseR:visit(p->data);

}}}

while(!StackEmpty(S));}while(succ&&!StackEmpt二叉樹的計數(shù)由二叉樹的前序序列和中序序列可唯一地確定一棵二叉樹。例,前序序列{ABHFDECKG}和中序序列{HBDFAEKCG},構(gòu)造二叉樹過程如下：HBDFEKCGAEKCGABHDF二叉樹的計數(shù)由二叉樹的前序序列和中序序列可唯一地確定一棵二叉KCGEKCGABHDFEKCGABHFDEABHFDEABHFDCKGKCGEKCGABHDFEKCGABHFDEABHFDEAB612345789612375849如果前序序列固定不變，給出不同的中序序列，可得到不同的二叉樹。問題是：固定前序排列，選擇所有可能的中序排列，可以構(gòu)造出多少種不同的二叉樹？612345789612375849如果前序序列固定不變，給123123123123123例如,有3個數(shù)據(jù){1,2,3}，可得5種不同的二叉樹。它們的前序排列均為123，中序序列可能是123，132，213，231，321。那么，如何推廣到一般情形呢？首先，只有一個結(jié)點的不同二叉樹只有一個；有2個結(jié)點的不同二叉樹只有2種，其他情況呢？123123123123123例如,有3個數(shù)據(jù){b0=1b1=1b2=2b3=5

b4=14有0個,1個,2個,3個結(jié)點的不同二叉樹如下b0=1b1=1b2=2b3=5b4=14bibn-i-11計算具有n個結(jié)點的不同二叉樹的棵數(shù)Catalan函數(shù)例bibn-i-11計算具有n個結(jié)點的不同二叉樹的棵數(shù)Ca線索二叉樹(ThreadedBinaryTree)又稱為穿線樹。通過二叉樹遍歷，可將二叉樹中所有結(jié)點的數(shù)據(jù)排列在一個線性序列中，可以找到某數(shù)據(jù)在這種排列下它的前驅(qū)和后繼。希望不必每次都通過遍歷找出這樣的線性序列。只要事先做預(yù)處理，將某種遍歷順序下的前驅(qū)、后繼關(guān)系記在樹的存儲結(jié)構(gòu)中，以后就可以高效地找出某結(jié)點的前驅(qū)、后繼。為此，在二叉樹存儲結(jié)點中增加線索信息。線索二叉樹(ThreadedBinaryTree)又稱線索(Thread)增加前驅(qū)Pred指針和后繼Succ指針的二叉樹predlchilddatarchildsuccabcdepredpredpredsuccsuccsuccD∧∧AE∧∧B∧∧C∧∧rootpredpredpredpredsuccsuccsuccsucc線索(Thread)增加前驅(qū)Pred指針和后繼Succ指針這種設(shè)計的缺點是每個結(jié)點增加兩個指針，當(dāng)結(jié)點數(shù)很大時存儲消耗較大。改造樹結(jié)點，將pred指針和succ指針壓縮到lchild和rchild的空閑指針中，并增設(shè)兩個標(biāo)志ltag和rtag，指明指針是指示子女還是前驅(qū)／后繼。后者稱為線索。ltag(或rtag)=0，表示相應(yīng)指針指示左子女（或右子女結(jié)點）；ltag(或rtag)=1,表示相應(yīng)指針為前驅(qū)（或后繼）線索。lchildltagdatartagrchild

這種設(shè)計的缺點是每個結(jié)點增加兩個指針，當(dāng)結(jié)點數(shù)很大時存儲消耗中序線索二叉樹及其鏈表表示lchildltagdatartagrchild

abcdepredpredpredsuccsuccsuccDAEB∧C∧rootpredpredsuccsucc0000111111中序線索二叉樹及其鏈表表示lchildltagtypedefintTTElemType;typedefstructnode{

intltag,rtag;

structnode*lchild,*rchild;

TTElemTypedata;}ThreadNode,*ThreadTree;注意，線索二叉樹在樹結(jié)點中增加了ltag和rtag，改變了二叉樹的結(jié)構(gòu)。線索二叉樹的結(jié)構(gòu)定義typedefintTTElemType;線索二叉樹的通過中序遍歷建立中序線索二叉樹voidInThread(ThreadNode*t,

ThreadNode*&pre){

//預(yù)設(shè)了一個pre指針，指示t的中序前驅(qū)，在主

//程序中預(yù)置為NULL

if(t!=NULL){ InThread(t->lchild,pre);

//遞歸,左子樹線索化

if(t->lchild==NULL){ t->lchild=pre;t->ltag=1;}

//建立當(dāng)前結(jié)點t的前驅(qū)線索

通過中序遍歷建立中序線索二叉樹voidInThread(

if(pre&&pre->rchild==NULL){pre->rchild=t;pre->rtag=1;

}

//建立前驅(qū)結(jié)點pre的后繼線索

pre=t; //前驅(qū)跟上當(dāng)前指針

InThread(t->rchild,pre);

//遞歸,右子樹線索化

}}使用此函數(shù)可以把以t為根的子樹一次中序線索化，但中序下最后一個結(jié)點的后繼線索沒有加上，指針

pre

在退出時正在指示這一結(jié)點。if(pre&&pre->rchivoidCreateInThread(ThreadTreeT){ThreadNode*pre=NULL; //前驅(qū)指針

if(T!=NULL){

//樹非空,線索化

InThread(T,pre); //中序遍歷線索二叉樹

pre->rchild=NULL;pre->rtag=1;

//后處理,中序最后一個結(jié)點

}}通過該主程序?qū)崿F(xiàn)了對二叉樹的中序線索化。它是基于二叉樹的中序遍歷實現(xiàn)的。voidCreateInThread(ThreadTre0A00B0

0C00D00E0Tpre==NULLt0A00B00A01B0

0C00D00E0Tpre==NULLt0A01B00A01B0

0C0

1D00E0Tpret0A01B00A01B0

0C0

1D10E0Tpret0A01B00A01B0

0C0

1D11E0Tpret0A01B00A01B0

0C0

1D11E1Tpret0A01B00A01B0

0C1

1D11E1Tpre后處理0A01B0尋找結(jié)點p在中序下的后繼if(p->rtag==1)

后繼為

p->rchildelse

//p->rtag!=1

后繼為結(jié)點

p右子樹

q中的中序下的第一個結(jié)點ABDECFHIKGJ尋找結(jié)點p在中序下的后繼if(p->rtag==1)ThreadNode

*First(ThreadNode

*t){//函數(shù)返回以*t為根的線索二叉樹中的中序序列下//的第一個結(jié)點

ThreadNode*p=t;

while(p->ltag==0)p=p->lchild;

returnp; //最左下的結(jié)點}ThreadNode*Next(ThreadNode

*p){//函數(shù)返回在線索二叉樹中結(jié)點*p在中序下的后//繼結(jié)點ThreadNode*First(ThreadNod

if(p->rtag==0)returnFirst(p->rchild);

//p->rtag==0,后繼為右子樹中序第一個結(jié)點

else

returnp->rchild;

//p->rtag==1,直接返回后繼線索}voidInorder(ThreadNode*t){//以t為根的線索二叉樹的中序遍歷

ThreadNode*p;for(p=First(t);p!=NULL;p=Next(p))

cout<<p->data<<endl;}

if(p->rtag==0)retur尋找結(jié)點p在中序下的前驅(qū)if(p->ltag==1)

前驅(qū)為

p->lchildelse

//p->leftThread==0

前驅(qū)為結(jié)點

p左子樹中序下的最后一個結(jié)點ABDECFHIKGJL尋找結(jié)點p在中序下的前驅(qū)if(p->ltag==1)A前序序列

ABDCEp->ltag==1?前驅(qū)線索

=左子女p->rchild==NULL后繼為p->lchild=無后繼

后繼為p->rchildABCED前序線索二叉樹在前序線索二叉樹中尋找當(dāng)前結(jié)點的后繼前序序列p->ltag==1?前驅(qū)線索=左后序序列

DBECAp->rtag==1?后繼線索

=右子女后繼為q的右子樹中后序下第一個結(jié)點

后繼為p->rchild=無后繼

后繼為qABCEDq=p->parentq==NULL?q->rtag==1||q->rchild==p?=后序線索二叉樹在后序線索二 叉樹中尋找當(dāng) 前結(jié)點的后繼后序序列p->rtag==1?后繼線索=右樹的存儲表示

雙親表示為了操作實現(xiàn)的方便，有時會規(guī)定結(jié)點的存放順序。例如，可以按樹的前序次序存放樹中的各個結(jié)點，或按樹的層次次序安排所有結(jié)點。樹與樹的遍歷ABCDEFGdataparentABCDEFG-10001130123456樹的存儲表示樹與樹的遍歷ABCDEFGdataparentA子女鏈表表示無序樹情形鏈表中各結(jié)點順序任意，有序樹必須自左向右鏈接各個子女結(jié)點。ABCDEFG123∧45∧6∧∧∧∧∧ABCDEFG0123456子女鏈表表示無序樹情形鏈表中各結(jié)點順序任意，有序樹必須自左向子女指針表示一個合理的想法是在結(jié)點中存放指向每一個子女結(jié)點的指針。但由于各個結(jié)點的子女?dāng)?shù)不同，每個結(jié)點設(shè)置數(shù)目不等的指針，將很難管理。為此，設(shè)置等長的結(jié)點，每個結(jié)點包含的指針個數(shù)相等，等于樹的度（degree）。這保證結(jié)點有足夠的指針指向它的所有子女結(jié)點。但可能產(chǎn)生很多空閑指針，造成存儲浪費。子女指針表示一個合理的想法是在結(jié)點中存放指向每一個子女結(jié)點的等數(shù)量的鏈域ABCDEFG

datachild1child2child3childdABCDEFG空鏈域2n+1個等數(shù)量的鏈域ABCDEFGdatachild1child子女-兄弟表示也稱為樹的二叉樹表示。結(jié)點構(gòu)造為：firstChild指向該結(jié)點的第一個子女結(jié)點。無序樹時，可任意指定一個結(jié)點為第一個子女。nextSibling指向該結(jié)點的下一個兄弟。任一結(jié)點在存儲時總是有順序的。若想找某結(jié)點的所有子女，可先找firstChild,再反復(fù)用nextSibling沿鏈掃描。

datafirstChildnextSibling子女-兄弟表示也稱為樹的二叉樹表示。結(jié)點構(gòu)造為：data樹的左子女-

右兄弟表示

datafchildnsiblingABCDEFGABCDGFE樹的左子女-datafchildnsiblingABC左子女-右兄弟表示的樹的結(jié)構(gòu)定義typedefintTElemType;typedefstructnode{

TElemTypedata;

structnode*fchild,*nsibling;}CSNode,*CSTree;注意，雖然此定義與二叉樹的類似，操作也類似，但語義是不同的。樹結(jié)構(gòu)是遞歸的，可用遞歸函數(shù)實現(xiàn)相應(yīng)操作。左子女-右兄弟表示的樹的結(jié)構(gòu)定義typedefintTE尋找雙親子女兄弟的操作TreeNode*FindParent(CSNode*T,CSNode*p){//在以T為根的樹中找結(jié)點p的雙親

if(T==NULL||p==NULL)returnNULL;CSNode*q=T->fchild,*s;

while(q!=NULL&&q!=p){

//循根的長子的兄弟鏈,遞歸在子樹中搜索

if((s=FindParent(q,p))!=NULL)returns;

//在以q為根的子樹找到p的雙親，返回

q=q->nsibling;

}尋找雙親子女兄弟的操作TreeNode*FindPar

if(q!=NULL&&q==p)returnT;//找到雙親

elsereturnNULL;//未找到雙親}TreeNode*FindfirstChild(CSNode*p){//在樹中找結(jié)點p的第一個子女

if(p!=NULL)returnp->fchild;

else

returnNULL;};TreeNode*FindnextSibling(CSNode*p){//在樹中找結(jié)點p的兄弟if(q!=NULL&&q==p)

if(p!=NULL

)returnp->nsibling;

elsereturnNULL;}深度優(yōu)先遍歷先根次序遍歷后根次序遍歷廣度優(yōu)先遍歷樹的遍歷ABCDEFGABCEDGF二叉樹表示if(p!=NULL)return當(dāng)樹非空時訪問根結(jié)點依次先根遍歷根的各棵子樹樹先根遍歷ABEFCDG 對應(yīng)二叉樹前序遍歷ABEFCDG樹的先根遍歷結(jié)果與其對應(yīng)二叉樹 表示的前序遍歷結(jié)果相同樹的先根遍歷可以借助對應(yīng)二叉樹的前序遍歷算法實現(xiàn)ABCEDGF樹的先根次序遍歷ABCDEFG當(dāng)樹非空時ABCEDGF樹的先根次序遍歷ABCDEFG樹的先根次序遍歷的遞歸算法voidPreOrder

(CSNode*t){ //以指針t為根,先根次序遍歷

if(t!=NULL){visit(t->data);

//訪問根結(jié)點

CSNode*p

=t->fchild; //第一棵子樹

while(p!=NULL){

PreOrder(p); //遞歸先根遍歷子樹

p=p->nsibling;}}}樹的先根次序遍歷的遞歸算法voidPreOrder(C當(dāng)樹非空時依次后根遍歷根的各棵子樹訪問根結(jié)點樹后根遍歷EFBCGDA 對應(yīng)二叉樹中序遍歷EFBCGDA樹的后根遍歷結(jié)果與其對應(yīng)二叉樹 表示的中序遍歷結(jié)果相同樹的后根遍歷可以借助對應(yīng)二叉樹的中序遍歷算法實現(xiàn)ABCEDGF樹的后根次序遍歷ABCDEFG當(dāng)樹非空時ABCEDGF樹的后根次序遍歷ABCDEFG樹的后根次序遍歷的遞歸算法voidPostOrder(CSNode*t){//以指針t為根,按后根次序遍歷樹

if(t!=NULL){CSNode

*p=t->fchild;while(p!=NULL){ PostOrder(p);

p=p->nsibling;

}visit(t->data); //最后訪問根結(jié)點

}}樹的后根次序遍歷的遞歸算法voidPostOrder(按廣度優(yōu)先次序遍歷樹的結(jié)果

ABCDEFG廣度優(yōu)先遍歷算法 voidLevelOrder(CSTreeT){

//分層遍歷樹，算法用到一個隊列

QueueQ;InitQueue(Q);

CSNode*p; if(T!=NULL){ //樹不空

EnQueue(Q,T); //根結(jié)點進(jìn)隊列廣度優(yōu)先(層次次序)遍歷ABCEDGFABCDEFG按廣度優(yōu)先次序遍歷樹的結(jié)果廣度優(yōu)先(層次次序)遍歷ABCED

while(!QueueEmpty(Q)){

DeQueue(Q,p);visit(p->data);

//隊列中取一個并訪問之

p=p->fchild;

//待訪問結(jié)點的子女結(jié)點進(jìn)隊列

while(p!=NULL){

EnQueue(Q,p);p=p->nsibling;

}}

}}while(!QueueE森林與二叉樹的轉(zhuǎn)換將一般樹化為二叉樹表示就是用樹的子女-兄弟表示來存儲樹的結(jié)構(gòu)。森林與二叉樹表示的轉(zhuǎn)換可以借助樹的二叉樹表示來實現(xiàn)。森林與二叉樹的轉(zhuǎn)換將一般樹化為二叉樹表示就是用樹的子女-兄弟T1T2T3AFHT1T2T3ABCDGIJEKFBCDEGHIKJABCEDHIKJFG3

棵樹的森林各棵樹的二叉樹表示森林的二叉樹表示T1T2T3AFHT1森林轉(zhuǎn)化成二叉樹的規(guī)則若F為空，即n=0，則對應(yīng)的二叉樹B為空樹。若F不空，則二叉樹B的根是F第一棵樹T1

的根；其左子樹為B(T11,T12,…,T1m)，其中，T11,T12,…,T1m

是T1的根的子樹；其右子樹為B(T2,T3,…,Tn)，其中，T2,T3,…,Tn

是除T1

外其它樹構(gòu)成的森林。森林轉(zhuǎn)化成二叉樹的規(guī)則若F為空，即n=0，則對應(yīng)的二叉樹轉(zhuǎn)換為森林的規(guī)則如果B為空，則對應(yīng)的森林F也為空。如果B非空，則F中第一棵樹T1

的根為B的根；T1的根的子樹森林{T11,T12,…,T1m}是由B的根的左子樹LB轉(zhuǎn)換而來；F中除了T1

之外其余的樹組成的森林{T2,T3,…,Tn}是由B的根的右子樹RB轉(zhuǎn)換而成的森林。二叉樹轉(zhuǎn)換為森林的規(guī)則如果B為空，則對應(yīng)的森林F也為例題設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點個數(shù)分別為m1，m2和m3。那么在由該森林轉(zhuǎn)化成的二叉樹中根結(jié)點的右子樹上有（）個結(jié)點。 A.m1+m2 B.m2+m3 C.m3+m1 D.m1+m2+m3【解答】在由森林轉(zhuǎn)化成的二叉樹中根結(jié)點的右子樹上的結(jié)點是除第一棵外其他樹上的結(jié)點，應(yīng)有m2+m3個，故選擇B。

例題設(shè)森林中有三棵樹，第一、第二和第三棵樹中的結(jié)點個數(shù)分別為森林的遍歷森林的遍歷也分為深度優(yōu)先遍歷（包括先根次序遍歷和中根次序遍歷）和廣度優(yōu)先遍歷。深度優(yōu)先遍歷給定森林F，若F=?，則遍歷結(jié)束。否則若F={{T1={r1,T11,…,T1k},T2,...,Tm}，則可以導(dǎo)出先根遍歷、中根遍歷兩種方法。其中，r1是第一棵樹的根結(jié)點，{T11,…,T1k}是第一棵樹的子樹森林，{T2,...,Tm}是除去第一棵樹之后剩余的樹構(gòu)成的森林。森林的遍歷森林的遍歷也分為深度優(yōu)先遍歷（包括先根次序遍歷和中若森林F=?，返回；否則訪問森林的根（也是第一棵樹的根）r1；先根遍歷森林第一棵樹的根的子樹森林{T11,…,T1k}；先根遍歷森林中除第一棵樹外其他樹組成的森林{T2,...,Tm}。注意，②是一個循環(huán)，對于每一個T1i，執(zhí)行樹的先根次序遍歷；③是一個遞歸過程，重新執(zhí)行T2

為第一棵樹的森林的先根次序遍歷。森林的先根次序遍歷若森林F=?，返回；否則森林的先根次序遍歷森林的先根次序遍歷的結(jié)果序列

ABCDEFGHIKJ這相當(dāng)于對應(yīng)二叉樹的前序遍歷結(jié)果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC森林的先根次序遍歷的結(jié)果序列T1T2森林的中根次序遍歷若森林F=?，返回；否則中根遍歷森林

F

第一棵樹的根結(jié)點的子樹森林{T11,…,T1k}；訪問森林的根結(jié)點r1；中根遍歷森林中除第一棵樹外其他樹組成的森林{T2,...,Tm}。注意，與先根次序遍歷相比，訪問根結(jié)點的時機不同。所以在③的情形，對以T2為第一棵樹的森林遍歷時，重復(fù)執(zhí)行①②③的操作。森林的中根次序遍歷若森林F=?，返回；否則森林的中根次序遍歷的結(jié)果序列

BCEDAGFKIJH這相當(dāng)于對應(yīng)二叉樹中序遍歷的結(jié)果。T1T2T3AFHBCDGIJEKBAEDHIKJFGC森林的中根次序遍歷的結(jié)果序列T1T2廣度優(yōu)先遍歷（層次序遍歷）AFHBCDGIJEKABCEDHIKJFG若森林F

為空，返回； 否則依次遍歷各棵樹的 根結(jié)點；依次遍歷各棵樹根 結(jié)點的所有子女；依次遍歷這些子女 結(jié)點的子女結(jié)點；廣度優(yōu)先遍歷（層次序遍歷）AFHBCDGIJEKABCE樹的應(yīng)用二叉排序樹平衡二叉樹Huffman樹堆并查集樹的應(yīng)用二叉排序樹二叉排序樹(BinarySearchTree)定義

二叉排序樹或者是一棵空樹，或者是具有下列性質(zhì)的二叉樹：每個結(jié)點都有一個作為查找依據(jù)的關(guān)鍵字(key)，所有結(jié)點的關(guān)鍵字互不相同。左子樹（如果非空）上所有結(jié)點的關(guān)鍵字都小于根結(jié)點的關(guān)鍵字。右子樹（如果非空）上所有結(jié)點的關(guān)鍵字都大于根結(jié)點的關(guān)鍵字。左子樹和右子樹也是二叉排序樹。二叉排序樹(BinarySearchTree)定義351545504025102030二叉排序樹例結(jié)點左子樹上所有關(guān)鍵 字小于結(jié)點關(guān)鍵字；結(jié)點右子樹上所有關(guān)鍵 字大于結(jié)點關(guān)鍵字；如果對一棵二叉排序樹 進(jìn)行中序遍歷，可以按 從小到大的順序?qū)⒏鹘Y(jié) 點關(guān)鍵字排列起來。注意，國外教材統(tǒng)稱為二叉搜索樹或二叉查找樹。351545504025102030二叉排序樹例結(jié)點左子樹上例題一棵二叉樹是二叉排序樹的（）條件是樹中任一結(jié)點的關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。 A.充分但不必要B.必要但不充分C.充分且必要D.既不充分也不必要【解答】B。 通俗來講，必要條件是指符合定義則必具有后續(xù)講的特性。顯然一棵二叉樹是二叉排序樹，則樹中任一結(jié)點的關(guān)鍵字值一定大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值。充分條件是指滿足例題一棵二叉樹是二叉排序樹的（）條件是樹中任一結(jié)點的 后續(xù)講的特性則定義一定成立。就是說，如果一棵二叉樹任一結(jié)點的關(guān)鍵字值都大于左子女的關(guān)鍵字值，小于右子女的關(guān)鍵字值，則它一定是二叉排序樹。這就不一定了。

右圖描述的二叉樹滿足樹中 任一結(jié)點的關(guān)鍵字值一定大 于左子女的關(guān)鍵字值，小于 右子女的 關(guān)鍵字值，但它不 是二叉排序樹。2515353045102050 后續(xù)講的特性則定義一定成立。就是說，如果一棵二叉樹任一結(jié)點

二叉排序樹的結(jié)構(gòu)定義typedefcharBSTElemType; //樹結(jié)點數(shù)據(jù)類型typedefstructnode{ //二叉排序樹結(jié)點

BSTElemType

data;

structnode*lchild,*rchild;}BSTNode,*BSTree; //二叉排序樹定義從面向?qū)ο笥^點來看，二叉排序樹是二叉樹的特殊情形，它繼承了二叉樹的結(jié)構(gòu)，增加了自己的特性，對數(shù)據(jù)的存放增加了約束。二叉排序樹的結(jié)構(gòu)定義typedefcharBST二叉排序樹上的查找查找45

查找成功

查找28查找失敗351545504025102030在二叉排序樹上進(jìn)行查找，是一個從根結(jié)點開始，沿某一個分支逐層向下進(jìn)行比較判等的過程。它可以是一個遞歸的過程。二叉排序樹上的查找查找45查找28351545假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過程從根結(jié)點開始。如果根指針為NULL，則查找不成功；否則用給定值x與根結(jié)點的關(guān)鍵字進(jìn)行比較：如果給定值等于根結(jié)點的關(guān)鍵字值，則查找成功。如果給定值小于根結(jié)點的關(guān)鍵字值，則繼續(xù)遞歸查找根結(jié)點的左子樹；否則。遞歸查找根結(jié)點的右子樹。查找成功時檢測指針停留在樹中某個結(jié)點。假設(shè)想要在二叉排序樹中查找關(guān)鍵字為x的元素，查找過程從根結(jié)點可用判定樹描述查找過程。內(nèi)結(jié)點是樹中原有結(jié)點，外結(jié)點是失敗結(jié)點，代表樹中沒有的數(shù)據(jù)。查找不成功時檢測指針停留在某個失敗結(jié)點。3515455025102030查找22查找45可用判定樹描述查找過程。內(nèi)結(jié)點是樹中原有結(jié)點，外結(jié)點是失敗結(jié)二叉排序樹的查找算法voidFind(BSTNode*t,BSTElemTypex,BSTNode*&p,BSTNode*&pr){//在二叉排序樹t中查找關(guān)鍵字等于x的結(jié)點，成功//時p返回找到結(jié)點地址,pr是其雙親結(jié)點.不成功//時p為空,pr返回最后走到的結(jié)點地址.

p=t;pr=NULL; //從根查找if(p!=NULL){

while(p!=NULL&&p->data!=x){pr=p;if(p->data<x)p=p->rchild;

elsep=p->lchild;二叉排序樹的查找算法voidFind(BSTNode

}}}查找的關(guān)鍵字比較次數(shù)最多不超過樹的高度。每次結(jié)點的插入，都要從根結(jié)點出發(fā)查找插入位置，然后把新結(jié)點作為葉結(jié)點插入。為了向二叉排序樹中插入一個新元素，必須先檢查這個元素是否在樹中已經(jīng)存在。二叉排序樹的插入}二叉排序樹的插入為此，在插入之前先使用查找算法在樹中檢查要插入元素有還是沒有。查找成功：樹中已有 這個元素,不再插入。查找不成功：樹中原 來沒有關(guān)鍵字等于給 定值的結(jié)點，把新元 素加到查找操作停止 的地方。35154550402510203028插入新結(jié)點28為此，在插入之前先使用查找算法在樹中檢查要插入元素有還是沒有voidInsert

(BSTNode*&t,BSTElemTypex){//將新元素x插到以*t為根的二叉排序樹中

BstNode*pt,*prt,*q;

Find(t,x,pt,prt); //查找結(jié)點插入位置

if(pt==NULL){ //查找失敗時可插入

q=newBstNode;q->data=x; //創(chuàng)建結(jié)點

q->lchild=q->rchild=NULL;

if(prt==NULL)t=q;//空樹

else

if(x<prt->data)ptr->lchild=q;elseptr->rchild=q;}}voidInsert(BSTNode*&t,BS535378537865537865175378658717537865091787537865811787095378651517870981輸入數(shù)據(jù)，建立二叉排序樹的過程輸入數(shù)據(jù){53,78,65,17,87,09,81,15}535378537865537865175378658717123111132223323同樣3個數(shù)據(jù){1,2,3}，輸入順序不同，建立起來的二叉排序樹的形態(tài)也不同。這直接影響到二叉排序樹的查找性能。如果輸入序列選得不好，會建立起一棵單支樹，使得二叉排序樹的高度達(dá)到最大。

{2,1,3}{1,2,3}{1,3,2}{2,3,1}{3,1,2}{3,2,1}123111132223323同樣3個數(shù)據(jù){1,2,二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點時，必須將因刪除結(jié)點而斷開的二叉鏈表重新鏈接起來，同時確保二叉排序樹的性質(zhì)不會失去。為保證在刪除后樹的查找性能不至于降低，還需要防止重新鏈接后樹的高度增加。被刪結(jié)點的右子樹為空，可以拿它的左子女結(jié)點頂替它的位置，再釋放它。被刪結(jié)點的左子樹為空，可以拿它的右子女結(jié)點頂替它的位置，再釋放它。被刪結(jié)點的左、右子樹都不為空，可以在它二叉排序樹的刪除在二叉排序樹中刪除一個結(jié)點時，必須將因刪除結(jié) 的右子樹中尋找中序下的第一個結(jié)點(所有比被刪關(guān)鍵字大的關(guān)鍵字中它的值最小),用它的值填補到被刪結(jié)點中，再來處理這個結(jié)點的刪除問題。當(dāng)然，也可以到它的左子樹中尋找中序下的最后一個結(jié)點。右子樹空,用左子女頂替5378651787092345刪除4553786517870923 的右子樹中尋找中序下的第一個結(jié)點(所有比被刪關(guān)鍵字大的關(guān)鍵左子樹空,用右子女頂替在右子樹上找中序下第一個結(jié)點填補8853788817940923刪除7853948817092353788117940945刪除78236553