數(shù)據(jù)結(jié)構(gòu)-樹與二叉樹

第六章樹和二叉樹23FileDocuments4

樹是一類重要的非線性數(shù)據(jù)結(jié)構(gòu)，是以分支關(guān)系定義的層次結(jié)構(gòu)5

樹(Tree)：是包括n(n>=0)個結(jié)點的有限集T。當T非空時，滿足：（1）有且僅有一個特別標出的稱為根的結(jié)點；（2）除根結(jié)點外，其余結(jié)點可分為m（m>=0）個互不相交非空的有限集T1,T2,…,Tm,其中每一個集合本身又是一棵樹，稱為根的子樹

(Subtree)。樹的遞歸定義：空樹：不包括任何結(jié)點的樹。A只有根結(jié)點的樹ABCDEFGHIJKLM有子樹的樹根子樹7樹(Tree)的例子：一個家族A有子女B,C；B和C分別有子女D,E,F和G,H;E有子女I,J。T=(N,R),其中N={A,B,C,D,E,F,G,H,I,J}R={A,B,A,C,B,D,B,E,B,F,C,G,C,H,E,I,E,J}8樹的表示方法：(b)凹入表（a）樹形表示ABCDEFIJGH9(A(B(D)(E(I)(J))(C(G)(H)))(d)嵌套括號表示法CDEIJFGHAB(c)文氏圖基本術(shù)語結(jié)點(node)——表示樹中的元素，包括數(shù)據(jù)項及若干指向其子樹的分支結(jié)點的度(degree)——結(jié)點擁有的子樹數(shù)葉子(leaf)——度為0的結(jié)點孩子(child)——結(jié)點子樹的根稱為該結(jié)點的孩子雙親(parents)——孩子結(jié)點的上層結(jié)點叫該結(jié)點的雙親兄弟(sibling)——同一雙親的孩子樹的度——一棵樹中最大的結(jié)點度數(shù)結(jié)點的層次(level)——從根結(jié)點算起，根為第一層，它的孩子為第二層……深度(depth)——樹中結(jié)點的最大層次數(shù)森林(forest)——m(m

0)棵互不相交的樹的集合ABCDEFGHIJKLM結(jié)點A的度：3結(jié)點B的度：2結(jié)點M的度：0葉子：K，L，F(xiàn)，G，M，I，J結(jié)點A的孩子：B，C，D結(jié)點B的孩子：E，F(xiàn)結(jié)點I的雙親：D結(jié)點L的雙親：E結(jié)點B，C，D為兄弟結(jié)點K，L為兄弟樹的度：3結(jié)點A的層次：1結(jié)點M的層次：4樹的深度：4結(jié)點A的層次：1結(jié)點M的層次：412無序樹、有序樹(orderedtree)對子樹的次序不加區(qū)別的樹叫作無序樹。對子樹之間的次序加以區(qū)別的樹叫作有序樹。12

(a)樹t (b)樹t'

對比樹型結(jié)構(gòu)和線性結(jié)構(gòu)的結(jié)構(gòu)特點~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~線性結(jié)構(gòu)樹型結(jié)構(gòu)第一個數(shù)據(jù)元素

(無前驅(qū))

根結(jié)點

(無前驅(qū))最后一個數(shù)據(jù)元素

(無后繼)多個葉子結(jié)點

(無后繼)其它數(shù)據(jù)元素(一個前驅(qū)、一個后繼)其它數(shù)據(jù)元素(一個前驅(qū)、多個后繼)

樹的基本操作：查找類

插入類刪除類

Root(T)//求樹的根結(jié)點

查找類：Value(T,cur_e)//求當前結(jié)點的元素值

Parent(T,cur_e)//求當前結(jié)點的雙親結(jié)點LeftChild(T,cur_e)//求當前結(jié)點的最左孩子RightSibling(T,cur_e)//求當前結(jié)點的右兄弟TreeEmpty(T)//判定樹是否為空樹TreeDepth(T)//求樹的深度TraverseTree(T,Visit())//遍歷InitTree(&T)//初始化置空樹

插入類：CreateTree(&T,definition)//按定義構(gòu)造樹Assign(T,cur_e,value)//給當前結(jié)點賦值InsertChild(&T,&p,i,c)//將以c為根的樹插入為結(jié)點p的第i棵子樹

ClearTree(&T)//將樹清空

刪除類：DestroyTree(&T)//銷毀樹的結(jié)構(gòu)DeleteChild(&T,&p,i)//刪除結(jié)點p的第i棵子樹6.2二叉樹定義定義：二叉樹是n(n0)個結(jié)點的有限集，它或為空樹(n=0)，或由一個根結(jié)點和兩棵分別稱為左子樹和右子樹的互不相交的二叉樹構(gòu)成特點每個結(jié)點至多有二棵子樹(即不存在度大于2的結(jié)點)二叉樹的子樹有左、右之分，且其次序不能任意顛倒基本形態(tài)A只有根結(jié)點的二叉樹

空二叉樹AB右子樹為空AB左子樹為空ABC左、右子樹均非空二叉樹性質(zhì)性質(zhì)1：證明：用歸納法證明之

i=1時，只有一個根結(jié)點，是對的假設(shè)對所有j(1j<i)命題成立，即第j層上至多有個結(jié)點那么，第i-1層至多有個結(jié)點又二叉樹每個結(jié)點的度至多為2第i層上最大結(jié)點數(shù)是第i-1層的2倍，即故命題得證在二叉樹的第i層上至多有2i-1個節(jié)點(i>＝1)性質(zhì)2：深度為k的二叉樹至多有個結(jié)點(k1)證明：由性質(zhì)1，可得深度為k的二叉樹最大結(jié)點數(shù)是性質(zhì)3：對任何一棵二叉樹T，如果其終端結(jié)點數(shù)為n0，度為2的結(jié)點數(shù)為n2，則n0=n2+1證明：n1為二叉樹T中度為1的結(jié)點數(shù)因為：二叉樹中所有結(jié)點的度均小于或等于2所以：其結(jié)點總數(shù)n=n0+n1+n2(1)

又因為在二叉樹中，除根結(jié)點外，其余結(jié)點都只

有一個分支進入設(shè)B為分支總數(shù)，則n=B+1

又：分支由度為1和度為2的結(jié)點射出，

B=n1+2*n2

于是，n=B+1=n1+2*n2+1(2)n1+2*n2+1=n0+n1+n2n0=n2+1幾種特殊形式的二叉樹滿二叉樹定義：特點：每一層上的結(jié)點數(shù)都是最大結(jié)點數(shù)完全二叉樹定義：深度為k，有n個結(jié)點的二叉樹當且僅當其每一個結(jié)點都與深度為k的滿二叉樹中編號從1至n的結(jié)點一一對應(yīng)時，稱為~特點葉子結(jié)點只可能在層次最大的兩層上出現(xiàn)對任一結(jié)點，若其右分支下子孫的最大層次為l，則其左分支下子孫的最大層次必為l或l+11231145891213671014151231145891267101234567123456性質(zhì)4：具有n個結(jié)點的完全二叉樹的深度k為

log2n+1.證明:假設(shè)深度為k,則根據(jù)性質(zhì)2和完全二叉樹的定義有:2k-1-1n2k-1

等價于:

2k-1

n2k

k-1log2nkk=log2n+1性質(zhì)5：如果對一棵有n個結(jié)點的完全二叉樹的結(jié)點按層序編號，則對任一結(jié)點i(1in)，有：

(1)如果i=1，則結(jié)點i是二叉樹的根，無雙親；如果i>1，則其雙親是

i/2(2)如果2i>n，則結(jié)點i無左孩子；如果2in，則其左孩子是2i(3)如果2i+1>n，則結(jié)點i無右孩子；如果2i+1n，則其右孩子是2i+128i2i2i+1i/212345678929性質(zhì)5的證明：對于（2）和（3）當i=1時，2i=2

n，左子女結(jié)點的序號為2。2i+1=3

n，右子女結(jié)點的序號為3。假設(shè)對于序號為j的結(jié)點，命題成立。對于i=j+1，其左子女結(jié)點的序號等于j的右子女結(jié)點的序號加1，即：2j+1+1=2(j+1)

其右子女結(jié)點的序號等于：2(j+1)+1根據(jù)（2）和（3），知的父結(jié)點為

i/2.

完全二叉樹的層次序列，反映了它的結(jié)構(gòu)。30123jj+1

2j2j+12(j+1)2(j+1)+131i2i+12i+2(i-1)/2012345678從０編號？二叉樹的存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)實現(xiàn)：按滿二叉樹的結(jié)點層次編號，依次存放二叉樹中的數(shù)據(jù)元素特點：結(jié)點間關(guān)系蘊含在其存儲位置中浪費空間，適于存滿二叉樹和完全二叉樹abcdefgabcde0000fg1234567891011鏈式存儲結(jié)構(gòu)二叉鏈表typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;lchilddatarchildABCDEFG在n個結(jié)點的二叉鏈表中，有n+1個空指針域?ABCDEFG^^^^^^^^三叉鏈表typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild,*parent;}BiTNode,*BiTree;lchilddataparentrchildABCDEFGABCDEFG^^^^^^^^^6.3遍歷二叉樹和線索二叉樹遍歷樹遍歷——按一定規(guī)律走遍樹的各個頂點，且使每一頂點僅被訪問一次，即找一個完整而有規(guī)律的走法，以得到樹中所有結(jié)點的一個線性排列

