二叉樹的遍歷(共9頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 荊楚理工學(xué)院 數(shù)據(jù)結(jié)構(gòu)課程設(shè)計 學(xué)院:計算機(jī)工程學(xué)院 班 級: 計算機(jī)科學(xué)與技術(shù)（1）班 學(xué)生姓名: 學(xué) 號: . 設(shè)計地點(diǎn)（單位） 荊楚理工學(xué)院 設(shè)計題目： 二叉樹遍歷 完成日期： 2010年 12 月 20 日 指導(dǎo)教師評語: 成績(五級記分制): 教師簽名: 一目的更好的了解二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)流程及操作步驟。加深理論知識，提高實(shí)踐能力。二問題描述二叉樹的中序、前序、后序的遞歸、非遞歸遍歷算法，層次序的非遞歸遍歷算法的實(shí)現(xiàn)，建樹的實(shí)現(xiàn)。三概要設(shè)計1.創(chuàng)建二叉樹2.二叉樹的遞歸遍歷算法（前、中、后）3.二叉

2、樹的層次遍歷算法4.二叉樹的非遞歸遍歷算法（前、中、后）5.退出以選擇面板開始，顯得更為清晰。其中3，4，5，6，8為添加內(nèi)容，有助于更好的了解二叉樹。四詳細(xì)設(shè)計1.創(chuàng)建二叉樹(1)定義二叉樹結(jié)點(diǎn)值的類型為字符型。(2)結(jié)點(diǎn)個數(shù)不超過10個。(3)按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空樹。2.二叉樹的遞歸遍歷算法（前、中、后）DLR(1)訪問根結(jié)點(diǎn)。(2)先序遍歷根結(jié)點(diǎn)的左子數(shù)。(3)先序遍歷根結(jié)點(diǎn)的右子數(shù)。LDR(1)先序遍歷根結(jié)點(diǎn)的左子數(shù)。(2)訪問根結(jié)點(diǎn)。(3)先序遍歷根結(jié)點(diǎn)的右子數(shù)。LRD(1)先序遍歷根結(jié)點(diǎn)的左子數(shù)。(2)先序遍歷根結(jié)點(diǎn)的右子數(shù)。(3)訪問根結(jié)點(diǎn)。3.

3、二叉樹的層次遍歷算法(1)訪問該元素所指結(jié)點(diǎn)。(2)若該元素所指結(jié)點(diǎn)的左右孩子結(jié)點(diǎn)非空，則該元素所指結(jié)點(diǎn)的左孩子指針和右孩子指針順序入隊。4.二叉樹的非遞歸遍歷算法（前、中、后）（1）非遞歸的先序遍歷算法a.訪問結(jié)點(diǎn)的數(shù)據(jù)域。b.指針指向p的左孩子結(jié)點(diǎn)。c.從棧中彈出棧頂元素。d.指針指向p的右孩子結(jié)點(diǎn)。（2）非遞歸的中序遍歷算法a.指針指向p的左孩子結(jié)點(diǎn)。b.從棧中彈出棧頂元素。c.訪問結(jié)點(diǎn)的數(shù)據(jù)域。d.指針指向p的右孩子結(jié)點(diǎn)。（3）非遞歸的后序遍歷算法bt是要遍歷樹的根指針，后序遍歷要求在遍歷完左右子樹后，再訪問根。需要判斷根結(jié)點(diǎn)的左右子樹是否均遍歷過?？刹捎脴?biāo)記法，結(jié)點(diǎn)入棧時，配一個標(biāo)志

4、tag一同入棧(1：遍歷左子樹前的現(xiàn)場保護(hù)，2：遍歷右子樹前的現(xiàn)場保護(hù))。首先將bt和tag(為1)入棧，遍歷左子樹；返回后，修改棧頂tag為2，遍歷右子樹；最后訪問根結(jié)點(diǎn)。5.退出五測試數(shù)據(jù)與分析abcdefg六源代碼#include "iostream.h"#include "stdlib.h"#include "stdio.h"typedef char ElemType;/定義二叉樹結(jié)點(diǎn)值的類型為字符型const int MaxLength=10;/結(jié)點(diǎn)個數(shù)不超過10個typedef struct BTNode ElemType

