二叉樹的遍歷算法

二叉樹的前序、后序的遞歸、非遞歸遍歷算法學(xué)生姓名：賀天立指導(dǎo)老師：湛新霞摘要本課程設(shè)計主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)。在課程設(shè)計中，系統(tǒng)開發(fā)平臺為Windows2000，程序設(shè)計設(shè)計語言采用VisualC++，程序運(yùn)行平臺為Windows98/2000/XP。用除遞歸算法前序，后續(xù)，中序遍歷樹外還通過非遞歸的算法遍歷樹。程序通過調(diào)試運(yùn)行，初步實現(xiàn)了設(shè)計目標(biāo)，并且經(jīng)過適當(dāng)完善后，將可以應(yīng)用在商業(yè)中解決實際問題。關(guān)鍵詞程序設(shè)計；C++；樹的遍歷；非遞歸遍歷1引言本課程設(shè)計主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)。1.1課程設(shè)計的任務(wù)構(gòu)造一棵樹并輸入數(shù)據(jù)，編寫三個函數(shù)，非別是樹的前序遞歸遍歷算法、樹的后序遞歸遍歷算法、樹的非遞歸中序遍歷算法（這里的非遞歸以中序為例）。在主程序中調(diào)用這三個函數(shù)進(jìn)行樹的遍歷，觀察用不同的遍歷方法輸出的數(shù)據(jù)的順序和驗證遞歸與非遞歸輸出的數(shù)據(jù)是否一樣。1.2課程設(shè)計的性質(zhì)由要求分析知，本設(shè)計主要要求解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實現(xiàn)。所以設(shè)計一個良好的前序、后序的遞歸、非遞歸遍歷算法非常重要。1.3課程設(shè)計的目的在程序設(shè)計中，可以用兩種方法解決問題：一是傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計方法，二是更先進(jìn)的面向?qū)ο蟪绦蛟O(shè)計方法[1]利用《數(shù)據(jù)結(jié)構(gòu)》課程的相關(guān)知識完成一個具有一定難度的綜合設(shè)計題目，利用C語言進(jìn)行程序設(shè)計。鞏固和加深對線性表、棧、隊列、字符串、樹、圖、查找、排序等理論知識的理解；掌握現(xiàn)實復(fù)雜問題的分析建模和解決方法（包括問題描述、系統(tǒng)分析、設(shè)計建模、代碼實現(xiàn)、結(jié)果分析等）；提高利用計算機(jī)分析解決綜合性實際問題的基本能力。樹的遍歷分為前序、中序和后序，可以用遞歸算法實現(xiàn)樹的三種遍歷。除了遞歸外還可以構(gòu)造棧，利用出棧和入棧來實現(xiàn)樹的前序遍歷、中序遍歷和后序遍歷。2需求分析（1）根據(jù)給定二叉樹的先序遍歷結(jié)果，構(gòu)造出該二叉樹；按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個字符），空格字符表示空樹。（2）給出該二叉樹的遞歸前序和后序遍歷結(jié)果還有非遞歸中序遍歷結(jié)果。二叉樹非遞歸遍歷是用顯示棧來存儲二叉樹的結(jié)點(diǎn)指針。前序遍歷時,按二叉樹前序遍歷的順序訪問結(jié)點(diǎn)并將結(jié)點(diǎn)的指針入棧,直到棧頂指針指向的結(jié)點(diǎn)的左指針域為空時取出棧頂指針并刪除棧頂指針，訪問剛?cè)〕龅闹羔樦赶虻慕Y(jié)點(diǎn)的右指針指向的結(jié)點(diǎn)并將其指針入棧,如此反復(fù)執(zhí)行且在有標(biāo)志的情況下實現(xiàn)前序非遞歸算法。前序遍歷二叉樹的遞歸遍歷為若二叉樹為空，則算法結(jié)束，否則（1）訪問根結(jié)點(diǎn)，（2）前序遍歷左子樹，（3）前序遍歷右子樹。后序遍歷得遞歸為若二叉樹非空，則依次執(zhí)行如下操作：（1）遍歷左子樹；（2）遍歷右子樹；（3）訪問根結(jié)點(diǎn)。3概要設(shè)計3.1數(shù)據(jù)存儲結(jié)構(gòu)二叉樹的存儲結(jié)構(gòu)typedefcharDataType;structBitreeNode{DataTypedata;BitreeNode*lchild;BitreeNode*rchild;};3.2基本操作T=CreateBitree();//創(chuàng)建樹Preorder(T);〃輸出樹的前序遍歷Postorder(T);〃輸出樹的后序遍歷Inorder2(T)；//輸出樹的非遞歸中序遍歷以下為流程圖:開始￥用前序輸入法構(gòu)造一顆二叉樹用前序遞歸算法輸出二叉樹用中序非遞歸算法輸出二叉樹Y釋放二叉樹用后序遞歸算法輸出二叉樹結(jié)束4詳細(xì)設(shè)計4.1數(shù)據(jù)類型定義二叉樹的定義：二叉樹的存儲結(jié)構(gòu)typedefcharDataType;structBitreeNode{DataTypedata;//二叉樹的數(shù)據(jù)BitreeNode*lchild;//指向左孩子的指針BitreeNode*rchild;〃指向右孩子的指針};4.2系統(tǒng)主要子程序詳細(xì)設(shè)計主程序模塊設(shè)計及用戶工作區(qū)模塊設(shè)計：voidmain()(structBitreeNode*T=0;//定義T為指向BitreeNode類型的指針T=CreateBitree();//用前序輸入法創(chuàng)建二叉樹printf("\n前序遍歷\n");Preorder(T);//用前序遞歸輸入法輸出二叉樹printf("\n后序遍歷\n");Postorder(T);〃用后序遞歸輸入法輸出二叉樹printf("\n中序遍歷(非遞歸八n");Inorder2(T);〃用中序非遞歸輸入法輸出二叉樹cout<<"\n";DeleteTree(T);〃釋放二叉樹}以下是各子函數(shù)的定義：創(chuàng)建二叉樹//按先序次序輸入二叉樹BitreeNode*CreateBitree()(charch;scanf(〃％c〃,&ch);BitreeNode*T=NULL;if(ch!='#')(T=(structBitreeNode*)(malloc(sizeof(structBitreeNode)));T->data=ch;T->lchild=CreateBitree();T->rchild=CreateBitree();}returnT;}先序遞歸遍歷二叉樹：voidPreorder(structBitreeNode*p)(if(p!=NULL)(printf(〃％c〃,p->data);Preorder(p->lchild);Preorder(p->rchild);后序遞歸遍歷二叉樹voidPostorder(structBitreeNode*p)(if(p!=NULL)(Postorder(p->lchild);Postorder(p->rchild);printf(〃％c〃,p->data);}}中序非遞歸遍歷二叉樹voidInorder2(BitreeNode*T)//中序遍歷二叉樹的非遞歸算法(BitreeNode*p;BitreeNode*stack[100];〃定義了一個棧的對象Sinttop=0;stack[top++]=T;〃根結(jié)點(diǎn)的指針進(jìn)棧while(top>0)(p=stack[top-1];while(p)(stack[top++]=p->lchild;//往左下走到底p=stack[top-1];}p=stack[--top];//空指針退棧if(top>0)(p=stack[--top];cout<<p->data;stack[top++]=p->rchild;〃訪問結(jié)點(diǎn)后向右下一步}}}⑤釋放存儲空間：voidDeleteTree(structBitreeNode*p)(if(p!=NULL)(DeleteTree(p->lchild);DeleteTree(p->rchild);free(p);}}5調(diào)試分析系統(tǒng)運(yùn)行主界面如圖5.1所示：cawC:\Wind2\cmd,exe請輸入一顆二叉樹S3在主菜單下，用戶輸入數(shù)據(jù)，按回車鍵。屏幕顯示如下圖所示S3固CAWindDws\5ystem32\cmd.exe睛輸入—顆二叉樹刎C腳如盹￡腳罪V啊序遍歷abcdefg同序遍歷cdbfgea何序遍歷（非遞歸〉cbdafeg請按任意鍵繼續(xù)...6總結(jié)“數(shù)據(jù)結(jié)構(gòu)”是計算機(jī)類各專業(yè)的核心課程，也是其他諸多類專業(yè)的重要選修課。我通過學(xué)習(xí)這門課，可以為理解、應(yīng)用和開發(fā)程序提供技術(shù)和方法支持，為后續(xù)課程的學(xué)習(xí)提供重要思想和方法基礎(chǔ)。同時對于我的邏輯思維培養(yǎng)和程序設(shè)計思想體系的建立有著重要的影響。在調(diào)試過程中，碰到諸多問題，比如定義表長過小，處理記錄數(shù)量錯誤時程序的異常，記錄沖突次數(shù)等等。處理這些問題異常麻煩，有時連續(xù)錯誤，摸不清頭緒，在不斷調(diào)試，詢問老師，和同學(xué)探討之后，終于解決，運(yùn)行成功。參考文獻(xiàn)李文軍，李師賢，周曉聰.C++作為計算機(jī)專業(yè)程序設(shè)計入門語言的實踐與探討.計算機(jī)科學(xué)，1999，26（4）：80?83唐浩強(qiáng).C程序設(shè)計（第三版）.清華大學(xué)出版社，2005嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）.清華大學(xué)出版社，1997F.BrokkenandK.Kubat.C++Annotations.Version4.4.0m，ICCE，UniversityofGroningen，Netherlands，1990.250?280附錄:#include"iostream"usingnamespacestd;typedefcharDataType;structBitreeNode(DataTypedata;BitreeNode*lchild;BitreeNode*rchild;};voidPreorder(structBitreeNode*p)//先序遍歷二叉樹(if(p!=NULL)(printf(〃％c〃,p->data);Preorder(p->lchild);Preorder(p->rchild);}}voidPostorder(structBitreeNode*p)//后序遍歷二叉樹(if(p!=NULL)(Postorder(p->lchild);Postorder(p->rchild);printf(〃％c〃,p->data);//a=&b;}}//PostorderBitreeNode*CreateBitree()//按先序次序輸入二叉樹(charch;scanf(〃％c〃,&ch);BitreeNode*T=NULL;if(ch!='#')(T=(structBitreeNode*)(malloc(sizeof(structBitreeNode)));T->data=ch;T->lchild=CreateBitree();T->rchild=CreateBitree();}returnT;}voidDeleteTree(structBitreeNode*p)//釋放存儲空間(if(p!=NULL)(DeleteTree(p->lchild);DeleteTree(p->rchild);free(p);}}//PostordervoidInorder2(BitreeNode*T)//中序遍歷二叉樹的非遞歸算法(BitreeNode*p;BitreeNode*stack[100];〃定義了一個棧的對象Sinttop=0;stack[top++]=T;〃根結(jié)點(diǎn)的指針進(jìn)棧while(top>0)(p=stack[top-1];while(p)(stack[top++]=p->lchild;//往左下走到底p=stack[top-1];}p=stack[--top];//空指針退棧if(top>0)(p=stack[--top];cout<<p->data;stack[top++]=p->rchild;〃訪問結(jié)點(diǎn)后向右下一步}//i