順著某一條搜索路徑巡訪二叉樹中的結(jié)點，使得每個結(jié)點均被訪問一次，而且僅被訪問一次。問題的提出“訪問”的含義可以很廣，如：輸出結(jié)點的信息等。

“遍歷”是任何類型均有的操作，對線性結(jié)構(gòu)而言，只有一條搜索路徑(因為每個結(jié)點均只有一個后繼)而二叉樹是非線性結(jié)構(gòu)，每個結(jié)點有兩個后繼，則存在如何遍歷即按什么樣的搜索路徑進行遍歷的問題對“二叉樹”而言，可以有三種搜索路徑：1．先上后下的按層次遍歷；2．先左（子樹）后右（子樹）的遍歷；3．先右（子樹）后左（子樹）的遍歷。二、先左后右的遍歷算法先（根）序的遍歷算法中（根）序的遍歷算法后（根）序的遍歷算法根左子樹右子樹根根根根根

若二叉樹為空樹，則空操作；否則，（1）訪問根結(jié)點；（2）先序遍歷左子樹；（3）先序遍歷右子樹。先（根）序的遍歷算法：

若二叉樹為空樹，則空操作；否則，（1）中序遍歷左子樹；（2）訪問根結(jié)點；（3）中序遍歷右子樹。中（根）序的遍歷算法：

