二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸和非遞歸算法

1、精選優(yōu)質(zhì)文檔-傾情為你奉上 數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計(jì)報(bào)告題 目： 二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸 和 非 遞 歸 算 法。 學(xué)生姓名： * * * 學(xué) 號(hào)： * 專業(yè)班級(jí)： 計(jì)算機(jī)科學(xué)與技術(shù)專業(yè) *班 同組姓名： * 指導(dǎo)教師： *老師 設(shè)計(jì)時(shí)間： 年下學(xué)期第 周 指導(dǎo)老師意見： 評(píng)定成績(jī)： 簽名： 日期：目 錄二、系統(tǒng)項(xiàng)目設(shè)計(jì). . . . . . . . . . . . . . .31.二叉樹的建立42.先序遍歷4 a.遞歸算法7 b.非遞歸算法73.中序遍歷6 a.遞歸算法7 b.非遞歸算法74.后序遍歷6 a.遞歸算法7 b.非遞歸算法75.主菜單程序45.子菜單程序41.二叉樹

2、的建立42.先序遍歷4 a.遞歸算法7 b.非遞歸算法72.中序遍歷6 a.遞歸算法7 b.非遞歸算法73.后序遍歷6 a.遞歸算法7 b.非遞歸算法74.主菜單程序45.子菜單程序4六、參考文獻(xiàn)23一 課題簡(jiǎn)介：通過這個(gè)課題設(shè)計(jì)主要掌握三種遍歷方法，包括前序遍歷，中序遍歷和后序遍歷，以及后續(xù)遍歷的非遞歸算法。二 項(xiàng)目設(shè)計(jì)： 非 遞 歸 算 法先序遍歷中序遍歷后序遍歷退出程序退出程序后序遍歷中序遍歷先序遍歷遞 歸 算 法系 統(tǒng) 主 界 面 圖1： 系統(tǒng)功能模塊圖準(zhǔn) 備系 統(tǒng) 登 錄選擇 遍歷中 序 遍 歷 后 序 遍 歷 先 序 遍 歷退 出 輸出遍歷結(jié)果 圖2：系統(tǒng)存盤功能流程圖 三 系統(tǒng)實(shí)

