大學(xué)《數(shù)據(jù)結(jié)構(gòu)》第五章：樹和二叉樹-第三節(jié)-二叉樹的運(yùn)算

第三節(jié)二叉樹的運(yùn)算一、二叉樹的生成1．按廣義表表示二叉樹結(jié)構(gòu)生成二叉鏈表的算法上圖所示二叉樹的廣義表表示形式為：(A(B(，D(E，F(xiàn)))，C))。特點(diǎn)：靠近左括號的結(jié)點(diǎn)是在左子樹上，而逗號右邊的結(jié)點(diǎn)是在右子樹上。算法中用了一個指針數(shù)組來模擬棧存儲結(jié)點(diǎn)的雙親指針，根據(jù)讀入廣義表中的字符分四種不同的情況進(jìn)行處理：【算法描述】BinTNode*CreateTree(char*str){//str為存儲廣義表的字符串的指針BinTNode*st[100]；//用指針數(shù)組模擬棧BinTNode*p=NULL；inttop，k，j=0；top=-1；//置空棧charch=str[j]；//存放廣義表的字符串的數(shù)組BinTNode*b=NULL；while(ch!='\0')//循環(huán)讀廣義表字符串中字符{switch(ch){case'('：top++；st[top]=p；k=1;break；//左括號表示新的子樹的開始，所以剛建立的結(jié)點(diǎn)指針入棧case')'：top--；break;//右括號表示一個子樹的結(jié)束，棧頂元素沒有子樹，出棧case'，'：k=2；break;default：p=(BinTNode*)malloc(sizeof(BinTNode))；//讀到的是字符p->data=ch;//填寫數(shù)據(jù)域p->lchild=p->rchild=NULL；//填寫指針域if(b==NULL)//建立第一個結(jié)點(diǎn)b=p；else{switch(k){case1：st[top]->lchild=p;break；//前一個字符是'('，該結(jié)點(diǎn)應(yīng)該插入到左子樹case2：st[top]->rchild=p；break；//前一個字符是'，'該結(jié)點(diǎn)應(yīng)該插入到右子樹}}}j++；ch=str[j]；//讀取下一個字符}returnb；//返回根結(jié)點(diǎn)的指針}2．按完全二叉樹的層次順序依次輸入結(jié)點(diǎn)信息建立二叉鏈表的算法【算法思想】首先對一般的二叉樹添加若干個虛結(jié)點(diǎn)，使其成為完全二叉樹，然后依次輸入結(jié)點(diǎn)信息，若輸入的結(jié)點(diǎn)不是虛結(jié)點(diǎn)"@"，則建立一個新結(jié)點(diǎn)，若是第一個結(jié)點(diǎn)，則令其為根結(jié)點(diǎn)，否則將新結(jié)點(diǎn)作為左孩子或右孩子鏈接到它的雙親結(jié)點(diǎn)上。如此重復(fù)下去，直到輸入結(jié)束符號"#"時為止(假設(shè)結(jié)點(diǎn)數(shù)據(jù)域為字符型)。【算法描述】BinTreeCreateBinTree(BinTreebt){//Q[1．．n]是一個BinTNode類型的指針數(shù)組，front和rear分別是隊頭和隊尾指針BinTNode*Q[100]；//定義隊列BinTNode*s；intfront，rear；charch；ch=getchar()；bt=NULL；//置空二叉樹front=1；rear=0；//初始化隊列while(ch!='#')//假設(shè)結(jié)點(diǎn)值為單字符，#為終止符。{s=NULL；//先假設(shè)讀入的為虛結(jié)點(diǎn)"@"if(ch!='@'){s=(BinTNode*)malloc(sizeof(BinTNode))；//申請新結(jié)點(diǎn)s->data=ch；s->lchlid=s->rchiId=NULL；//新結(jié)點(diǎn)賦值｝//endif_1rear++；//隊尾指針自增Q[rear]=s；//將新結(jié)點(diǎn)地址或虛結(jié)點(diǎn)地址(NULL)入隊if(rear==1)//若rear為1，則說明是根結(jié)點(diǎn)，用bt指向它bt=s；else｛if(s!=NULL&&Q[front]!=NULL)//當(dāng)前結(jié)點(diǎn)及其雙親結(jié)點(diǎn)都不是虛結(jié)點(diǎn)if(rear%2==0)//rear為偶數(shù)，新結(jié)點(diǎn)應(yīng)作為左孩子Q[front]->lchild=s；e1se//rear為奇數(shù)，新結(jié)點(diǎn)應(yīng)作為右孩子Q[front]->rchild=s；if(rear%2！=0)front++；//rear為奇數(shù)，說明front所指結(jié)點(diǎn)的左右兒子都處理完了，因此front加1指向下一個雙親｝ch=getchar()；//讀下一個結(jié)點(diǎn)值}//endwhilereturnbt；}二、二叉樹的遍歷遍歷：是指沿著某條搜索路徑(線)周游二叉樹，依次對樹中每個結(jié)點(diǎn)訪問且僅訪問一次。遍歷方案從二叉樹的遞歸定義可知，一棵非空的二叉樹由根結(jié)點(diǎn)及左、右子樹這三個基本部分組成。因此，在任一給定結(jié)點(diǎn)上，可以按某種次序執(zhí)行三個操作：①訪問根結(jié)點(diǎn)本身(D)，②遍歷根結(jié)點(diǎn)的左子樹(L)，③遍歷根結(jié)點(diǎn)的右子樹(R)。以上三種操作有六種執(zhí)行次序：DLR（根左右）、LDR（左根右）、LRD（左右根）；DRL（根右左）、RDL（右根左）、RLD（右左根）。注意：前三種次序與后三種次序?qū)ΨQ，故只討論先左后右的前三種次序。1、遞歸遍歷算法三種遍歷的遞歸定義：（1）先序遍歷DLR（根左右）：也叫先根遍歷，若二叉樹非空，則依次執(zhí)行如下操作：①訪問根結(jié)點(diǎn)；②遍歷左子樹；③遍歷右子樹。（2）中序遍歷LDR（左根右）：也叫中根遍歷，若二叉樹非空，則依次執(zhí)行如下操作：①遍歷左子樹；②訪問根結(jié)點(diǎn)；③遍歷右子樹。（3）后序遍歷LRD（左右根）：也叫后根遍歷，若二叉樹非空，則依次執(zhí)行如下操作：①遍歷左子樹；②遍歷右子樹；③訪問根結(jié)點(diǎn)?！纠糠謩e寫出圖所示的二叉樹的前序、中序、后序遍歷序列?！敬鸢浮壳靶虮闅v序列：ABDCEF中序遍歷系列：DBAECF后序遍歷序列：DBEFCA【真題選解】（例題?分析題）假設(shè)二叉樹的RNL遍歷算法定義如下：若二叉樹非空，則依次執(zhí)行如下操作：(1)遍歷右子樹；(2)訪問根節(jié)點(diǎn)；(3)遍歷左子樹。已知一棵二叉樹如圖所示，請給出其RNL遍歷的結(jié)果序列。隱藏答案【解析】根據(jù)二叉樹的RNL（右根左）遍歷算法定義和我們已經(jīng)研究過的LNR（左根右）遍歷算法定義，可以寫出該二叉樹的RNL（右根左）遍歷的結(jié)果序列：GCFABD；二叉樹的LNR（左根右）遍歷的結(jié)果序列：DBAFCG；二者是對稱的?！敬鸢浮縂CFABD三種遍歷的算法（1）前序遍歷遞歸算法voidPreorder(BinTreebt){//采用二叉鏈表存儲結(jié)構(gòu)，并設(shè)結(jié)點(diǎn)值為字符型if(bt!=NULL){printf("%c"，bt->data)；//訪問根結(jié)點(diǎn)Preorder(bt->lchild)；//前序遍歷左子樹preorder(bt->rchild)；//前序遍歷右子樹｝｝（2）中序遍歷遞歸算法voidInorder(BinTreebt){if(bt!=NULL){Inorder(bt->lchild)；//中序遍歷左子樹printf("%c"，bt->data)；//訪問根結(jié)點(diǎn)Inorder(bt->rchild)；//中序遍歷右子樹｝｝（3）后序遍歷遞歸算法voidPostorder(BinTreebt){if(bt!=NULL){Postorder(bt->lchild)；//中序遍歷左子樹Postorder(bt->rchild)；//中序遍歷右子樹printf("%c"，bt->data)；//訪問根結(jié)點(diǎn)｝｝2、二叉樹遍歷的非遞歸算法(1)利用棧的非遞歸中序遍歷算法：voidInorderl(BinTreebt){//采用二叉鏈表存儲結(jié)構(gòu)SeqStackS；BinTNode*P；InitStack(&S)；Push(&S，bt)；//根結(jié)點(diǎn)入棧while(!StackEmpty(&S)){while(GetTop(&S))//讀棧頂元素，當(dāng)棧頂不為空Push(&S，GetTop(&S)->lchild)；//左孩子依次入棧，直到左子樹空為止p=Pop(&S)；//最后一個入棧的空指針退棧if(!StackEmpty(&S)){printf("%c"，GetTop(&S)->data)；//訪問根結(jié)點(diǎn)p=Pop(&S)；Push(&S，p->rchild)；//右子樹進(jìn)棧｝｝｝（2）利用指針數(shù)組模擬棧實現(xiàn)的非遞歸中序遍歷算法：voidInorder2(B1nTreebt)｛//二叉樹非遞歸中序遍歷算法BinTNode*ST[100]；//用指針數(shù)組模擬棧inttop=0；//初始化數(shù)組ST[top]=bt；do{while(ST[top]!=NULL)//根結(jié)點(diǎn)及其所有的左結(jié)點(diǎn)地址裝入數(shù)組{top=top+1；ST[top]=ST[top-1]->lchild；｝top=top-1；//最后一個入數(shù)組的空指針退"棧"if(top>=0)//判數(shù)組中地址是否訪問完{printf("%c"，ST[top]->data)；//訪問結(jié)點(diǎn)ST[top]=ST[top]->rchild；//掃描右子樹｝｝while(top!=-1)；｝(3)利用棧的非遞歸前序遍歷算法。算法思想：利用棧先將二叉樹根結(jié)點(diǎn)指針入棧，然后執(zhí)行出棧，獲取棧頂元素值(即結(jié)點(diǎn)指針)，若不為空值，則訪問該結(jié)點(diǎn)，再將右、左子樹的根結(jié)點(diǎn)指針分別入棧，依次重復(fù)出棧、入棧，直至棧空為止。voidPreorderl(BinTreebt){SeqStackS；InitStack(&S)；//初始化棧Push(&S，bt)，//根結(jié)點(diǎn)指針進(jìn)棧while(!StackEmpty(&S)){bt=Pop(&S)；//出棧if(bt!=NULL){printf("%c"，bt->data)；//訪問結(jié)點(diǎn)，假設(shè)數(shù)據(jù)域為字符型Push(&S，bt->rchild)；//右子樹入棧先訪問左子樹，棧先進(jìn)后出Push(&S，bt->lchiid)；//左子樹入棧}}}(4)非遞歸的按層遍歷二叉鏈表樹。按層遍歷二叉樹：從上到下，從左到右遍歷二叉樹?！纠繉ο聢D二叉樹按層進(jìn)行遍歷【答案】ABCDEF算法思想：采用一隊列Q，若樹不空，先將二叉樹根結(jié)點(diǎn)輸出，并將根結(jié)點(diǎn)指針入隊，然后出隊。若根結(jié)點(diǎn)有左子樹，則將左子樹的根結(jié)點(diǎn)輸出并將其指針入隊；若其有右子樹，則將其右子樹的根結(jié)點(diǎn)輸出并將其指針入隊，再出隊，如此下去，直至隊列空為止。voidTransLevel(BinTreebt)｛cirQueueQ；//按層遍歷二叉樹，從上到下，從左到右InitQueue(&Q)；//初始化隊列為空隊列if(bt==NULL)return；e1se{printf("%c"，bt->data)；//輸出根結(jié)點(diǎn)，假設(shè)其數(shù)據(jù)域為字符型EnQueue(&Q，bt)；//根結(jié)點(diǎn)指針入隊while(!QueueEmpty(&Q))｛bt=DeQueue(&Q)；//出隊列if(bt->rchild!=NULL){printf("%c"，bt->lchild->data)；//輸出左子樹根結(jié)點(diǎn)EnQueue(&Q，bt->1child)；//左子樹入隊｝if(bt->rchild!=NULL){printf("%c"，bt->rchild->data)；//輸出右子樹根結(jié)點(diǎn)EnQueue(&Q，bt->rchild);//右子樹入隊列}｝//endofthewhile｝//endoftheif}3、由遍歷序列恢復(fù)二叉樹（多次在全國自學(xué)考試試題中出現(xiàn)）（1）已知二叉樹的前序遍歷序列和中序遍歷序列，可以唯一地恢復(fù)該二叉樹。原則是：在前序序列中確定根結(jié)點(diǎn)（最前面那個結(jié)點(diǎn)一定是根結(jié)點(diǎn)），然后根據(jù)根結(jié)點(diǎn)在中序序列中的位置分出根結(jié)點(diǎn)的左、右子樹（根結(jié)點(diǎn)前面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的左子樹上的結(jié)點(diǎn)，根結(jié)點(diǎn)后面的那些結(jié)點(diǎn)為根結(jié)點(diǎn)的右子樹上的結(jié)點(diǎn)）?；謴?fù)該二叉樹的任何一棵子樹的過程仍然遵循這個原則?！纠恳阎豢枚鏄涞那靶虮闅v序列與中序遍歷序列分別為前序遍歷序列：ABCDEFGHI中序遍歷序列：BCAEDGHFI試恢復(fù)該二叉樹。【解答】按照上述分解原則求得整棵二叉樹的過程如所示。同理，已知二叉樹的中序遍歷序列和后序遍歷序列，也可以唯一地恢復(fù)該二叉樹，只是在后序序列中去確定根結(jié)點(diǎn)（最后面那個結(jié)點(diǎn)一定是根結(jié)點(diǎn)），而在中序序列中分出左右子樹的過程與上述過程沒有區(qū)別。已知二叉樹的前序遍歷序列和后序遍歷序列，無法唯一地恢復(fù)該二叉樹，因為無法確定左右子樹。三、二叉樹應(yīng)用舉例【例1】已知二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)，求二叉樹的深度?！菊骖}】【分析】若一棵二叉樹為空，則它的深度為0，否則它的深度等于其左右子樹中的最大深度加l。設(shè)depl和depr分別表示左右子樹的深度，則二叉樹的深度為：max(depl，depr)+1【算法描述】intBinTreeDepth(BinTreebt){intdepl，depr；if(bt==NULL)return0；//對于空樹，返回0值，結(jié)束遞歸else{depl=BinTreeDepth(bt->lchild)；//計算左子樹的深度depr=BinTreeDepth(bt->rchild)；//計算右子樹的深度if(depl>depr)returndepl+1；elsereturndepr+1；}}【例2】以二叉鏈表為存儲結(jié)構(gòu)，試編寫在二叉樹中查找值為x