若二叉樹為空樹，則空操作；否則，（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點。后（根）序的遍歷算法：二叉樹的遍歷方法先序遍歷：先訪問根結(jié)點,然后分別先序遍歷左子樹、右子樹中序遍歷：先中序遍歷左子樹，然后訪問根結(jié)點，最后中序遍歷右子樹后序遍歷：先后序遍歷左、右子樹，然后訪問根結(jié)點按層次遍歷：從上到下、從左到右訪問各結(jié)點DLRLDR、LRD、DLRRDL、RLD、DRLADBCDLRADLRDLR>B>>D>>CDLR先序遍歷序列：ABDC先序遍歷:ADBCLDRBLDRLDR>A>>D>>CLDR中序遍歷序列：BDAC中序遍歷:ADBCLRDLRDLRD>A>>D>>CLRD后序遍歷序列：DBCA后序遍歷:B-+/a*b-efcd先序遍歷：中序遍歷：后序遍歷：層次遍歷：-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/ef-+a*b-cd/efABCDEFGHK練習：先序序列：中序序列：后序序列：A

BCD

EFGHKBDC

A

EHGKFDCBHKGFE

A遍歷算法遞歸算法非遞歸算法voidPreorderTraverse(T){if(T){printf("%d\t",T->data);preorder(T->lchild);preorder(T->rchild);}}主程序Pre(T)返回返回返回返回ACBDTBprintf(B);pre(TL);BTAprintf(A);pre(TL);ATDprintf(D);pre(TL);DTCprintf(C);pre(TL);C返回T>左是空返回pre(TR);T>左是空返回T>右是空返回T>左是空返回T>右是空返回pre(TR);先序序列：ABDCpre(TR);pre(TR);非遞歸算法：中序ABCDEFGpiP->A(1)ABCDEFGpiP->AP->B(2)ABCDEFGpiP->AP->BP->C(3)p=NULLABCDEFGiP->AP->B訪問：C(4)pABCDEFGiP->A訪問：CB(5)ABCDEFGiP->AP->D訪問：CBp(6)ABCDEFGiP->AP->DP->E訪問：CBp(7)ABCDEFGiP->AP->D訪問：CBEp(8)ABCDEFGiP->AP->DP->G訪問：CBEP=NULL(9)ABCDEFGiP->A訪問：CBEGDp(11)ABCDEFGiP->AP->F訪問：CBEGDp(12)ABCDEFGiP->AP->D訪問：CBEGp(10)ABCDEFGiP->A訪問：CBEGDFp=NULL(13)ABCDEFGi訪問：CBEGDFAp(14)ABCDEFGi訪問：CBEGDFAp=NULL(15)StatusInOrderTraverse(BiTreeT,Status(*Visit)(ElemType)){//算法6.3//采用二叉鏈表存儲結(jié)構(gòu)，Visit是對數(shù)據(jù)元素操作的應(yīng)用函數(shù)。

//中序遍歷二叉樹T的非遞歸算法，對每個數(shù)據(jù)元素調(diào)用函數(shù)Visit。

stackS;BiTreep;InitStack(S);p=T;while(p||!StackEmpty(S)){if(p){Push(S,p);p=p->lchild;}//非空指針進棧，繼續(xù)左進

else{//上層指針退棧，訪問其所指結(jié)點，再向右進

Pop(S,p);if(!Visit(p->data))returnERROR;p=p->rchild;}}returnOK;}//InOrderTraverse遍歷算法的應(yīng)用舉例2、建立二叉樹的存儲結(jié)構(gòu)1、查詢二叉樹中某個結(jié)點1.查詢二叉樹中某個結(jié)點1.

