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

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