二叉樹的遍歷算法

1、二叉樹的前序、后序的遞歸、非遞歸遍歷算法學(xué)生姓名：賀天立 指導(dǎo)老師：湛新霞摘 要 本課程設(shè)計(jì)主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序 的非遞歸遍歷算法的實(shí)現(xiàn)。在課程設(shè)計(jì)中，系統(tǒng)開發(fā)平臺(tái)為 Windows 2000，程 序設(shè)計(jì)設(shè)計(jì)語言采用Visual C+，程序運(yùn)行平臺(tái)為Windows 98/2000/XP。用除 遞歸算法前序，后續(xù)，中序遍歷樹外還通過非遞歸的算法遍歷樹。程序通過調(diào)試 運(yùn)行，初步實(shí)現(xiàn)了設(shè)計(jì)目標(biāo)，并且經(jīng)過適當(dāng)完善后，將可以應(yīng)用在商業(yè)中解決實(shí) 際問題。關(guān)鍵詞程序設(shè)計(jì)；C+ ；樹的遍歷；非遞歸遍歷引 言本課程設(shè)計(jì)主要解決樹的前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞 歸

2、遍歷算法的實(shí)現(xiàn)。課程設(shè)計(jì)的任務(wù)構(gòu)造一棵樹并輸入數(shù)據(jù)，編寫三個(gè)函數(shù)，非別是樹的前序遞歸遍歷算法、樹的 后序遞歸遍歷算法、樹的非遞歸中序遍歷算法（這里的非遞歸以中序?yàn)槔?。?主程序中調(diào)用這三個(gè)函數(shù)進(jìn)行樹的遍歷，觀察用不同的遍歷方法輸出的數(shù)據(jù)的順 序和驗(yàn)證遞歸與非遞歸輸出的數(shù)據(jù)是否一樣。課程設(shè)計(jì)的性質(zhì)由要求分析知，本設(shè)計(jì)主要要求解決樹的前序、后序的遞歸、非遞歸遍歷算 法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)。所以設(shè)計(jì)一個(gè)良好的前序、后序的遞歸、 非遞歸遍歷算法非常重要。課程設(shè)計(jì)的目的在程序設(shè)計(jì)中，可以用兩種方法解決問題：一是傳統(tǒng)的結(jié)構(gòu)化程序設(shè)計(jì)方法，二是更先進(jìn)的面向?qū)ο蟪绦蛟O(shè)計(jì)方法1。利用數(shù)據(jù)結(jié)構(gòu)課程的相

3、關(guān)知識(shí)完成一個(gè)具有一定難度的綜合設(shè)計(jì)題目， 利用C語言進(jìn)行程序設(shè)計(jì)。鞏固和加深對(duì)線性表、棧、隊(duì)列、字符串、樹、圖、 查找、排序等理論知識(shí)的理解；掌握現(xiàn)實(shí)復(fù)雜問題的分析建模和解決方法（包括 問題描述、系統(tǒng)分析、設(shè)計(jì)建模、代碼實(shí)現(xiàn)、結(jié)果分析等）；提高利用計(jì)算機(jī)分 析解決綜合性實(shí)際問題的基本能力。樹的遍歷分為前序、中序和后序，可以用遞歸算法實(shí)現(xiàn)樹的三種遍歷。除了 遞歸外還可以構(gòu)造棧，利用出棧和入棧來實(shí)現(xiàn)樹的前序遍歷、中序遍歷和后序遍 歷。需求分析（1）根據(jù)給定二叉樹的先序遍歷結(jié)果，構(gòu)造出該二叉樹； 按先序次序輸入二叉樹中結(jié)點(diǎn)的值（一個(gè)字符），空格字符表示空樹。（2）給出該二叉樹的遞歸前序和后序遍歷結(jié)

4、果還有非遞歸中序遍歷結(jié)果。二叉樹非遞歸遍歷是用顯示棧來存儲(chǔ)二叉樹的結(jié)點(diǎn)指針。前序遍歷時(shí),按二叉樹前序 遍歷的順序訪問結(jié)點(diǎn)并將結(jié)點(diǎn)的指針入棧,直到棧頂指針指向的結(jié)點(diǎn)的左指針域?yàn)榭諘r(shí)取出 棧頂指針并刪除棧頂指針,訪問剛?cè)〕龅闹羔樦赶虻慕Y(jié)點(diǎn)的右指針指向的結(jié)點(diǎn)并將其指針入 棧,如此反復(fù)執(zhí)行且在有標(biāo)志的情況下實(shí)現(xiàn)前序非遞歸算法。前序遍歷二叉樹的遞歸遍歷為 若二叉樹為空，則算法結(jié)束，否則（1）訪問根結(jié)點(diǎn)，（2）前序遍歷左子樹，（3）前序遍歷 右子樹。后序遍歷得遞歸為若二叉樹非空，則依次執(zhí)行如下操作：（1）遍歷左子樹；（2）遍歷 右子樹；（3）訪問根結(jié)點(diǎn)。概要設(shè)計(jì)3.1 數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)二叉樹的存儲(chǔ)結(jié)構(gòu)type

5、def char DataType;struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;3.2 基本操作T=CreateBitree();/創(chuàng)建樹Preorder(T) ;/輸出樹的前序遍歷Postorder(T);/輸出樹的后序遍歷Inorder2(T)；/輸出樹的非遞歸中序遍歷以下為流程圖：詳細(xì)設(shè)計(jì)4.1 數(shù)據(jù)類型定義二叉樹的定義：二叉樹的存儲(chǔ)結(jié)構(gòu)typedef char DataType;struct BitreeNodeDataType data;/二叉樹的數(shù)據(jù)BitreeNode*lchild;/指向左孩