在二叉樹不空的前提下,和根結(jié)點的元素進行比較,若相等,則找到返回TRUE;2.

否則在左子樹中進行查找,若找到,則返回TRUE;3.

否則繼續(xù)在右子樹中進行查找,若找到,則返回TRUE,否則返回FALSE;StatusPreorder(BiTreeT,ElemTypex,BiTree&p)

{//

若二叉樹中存在和x相同的元素，則

p指向該結(jié)點并返回

OK,//否則返回

FALSE

}if(T){if(T->data==x){p=T;returnOK,}

}//ifelsereturnFALSE;else{if(Preorder(T->lchild,x,p)returnOK;elsereturn(Preorder(T->rchild,x,p))

;}//else2.建立二叉樹的存儲結(jié)構(gòu)不同的定義方法相應(yīng)有不同的存儲結(jié)構(gòu)的建立算法以字符串的形式“根左子樹右子樹”定義一棵二叉樹,空樹要顯式表示例如:以空白字符“#”表示ABCDA(B(#,C(#,#)),D(#,#))空樹只含一個根結(jié)點的二叉樹A以字符串“A##”表示以下列字符串表示Status

CreateBiTree(BiTree&T)

{scanf(&ch);

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

else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;//生成根結(jié)點

CreateBiTree(T->lchild);//構(gòu)造左子樹

CreateBiTree(T->rchild);//構(gòu)造右子樹

}

returnOK;}//CreateBiTreeAB#

C

##

D

#