3、現(xiàn)系統(tǒng)核心代碼：1.二叉樹的建立：二叉樹的遍歷算法需要先建立二叉樹，二叉樹的建立需要建立棧和數(shù)組棧和數(shù)組的建立：typedef struct node /*結(jié)點(diǎn)定義*/ char data; struct node * lchild, * rchild; BinTreeNode;typedef struct /棧的定義BinTreeNode * ptr;int tag;StackNode;二叉樹的建立：BinTreeNode * CreateBinTree (BinTreeNode * Tree )/*,按先序序列建立二叉樹，輸入并建立一棵二叉樹Tree*/ char c;scanf(&quo

4、t;%c",&c);if(c='&') Tree = NULL;elseTree=(BinTreeNode * )malloc(sizeof(BinTreeNode);Tree->data=c;Tree->lchild= CreateBinTree(Tree->lchild);Tree->rchild= CreateBinTree(Tree->rchild); return(Tree);2.先序遍歷：a.遞歸算法：先序遍歷的遞歸算法：/*二叉樹的先序遍歷*/void PreOrder ( BinTreeNode *T )

5、if ( T != NULL ) printf("%c",T->data); PreOrder ( T->lchild ); PreOrder ( T->rchild ); b.非遞歸算法：先序遍歷的非遞歸算法：/*二叉樹的先序遍歷的非遞歸算法*/void PreOrderTwo ( BinTreeNode *T ) BinTreeNode *p,*SMax; int top=-1; p=T; /*初始化*/ do while ( p != NULL ) printf("%c",p->data); top+;Stop=p; p=p

6、->lchild; if( top >-1 ) /*棧非空*/ p=Stop; top-; /*取棧頂元素，出棧*/ p = p->rchild; while ( p != NULL ) |(top>-1); 2.中序遍歷：檢查該用戶是否可以使用該系統(tǒng)，如果沒有該用戶則重新輸入輸入，若用戶密碼輸入錯(cuò)誤，三次錯(cuò)誤時(shí)，退出登錄系統(tǒng)，并且該用戶被凍結(jié)。void common_user()/ 普通用戶登錄char ch;char pass20;char uname20;int i=0;Lab:if(i=3) exit(1);puts("n請(qǐng)輸入用戶名：");

7、cin>>uname;for(user *p= head; p!= NULL;p= p->next)if(!strcmp(uname,p->getmingzi()if(p->getstate() >=3) cout<<"該賬戶已經(jīng)被凍結(jié)！n"i+; goto Lab;else break;if(!p)cout<<"該用戶不存在，請(qǐng)重新輸入！n"i+;goto Lab;int x = 0;cout<<"請(qǐng)輸入密碼：n"while(ch=getch()!= -1 &a

8、mp;& ch!= 'r')passx+= ch;putchar('*');passx='0'if(!strcmp(p->getmima1(), pass)while(1)system("cls");int a;cout<<endl<<endl<<endl;cout<<" =歡迎使用本銀行="<<endl;cout<<" * 存 錢 1 *"<<endl;cout<<"

9、 * 取 錢 2 *"<<endl;cout<<" * 轉(zhuǎn) 帳 3 *"<<endl;cout<<" * 查 詢 4 *"<<endl;cout<<" * 掛 失 5 *"<<endl;cout<<" * 修改密碼 6 *"<<endl;cout<<" * 保存信息 7 *"<<endl;cout<<" * 返回上級(jí) 0 *"

10、;<<endl;cout<<" *"<<endl;cout<<"請(qǐng)輸入您的選擇:"<<endl;cin>>a;switch(a)case 1:cunqian(); system("cls");break;case 2:quqian();system("cls");break;case 3:zhuanzhang();system("cls");break ;case 4: chaxun();/cout<<"

11、;請(qǐng)輸入帳號(hào)："<<endl; /查詢system("cls");break;case 5:guashi();system("cls");return; case 6: xiugai();system("cls");break;case 7: cunyonghu();cunzhanghu();cunguanli();exit(1);case 0:return;else cout<<"密碼錯(cuò)誤！n"p->setstate(p->getstate()+1); /如果密碼錯(cuò)誤

12、，在以前基礎(chǔ)上加狀態(tài)一并存盤cunyonghu();i+;goto Lab;void display() /打印函數(shù)p= head;while(p!= NULL)cout<<"用戶名："<<p->getmingzi()<<endl<<"普通密碼："<<p->getmima1()<<endl<<"狀態(tài)："<<p->getstate()<<endl;p=p->next;1) 沒有此用戶：2）用戶密碼錯(cuò)誤：3）

13、密碼正確：3.后序遍歷：檢查該用戶是否可以使用本系統(tǒng)，三次密碼錯(cuò)誤則退出登錄系統(tǒng)。void manage() / 管理員char ch;char pass20;char uname20;int i=0;Lab:if(i=3) exit(1);puts("n請(qǐng)輸入用戶名：");cin>>uname;for(user *p= head; p!= NULL;p= p->next)if(!strcmp(uname,p->getmingzi()if(p->getstate() <0 ) cout<<"該賬戶已經(jīng)被凍結(jié)！n&qu

14、ot;i+; goto Lab;else break;if(!p)cout<<"該用戶不存在，請(qǐng)重新輸入！n"i+;goto Lab;int x = 0;cout<<"請(qǐng)輸入密碼：n"while(ch=getch()!= -1 && ch!= 'r')passx+= ch;putchar('*');passx='0'if(!strcmp("133", pass)while(1)system("cls");int x;cout&l

15、t;<endl<<endl<<endl;cout<<" =歡迎使用本銀行="<<endl;cout<<" * 開 戶 1 *"<<endl;cout<<" * 銷 戶 2 *"<<endl;cout<<" * 查 看 3 *"<<endl;cout<<" * 修改密碼 4 *"<<endl;cout<<" * 刪除賬戶 5 *

16、"<<endl;cout<<" * 修改賬戶狀態(tài) 6 *"<<endl;cout<<" * 修改用戶狀態(tài) 7 *"<<endl;cout<<" * 保存用戶信息 8 *"<<endl;cout<<" * 返回上級(jí) 0 *"<<endl;cout<<" *"<<endl;cout<<"請(qǐng)輸入您的選擇:"<<endl

17、;cin>>x;switch(x)case 1: system("cls");kaihu();system("cls");break;case 2:xiaohu(); /銷戶system("cls");break;case 3:chakan(); / 查詢system("cls");break;case 4: xiugai(); /修改密碼才system("cls");break;case 5:Delete(); /修改狀態(tài)system("cls");break;

18、case 6: xiugai1();system("cls"); break;case 7: xiugaiyh();system("cls"); break;case 8:cunyonghu();cunzhanghu();cunguanli();exit(1);case 0:return;else cout<<"n密碼錯(cuò)誤！n"i+;goto Lab;1) 密碼錯(cuò)誤：2）密碼正確：開戶功能：使用該功能可以擁有自己的賬戶，使用銀行系統(tǒng)void kaihu()char zhanghao20; /用戶帳號(hào)char id20; /

19、身份證號(hào)碼char mima20; /普通用戶密碼 int s= 0; /狀態(tài)初始化為0，等于3時(shí)賬戶凍結(jié)cout<<"tt增加用戶操作中n"cout<<"請(qǐng)輸入用戶的帳號(hào)：n"cin>>zhanghao;cout<<"請(qǐng)輸入用戶的身份證號(hào)碼：n"cin>>id;cout<<"請(qǐng)輸入普通用戶的密碼：n"cin>>mima;oz= new zhanghu;oz->setzhanghao(zhanghao);oz->seti

20、d(id);oz->setmima(mima);oz->setleixing(s);oz->next = headz;headz= oz;cout<<"注冊(cè)完成！n"system("pause");銷戶功能：取消沒有用了的賬戶。void xiaohu () /注銷一個(gè)帳戶char ch;char s20;int n=0; cout<<"請(qǐng)輸入用戶名："cin>>s;for(pz= headz; pz!= NULL; pz=pz->next)if(!strcmp(headz-&

21、gt;getzhanghao(), s) n=1;break;else if(!strcmp(pz->next->getzhanghao(), s)break;if(pz)cout<<"該用戶已經(jīng)找到，請(qǐng)確認(rèn)刪除(y/n)："cin>>ch;if(ch='y'| ch='Y')if(n=1) headz= headz->next;else pz->next= pz->next->next;cout<<"刪除成功！n"system("pause

22、");delete pz->next;/ 釋放節(jié)點(diǎn)空間if(!pz)cout<<"沒有找到該賬戶！n"掛失功能：void duzhanghu() int v; /狀態(tài)char u20;/ 帳號(hào)char w20; /身份證號(hào)碼char g20;/ 普通用戶密碼int n; double x;ifstream fin("銀行賬戶.txt");if(!fin)cout<<"銀行賬戶文件打開失??！n"else fin>>n;for(int i=0; i< n; i+)fin>&g

23、t;v>>u>>w>>g>>x;oz= new zhanghu;oz->setleixing(v);oz->setzhanghao(u);oz->setid(w);oz->setmima(g);oz->setyue(x);oz->next= headz;headz= oz;fin.close();cout<<"銀行賬戶打開成功！n"類的定義class zhanghu /賬戶類private:char zhanghao20; /帳號(hào)char id20; /身份證號(hào)碼char mim

24、a20; /普通用戶密碼double yue; /余額 int leixing; /賬戶類型public:zhanghu()yue= 0;char* getzhanghao()return zhanghao;void setzhanghao(char a1)strcpy(zhanghao,a1);char * getid()return id;void setid(char a2)strcpy(id,a2);char* getmima()return mima;void setmima(char a3)strcpy(mima,a3); double getyue() return yue;vo

25、id setyue(double a4)yue=a4;int getleixing() return leixing;void setleixing(int a5)leixing=a5;class zhanghu * next;zhanghu * headz=NULL;zhanghu * pz=NULL;zhanghu * qz=NULL;zhanghu * oz=NULL;class user /用戶類private:char mingzi20; /用戶姓名char mima120; /普通用戶密碼 int state; /賬戶狀態(tài) public: char* getmingzi()retu

26、rn mingzi;void setmingzi(char a)strcpy(mingzi,a);char* getmima1()return mima1;void setmima1(char a2)strcpy(mima1,a2);int getstate() return state;void setstate(int a3)state=a3; user * next;user * head=NULL;user * p=NULL;user * q=NULL;user * o=NULL;void duyonghu() /將賬用戶信息讀出 int v; /狀態(tài)char u20;/ 用戶名cha

27、r g20;/ 普通用戶密碼int n;ifstream fin("銀行用戶.txt");if(!fin)cout<<"銀行用戶文件打開失??！n"else fin>>n;for(int i=0; i< n; i+)fin>>v>>u>>g;o= new user;o->setstate(v);o->setmingzi(u);o->setmima1(g);o->next= head;head= o;cout<<"銀行用戶打開成功！n"v

28、oid cunyonghu() /將用戶信息存入ofstream fout("銀行用戶.txt");if(!fout)cout<<"打開文件失敗"<<endl;return;int i=0;p= head;while(p!=NULL)/計(jì)算鏈表中共有多少個(gè)節(jié)點(diǎn)i+;p=p->next;fout<<i<<'n'p=head;while(p!=NULL) /計(jì)算文件中共有多少個(gè)數(shù)據(jù)fout<<p->getstate()<<'t'fout<

29、<p->getmingzi()<<'t'fout<<p->getmima1()<<'n'p=p->next;/cout<<"文件存入成功!"<<endl;fout.close();void duzhanghu() /將賬戶信息讀出 int v; /狀態(tài)char u20;/ 帳號(hào)char w20; /身份證號(hào)碼char g20;/ 普通用戶密碼int n; double x;ifstream fin("銀行賬戶.txt");if(!fin)c

30、out<<"銀行賬戶文件打開失?。"else fin>>n;for(int i=0; i< n; i+)fin>>v>>u>>w>>g>>x;oz= new zhanghu;oz->setleixing(v);oz->setzhanghao(u);oz->setid(w);oz->setmima(g);oz->setyue(x);oz->next= headz;headz= oz;fin.close();cout<<"銀行賬戶打開成功！n"void cunzhanghu() /將賬戶信息存入ofstream fout("銀行賬戶.txt");if(!fout)cout<<"打開文件失敗"<<endl;return;int i=0;pz= headz;while(pz!=NULL)/計(jì)算鏈表中共有多少個(gè)節(jié)點(diǎn)i+;pz=pz->next;fout<<i<<'n'pz=headz;while(pz!=N