6、子的指針BitreeNode*rchild;/指向右孩子的指針;4.2 系統(tǒng)主要子程序詳細(xì)設(shè)計(jì)主程序模塊設(shè)計(jì)及用戶工作區(qū)模塊設(shè)計(jì)： void main()struct BitreeNode*T=0;/定義T為指向BitreeNode類型的指針T=CreateBitree();/ 用前序輸入法創(chuàng)建二叉樹prin tf( n 前序遍歷n);Preorder(T) ;/用前序遞歸輸入法輸出二叉樹prin tf( n 后序遍歷n);Postorder(T); /用后序遞歸輸入法輸出二叉樹 prin tf( n中序遍歷(非遞歸)n);Inorder2(T);/用中序非遞歸輸入法輸出二叉樹coutdata

7、=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;先序遞歸遍歷二叉樹：void Preorder(struct BitreeNode *p) if (p!=NULL)printf(%c,p-data);Preorder( p-lchild );Preorder(p-rchild );后序遞歸遍歷二叉樹void Postorder(struct BitreeNode *p) if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);

8、中序非遞歸遍歷二叉樹void Inorder2(BitreeNode *T)/ 中序遍歷二叉樹的非遞歸算法BitreeNode *p;BitreeNode * stack100;/定義了一個(gè)棧的對(duì)象sint top=0;stacktop+=T; /根結(jié)點(diǎn)的指針進(jìn)棧while (top0)p= stacktop-1;while (p)stacktop+= p-lchild/往左下走到底p= stacktop-1;p= stack-top;/ 空指針退棧if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/訪問結(jié)點(diǎn)后向右下一步 釋放存儲(chǔ)空間：v

9、oid DeleteTree(struct BitreeNode *p) if (p!=NULL)DeleteTree( p-lchild ); DeleteTree(p-rchild ) ; free(p);調(diào)試分析系統(tǒng)運(yùn)行主界面如圖 5.1 所示：caw乩已（亡請(qǐng)輸入一顆二叉樹在主菜單下，用戶輸入數(shù)據(jù)，按回車鍵。屏幕顯示如下圖所示S3血 CAWi nd Dws5ystem32cmd .exeS3晴輸入顆二叉樹孔皿F刪9丼丼網(wǎng)序遍歷abedefg 辰序遍歷 edbfgea 用序遍歷（非遞歸 cbdafeg請(qǐng)按任意鍵繼續(xù) 總結(jié)“ 數(shù)據(jù)結(jié)構(gòu) ” 是計(jì)算機(jī)類各專業(yè)的核心課程，也是其他諸多類專業(yè)的重

10、 要選修課。我通過學(xué)習(xí)這門課，可以為理解、應(yīng)用和開發(fā)程序提供技術(shù)和方法支 持，為后續(xù)課程的學(xué)習(xí)提供重要思想和方法基礎(chǔ)。同時(shí)對(duì)于我的邏輯思維培養(yǎng)和 程序設(shè)計(jì)思想體系的建立有著重要的影響。在調(diào)試過程中，碰到諸多問題，比如定義表長過小，處理記錄數(shù)量錯(cuò)誤時(shí) 程序的異常，記錄沖突次數(shù)等等。處理這些問題異常麻煩，有時(shí)連續(xù)錯(cuò)誤，摸不 清頭緒，在不斷調(diào)試，詢問老師,和同學(xué)探討之后，終于解決，運(yùn)行成功。參考文獻(xiàn)李文軍，李師賢，周曉聰.C+作為計(jì)算機(jī)專業(yè)程序設(shè)計(jì)入門語言的實(shí)踐與探討.計(jì)算機(jī)科學(xué)，1999, 26 （4）： 8083唐浩強(qiáng) C程序設(shè)計(jì)（第三版）清華大學(xué)出版社，2005嚴(yán)蔚敏，吳偉民數(shù)據(jù)結(jié)構(gòu)（C語言版

11、）清華大學(xué)出版社，1997F. Brokken and K. Kubat.C+ Annotations. Version 4.4.0m， ICCE，University of Groningen， Netherlands, 1990. 250280附錄：#includeiostream using namespace std; typedef char DataType; struct BitreeNodeDataTypedata;BitreeNode*lchild;BitreeNode*rchild;void Preorder(struct BitreeNode *p) / 先序遍歷二叉樹i

12、f (p!=NULL) printf(%c,p-data); Preorder( p-lchild ); Preorder(p-rchild );void Postorder(struct BitreeNode *p) / 后序遍歷二叉樹if (p!=NULL)Postorder( p-lchild ); Postorder(p-rchild ) ; printf(%c,p-data);/ a=&b;/PostorderBitreeNode *CreateBitree() /按先序次序輸入二叉樹 char ch;scanf(%c,&ch);BitreeNode* T=NULL;if(ch!=#

13、)T= (struct BitreeNode*)(malloc(sizeof(struct BitreeNode); T-data=ch;T-lchild=CreateBitree();T-rchild=CreateBitree();return T;void DeleteTree(struct BitreeNode *p)/ 釋放存儲(chǔ)空間if (p!=NULL)DeleteTree( p-lchild );DeleteTree(p-rchild ) ; free(p);/Postordervoid Inorder2(BitreeNode *T)/ 中序遍歷二叉樹的非遞歸算法BitreeNode *p;BitreeNode * stack100;/定義了一個(gè)棧的對(duì)象sint top=0; stacktop+=T;/根結(jié)點(diǎn)的指針進(jìn)棧while (top0)p= stacktop-1;while (p)stacktop+= p-lchild ;/往左下走到底p= stacktop-1;p= stack-top;/ 空指針退棧if (top0 )p=stack-top; coutdata; stacktop+= p-rchild;/訪問結(jié)點(diǎn)后向右下一步/if/wh