#

ABCD上頁算法執(zhí)行過程舉例如下:ATBCD^^^^^scanf(&ch);if(ch=='')T=NULL;else{

if(!(T=newBiTNode))

exit(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);遍歷算法應(yīng)用按先序遍歷序列建立二叉樹的二叉鏈表，已知先序序列為：

ABC##DE#G##F###ABCDEFGA^B^C^D^E^F^^G^由二叉樹的非空結(jié)點的先序和中序序列建樹練習一棵二叉樹的先序遍歷序列為ABCDEFG，它的中序遍歷序列可能是()A.CABDEFG B.ABCDEFGC.DACEFBG D.ADCFEGB一棵二叉樹的先序遍歷序列為EFHIGJK，它的中序遍歷序列為HFIEJKG，則該二叉樹根節(jié)點的右孩子為()A.E B.FC.G D.HB,DC一棵二叉樹的先序遍歷序列為ABCDEF，它的中序遍歷為CBAEDF，則后序遍歷序列為()A.CBEFDA B.FEDCBAC.CBEDFA D.不確定一棵二叉樹的后序遍歷序列為DABEC，中序遍歷序列為DEBAC，則先序遍歷序列為()A.ACBED B.DECABC.DEABC D.CEDBADA任何n個不同結(jié)點的二叉樹,都可由它的中序序列和先序序列唯一確定任何n個不同結(jié)點的二叉樹,都可由它的中序序列和后序序列唯一確定

僅知二叉樹的先序序列“abcdefg”

不能唯一確定一棵二叉樹，

如果同時已知二叉樹的中序序列“cbdaegf”,則會如何？

二叉樹的先序序列二叉樹的中序序列左子樹左子樹右子樹右子樹根根abcdefgcbdaegf例如:aabbccddeeffggabcdefg^^^^^^^^先序序列中序序列voidCrtBT(BiTree&T,charpre[],charino[],intps,intis,intn){//已知pre[ps..ps+n-1]為二叉樹的先序序列，//ino[is..is+n-1]為二叉樹的中序序列，本算//法由此兩個序列構(gòu)造二叉鏈表

if(n==0)T=NULL;else{k=Search(ino,pre[ps]);//在中序序列中查詢

if(k==-1)T=NULL;else{}}//}//CrtBT……if(!(T=newBiTNode))exit(OVERFLOW);T->data=pre[ps];if(k==is)T->Lchild=NULL;elseCrtBT(T->Lchild,pre[],ino[],ps+1,is,k-is);if(k==is+n-1)T->Rchild=NULL;elseCrtBT(T->Rchild,pre[],ino[],ps+1+(k-is),k+1,n-(k-is)-1);作業(yè)已知二叉樹的中序遍歷序列charino[]以及后序遍歷序列charpost[]，請用算法生成該二叉樹（用二叉鏈表的形式存儲）。線索二叉樹線索二叉樹定義：遍歷二叉樹以一定規(guī)則將二叉樹中的結(jié)點排列成一個線形序列,在二叉樹的先序、中序或后序遍歷序列中兩個相鄰的結(jié)點互稱為前驅(qū)與后繼線索：指向前驅(qū)或后繼結(jié)點的指針稱為~線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫~線索化：對二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫~實現(xiàn)在有n個結(jié)點的二叉鏈表中必定有n+1個空鏈域在線索二叉樹的結(jié)點中增加兩個標志域lt:若lt=0,lc

域指向左孩子；若lt=1,lc域指向其前驅(qū)rt:若rt=0,rc

域指向右孩子；若rt=1,rc域指向其后繼結(jié)點定義：lcltdatartrcABCDEABDCET先序序列：ABCDE先序線索二叉樹00001111^11ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^ABCDEABDCET后序序列：CBEDA后序線索二叉樹0000111111^二叉排序樹二叉排序樹定義：二叉排序樹或是一棵空樹，或是具有下列性質(zhì)的二叉樹：若它的左子樹不空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值若它的右子樹不空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值它的左、右子樹也分別為二叉排序樹二叉排序樹二叉排序樹的插入插入原則：若二叉排序樹為空，則插入結(jié)點應(yīng)為新的根結(jié)點；否則，繼續(xù)在其左、右子樹上查找，直至某個結(jié)點的左子樹或右子樹為空為止，則插入結(jié)點應(yīng)為該葉子結(jié)點的左孩子或右孩子二叉排序樹生成：從空樹出發(fā)，經(jīng)過一系列的查找、插入操作之后，可生成一棵二叉排序樹插入算法例{10，18，3，8，12，2，7}10101810183101838101838121018381221018381227中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列StatusSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p){//算法9.5(b)//在根指針T所指二叉排序樹中遞歸地查找其關(guān)鍵字等于key的數(shù)據(jù)元素，

//若查找成功，則指針p指向該數(shù)據(jù)元素結(jié)點，并返回TRUE，

//否則指針p指向查找路徑上訪問的最后一個結(jié)點并返回FALSE，

//指針f指向T的雙親，其初始調(diào)用值為NULLif(!T){p=f;returnFALSE;}//查找不成功

elseif(EQ(key,T->data.key)){p=T;returnTRUE;}//查找成功

elseif(LT(key,T->data.key))returnSearchBST(T->lchild,key,T,p);//在左子樹中繼續(xù)查找

elsereturnSearchBST(T->rchild,key,T,p);//在右子樹中繼續(xù)查找}//SearchBSTSearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)在T為根的二叉樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素(f指向T的雙親),查找成功,返true,p指向該節(jié)點,否則p指向查找路徑上的最后一個節(jié)點,返回falseStatusInsertBST(BiTree&T,ElemTypee){ BiTNode*p; BiTNode*s; if(!SearchBST(T,e,NULL,p)) { s=(BiTNode*)malloc(sizeof(BiTNode)); s->data=e; s->lchild=NULL; s->rchild=NULL; if(!p)T=s; elseif(e<p->data)p->lchild=s; elsep->rchild=s; returnTRUE; } elsereturnFALSE;}SearchBST(BiTreeT,KeyTypekey,BiTreef,BiTree&p)在T為根的二叉樹中查找關(guān)鍵字等于key的數(shù)據(jù)元素(f指向T的雙親),查找成功,返true,p指向該節(jié)點,否則p指向查找路徑上的最后一個節(jié)點,返回false二叉排序樹的刪除要刪除二叉排序樹中的p結(jié)點，分三種情況：p為葉子結(jié)點，只需修改p雙親f的指針f->lchild=NULLf->rchild=NULLp只有左子樹或右子樹p只有左子樹，用p的左孩子代替p(1)(2)p只有右子樹，用p的右孩子代替p(3)(4)p左、右子樹均非空沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p(5)或者用C代替p,p的右孩子成為S的右孩子。若C無右子樹，用C取代p(6)SQPLP中序遍歷：QSPLPSQPL中序遍歷：QSPL(2)SPPLQ中序遍歷：PLPSQSPLQ中序遍歷：PLSQ(1)p只有左子樹，用p的左孩子代替p中序遍歷：PPRSQSPRQ中序遍歷：PRSQ(3)SPPRQ中序遍歷：QSPPRSQPR中序遍歷：QSPR(4)SQPRPp只有右子樹，用p的右孩子代替pp左、右子樹均非空沿p左子樹的根C的右子樹分支找到S，S的右子樹為空，將S的左子樹成為S的雙親Q的右子樹，用S取代p(5)或者用C代替p,p的右孩子成為S的右孩子。若C無右子樹，用C取代p(6)FPCPRCL中序遍歷：CLCPPRFFCPRCL中序遍歷：CLCPRF(6)FPCPRCLQQLSSL中序遍歷：CLC……QLQSLSPPRFFSCPRCLQQLSL中序遍歷：CLC……QLQSLSPRF(5)FSCPRCLQQLSL刪除算法例805012060110150557053刪除508060120110150557053刪除60805512011015053701042581365刪除1084256135刪除68425513StatusDeleteBST(BiTree&T,KeyTypekey){//算法9.7//若二叉排序樹T中存在關(guān)鍵字等于key的數(shù)據(jù)元素時，

//則刪除該數(shù)據(jù)元素結(jié)點p，并返回TRUE；否則返回FALSEif(!T)returnFALSE;//不存在關(guān)鍵字等于key的數(shù)據(jù)元素

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

returnDelete(T);elseif(LT(key,T->data.key))returnDeleteBST(T->lchild,key);elsereturnDeleteBST(T->rchild,key);}}//DeleteBSTStatusDelete(BiTree&p){//算法9.8//從二叉排序樹中刪除結(jié)點p，并重接它的左或右子樹