5、 data; struct BTNode *lchild,*rchild;BTNode,* BiTree;void CreateBiTree(BiTree &T)/按先序次序輸入，構(gòu)造二叉鏈表表示的二叉樹T，空格表示空樹/ if(T) return; char ch; ch=getchar(); /不能用cin來輸入，在cin中不能識別空格。 if(ch=' ') T=NULL; else if(!(T=(BTNode *)malloc(sizeof(BTNode) cout<<"malloc fail!" T->data=ch;

6、CreateBiTree(T->lchild); CreateBiTree(T->rchild); void PreOrderTraverse(BiTree T)/先序遍歷 if(T) cout<<T->data<<' ' PreOrderTraverse(T->lchild); PreOrderTraverse(T->rchild); void InOrderTraverse(BiTree T)/中序遍歷 if(T) InOrderTraverse(T->lchild); cout<<T->data

7、<<' ' InOrderTraverse(T->rchild); void PostOrderTraverse(BiTree T)/后序遍歷 if(T) PostOrderTraverse(T->lchild); PostOrderTraverse(T->rchild); cout<<T->data<<' ' void LevelOrderTraverse(BiTree T)/層序遍歷 BiTree QMaxLength; int front=0,rear=0; BiTree p; if(T) /根結(jié)

8、點(diǎn)入隊 Qrear=T; rear=(rear+1)%MaxLength; while(front!=rear) p=Qfront; /隊頭元素出隊 front=(front+1)%MaxLength; cout<<p->data<<' ' if(p->lchild) /左孩子不為空，入隊 Qrear=p->lchild; rear=(rear+1)%MaxLength; if(p->rchild) /右孩子不為空，入隊 Qrear=p->rchild; rear=(rear+1)%MaxLength; /非遞歸的先序遍歷算

9、法void NRPreOrder(BiTree bt) BiTree stackMaxLength,p; int top; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top>0) while(p!=NULL) cout<<p->data; stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop; p=p->rchild; /非遞歸的中序遍歷算法void NRInOrder(BiTree bt) BiTree stackMaxLength,p; int t

10、op; if (bt!=NULL) top=0;p=bt; while(p!=NULL|top>0) while(p!=NULL) stacktop=p; top+; p=p->lchild; if (top>0) top-; p=stacktop;cout<<p->data; p=p->rchild; /非遞歸的后序遍歷算法typedef struct BiTree ptr; int tag;stacknode;void NRPostOrder(BiTree bt) stacknode sMaxLength,x; BiTree p=bt; int t

11、op; if(bt!=NULL) top=0;p=bt; do while (p!=NULL) /遍歷左子樹 stop.ptr = p; stop.tag = 1; /標(biāo)記為左子樹 top+; p=p->lchild; while (top>0 && stop-1.tag=2) x = s-top; p = x.ptr; cout<<p->data; /tag為R，表示右子樹訪問完畢，故訪問根結(jié)點(diǎn) if (top>0) stop-1.tag =2; /遍歷右子樹 p=stop-1.ptr->rchild; while (top>0

12、);/PostOrderUnrecvoid main() BiTree T; T=NULL; int select; /cout<<"請按先序次序輸入各結(jié)點(diǎn)的值，以空格表示空樹(輸入時可連續(xù)輸入):"<<endl;/ CreateBiTree(T); while(1) cout<<"nn請選擇要執(zhí)行的操作:n" cout<<"1.創(chuàng)建二叉樹n" cout<<"2.二叉樹的遞歸遍歷算法（前、中、后）n" cout<<"3.二叉樹的層次遍

13、歷算法n"cout<<"4.二叉樹的非遞歸遍歷算法（前、中、后）n" cout<<"0.退出n" cin>>select; switch(select) case 0:return; case 1: cout<<"請按先序次序輸入各結(jié)點(diǎn)的值，以空格表示空樹(輸入時可連續(xù)輸入):"<<endl; CreateBiTree(T); break; case 2: if(!T) cout<<"未建立樹，請先建樹！" else cout<<"n先序遍歷:n" PreOrderTraverse(T); cout<<"n中序遍歷:n" InOrderTraverse(T); cout<<"n后序遍歷:n" PostOrderTraverse(T); break; case 3: cout<<"n層序遍歷:n" LevelOrderTraverse(T); break; case 4: if(!T) cout<<"未建立樹，請先建樹！" else c