BiTreeq,s;if(!p->rchild){//右子樹空則只需重接它的左子樹

q=p;p=p->lchild;free(q);}elseif(!p->lchild){//只需重接它的右子樹

q=p;p=p->rchild;free(q);}else{//左右子樹均不空

q=p;s=p->lchild;while(s->rchild)//轉(zhuǎn)左，然后向右到盡頭

{q=s;s=s->rchild;}p->data=s->data;//s指向被刪結(jié)點的“后繼”

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

elseq->lchild=s->lchild;//重接*q的左子樹

free(s);}returnTRUE;}//Delete樹和森林6.4樹和森林樹的存儲結(jié)構(gòu)雙親表示法實現(xiàn)：定義結(jié)構(gòu)數(shù)組存放樹的結(jié)點，每個結(jié)點含兩個域：數(shù)據(jù)域：存放結(jié)點本身信息雙親域：指示本結(jié)點的雙親結(jié)點在數(shù)組中位置特點：找雙親容易，找孩子難typedefstructPTNode//節(jié)點結(jié)構(gòu){TElemTypedata;intparent;}PTNode;typedefstruct{//樹結(jié)構(gòu)

PTNodenodes[MAX_TREE_SIZE]intr,n;}abcdefhgiacdefghib-1011244406012345789dataparent如何找孩子結(jié)點孩子表示法多重鏈表：每個結(jié)點有多個指針域，分別指向其子樹的根結(jié)點同構(gòu)：結(jié)點的指針個數(shù)相等，為樹的度D結(jié)點不同構(gòu)：結(jié)點指針個數(shù)不等，為該結(jié)點的度ddatachild1child2……….childDdatadegreechild1child2……….childd孩子鏈表：每個結(jié)點的孩子結(jié)點用單鏈表存儲，再用含n個元素的結(jié)構(gòu)數(shù)組指向每個孩子鏈表孩子結(jié)點：typedefstructCTNode{intchild;//該結(jié)點在表頭數(shù)組中下標

structCTNode*next;//指向下一孩子結(jié)點}*ChildPtr;表頭結(jié)點：typedefstruct{TElemTypedata;//數(shù)據(jù)域

*ChildPtrfirstchild;//指向第一個孩子結(jié)點}CTBox;typedefstruct{//樹結(jié)構(gòu)

CTBoxnodes[MAX_TREE_SIZE];intr,n;}CTree;abcdefhgi6012345789acdefghibdatafc12^34^^867^5^^^^^如何找雙親結(jié)點帶雙親的孩子鏈表501234678acdefghibdatafc12348675^^^^^^^^^012235551parentabcdefhgi孩子兄弟表示法（二叉樹表示法）實現(xiàn)：用二叉鏈表作樹的存儲結(jié)構(gòu)，鏈表中每個結(jié)點的兩個指針域分別指向其第一個孩子結(jié)點和下一個兄弟結(jié)點特點操作容易破壞了樹的層次typedefstructCSNode{TElemTypedata;structCSNode*firstchild,*nsib;}CSNode;abcdefhgiabcdefghi^^^^^^^^^^樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^A^^BC^D^^E^對應(yīng)存儲存儲解釋解釋將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對每個結(jié)點，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空將二叉樹轉(zhuǎn)換成樹加線：若p結(jié)點是雙親結(jié)點的左孩子，則將p的右孩子，右孩子的右孩子，……沿分支找到的所有右孩子，都與p的雙親用線連起來抹線：抹掉原二叉樹中雙親與右孩子之間的連線調(diào)整：將結(jié)點按層次排列，形成樹結(jié)構(gòu)ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI森林轉(zhuǎn)換成二叉樹將各棵樹分別轉(zhuǎn)換成二叉樹將每棵樹的根結(jié)點用線相連以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹型結(jié)構(gòu)ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ二叉樹轉(zhuǎn)換成森林抹線：將二叉樹中根結(jié)點與其右孩子連線，及沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成孤立的二叉樹還原：將孤立的二叉樹還原成樹ABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ樹的遍歷森林的遍歷樹的遍歷可有2條搜索路徑:按層次遍歷:先根(次序)遍歷:后根(次序)遍歷:

若樹不空，則先訪問根結(jié)點，然后依次先根遍歷各棵子樹。

若樹不空，則先依次后根遍歷各棵子樹，然后訪問根結(jié)點。

若樹不空，則自上而下自左至右訪問樹中每個結(jié)點。

層次遍歷時頂點的訪問次序：ABCDEFGHIJK

先根遍歷時頂點的訪問次序：ABEFCDGHIJK

后根遍歷時頂點的訪問次序：EFBCIJKHGDAABCDEFGHIJK

BCDEFGHIJK1。森林中第一棵樹的根結(jié)點；2。森林中第一棵樹的子樹森林；3。森林中其它樹構(gòu)成的森林?？梢苑纸獬扇糠郑荷?/p>

若森林不空，則訪問森林中第一棵樹的根結(jié)點;先序遍歷森林中第一棵樹的子樹森林;先序遍歷森林中(除第一棵樹之外)其余樹構(gòu)成的森林。先序遍歷森林的遍歷即：依次從左至右對森林中的每一棵樹進行先根遍歷。

BCDEFGHIJK先序遍歷:BEFCDGHIJK

中序遍歷

若森林不空，則中序遍歷森林中第一棵樹的子樹森林;訪問森林中第一棵樹的根結(jié)點;中序遍歷森林中(除第一棵樹之外)其

余樹構(gòu)成的森林。即：依次從左至右對森林中的每一棵樹進行后根遍歷。

BCDEFGHIJK中序遍歷:EFBCIJKHGD

樹的遍歷和二叉樹遍歷的對應(yīng)關(guān)系？先根遍歷后根遍歷樹二叉樹森林先序遍歷先序遍歷中序遍歷中序遍歷二叉樹的應(yīng)用——哈夫曼樹(Huffman)6.6二叉樹的應(yīng)用哈夫曼樹(Huffman)——帶權(quán)路徑長度最短的樹定義路徑：從樹中一個結(jié)點到另一個結(jié)點之間的分支構(gòu)成這兩個結(jié)點間的~路徑長度：路徑上的分支數(shù)樹的路徑長度：從樹根到每一個結(jié)點的路徑長度之和樹的帶權(quán)路徑長度：樹中所有葉子結(jié)點的帶權(quán)路徑長度之和Huffman樹——設(shè)有n個權(quán)值{w1,w2,……wn}，構(gòu)造一棵有n個葉子結(jié)點的二叉樹，每個葉子的權(quán)值為wi,則wpl最小的二叉樹叫~例有4個結(jié)點，權(quán)值分別為7，5，2，4，構(gòu)造有4個葉子結(jié)點的二叉樹abcd7524WPL=7*2+5*2+2*2+4*2=36dcab2475WPL=7*3+5*3+2*1+4*2=46abcd7524WPL=7*1+5*2+2*3+4*3=35Huffman樹應(yīng)用最佳判定樹等級分數(shù)段比例ABCDE0~5960~6970~7980~8990~1000.050.150.400.300.10a<60a<90a<80a<70EYNDYNCYNBYNA70

a<80a<60CYNBYNDYNEYNA80

a<9060

a<70BACDEa<80a<70