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

1、數(shù)據(jù)結(jié)構(gòu) 課程設(shè)計報告題 目： 二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸和 非 遞 歸 算 法。學(xué)生姓名學(xué)號學(xué)生姓名學(xué)號專業(yè)班級： 計算機科學(xué)與技術(shù)專業(yè)*班*X* *X* *X* *Jx *X* p* p* *X* *X* *X* *Jx *X* p* p* p* p* p*指導(dǎo)教師：*老師設(shè)計時間：年下學(xué)期第 周一、課題簡介二、系統(tǒng)項目設(shè)計 TOC o 1-5 h z HYPERLINK l bookmark10 o Current Document 三、系統(tǒng)實現(xiàn) 3 HYPERLINK l bookmark14 o Current Document 二叉樹的建立 4 HYPERLINK

2、l bookmark18 o Current Document 先序遍歷 4a.遞歸算法 b. 非遞歸算法中序遍歷 6 HYPERLINK l bookmark20 o Current Document a. 遞歸算法7 HYPERLINK l bookmark26 o Current Document b非遞歸算法7后序遍歷a. 遞歸算法 b. 非遞歸算法主菜單程序 5. 子菜單程序18系統(tǒng)測試18 TOC o 1-5 h z 二叉樹的建立 4先序遍歷 4a.遞歸算法7b非遞歸算法72.中序遍歷a.遞歸算法b.非遞歸算法后序遍歷a. 遞歸算法b. 非遞歸算法主菜單程序 4子菜單程序 422五

3、、小結(jié)2223六、參考文獻23一 課題簡介：通過這個課題設(shè)計主要掌握三種遍歷方法，包括前序遍歷，中序遍歷和后序遍歷，以及 后續(xù)遍歷的非遞歸算法。二 項目設(shè)計：圖 1 ： 系統(tǒng)功能模塊圖后序遍歷圖 2 ：系統(tǒng)存盤功能流程圖三 系統(tǒng)實現(xiàn)系統(tǒng)核心代碼：二叉樹的建立：二叉樹的遍歷算法需要先建立二叉樹，二叉樹的建立需要建立棧和數(shù)組 棧和數(shù)組的建立：typedef struct node/*結(jié)點定義*/ char data;struct node * lchild, * rchild; BinTreeNode;typedef struct /棧的定義BinTreeNode * ptr; int tag;S

4、tackNode;二叉樹的建立：BinTreeNode * CreateBinTree (BinTreeNode * Tree ) /*,按先序序列建立二叉樹，輸入并建立一棵二叉樹 Tree*/ char c; scanf(%c,&c); if(c=&) Tree = NULL;else Tree=(BinTreeNode * )malloc(sizeof(BinTreeNode); Tree-data=c;Tree-lchild= CreateBinTree(Tree-lchild);Tree-rchild= CreateBinTree(Tree-rchild); return(Tree);

5、按先序序列建立二叉樹，輸入先序序列:ab&c&先序遍歷：a.遞歸算法：先序遍歷的遞歸算法：/*二叉樹的先序遍歷*/ void PreOrder ( BinTreeNode *T ) if ( T != NULL ) printf(%c,T-data); PreOrder ( T-lchild ); PreOrder ( T-rchild );法單算歸主排歸遞回出遞非返退X- X- X- X-12 3 0KHKH二叉樹遞歸算法的先序遍歷結(jié)果為:abc請按任意犍繼續(xù) 二叉樹的先序遍歷：選擇菜法單 W歸主排 歸遞回岀 遞非返退 二叉樹的先序遍歷：選擇菜法單 W歸主排 歸遞回岀 遞非返退 w f F

6、12 3 0b.非遞歸算法:先序遍歷的非遞歸算法：/*二叉樹的先序遍歷的非遞歸算法*/void PreOrderTwo ( BinTreeNode *T )BinTreeNode *p,*SMax;int top=-1;p=T;/*初始化*/dowhile ( p != NULL ) printf(%c,p-data); top+;Stop=p; p=p-lchild;if( top -1 ) /*棧非空*/p=Stop; top-; /*取棧頂元素，出棧*/ p = p-rchild;while ( p != NULL ) |(top-1);-叉樹非遞歸算法的先序遍歷結(jié)果為:abc請按任意犍

7、繼縹.2.中序遍歷：檢查該用戶是否可以使用該系統(tǒng)，如果沒有該用戶則重新輸入輸入，若用戶密碼輸入錯誤，三次錯誤時，退出登錄系統(tǒng)，并且該用戶被凍結(jié)。void common_user()/ 普通用戶登錄char ch;char pass20;char uname20;int i=0;Lab:if(i=3) exit(1);puts(n 請輸入用戶名：);cinuname;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;e

8、lse break;if(!p)cout該用戶不存在，請重新輸入！ n;i+;goto Lab;int x = 0;cout請輸入密碼：n;while(ch=getch()!= -1 & ch!= r) passx+= ch; putchar(*);passx=0; if(!strcmp(p-getmima1(), pass)while(1)system(cls);int a;coutendlendlendl;cout歡迎使用本銀行:=endl;cout存錢 1*endl;cout取錢 2*endl;cout轉(zhuǎn)帳 3*endl;cout查詢 4*endl;cout掛失 5*endl;cout修

9、改密碼6*endl;cout保存信息 7*endl;cout返回上級 0*endl;cout*endl;cou t請輸入您的選擇：endl;cina;switch(a)case 1:cunqian(); system(cls);break;case 2:quqian();system(cls);break;case 3:zhuanzhang();system(cls);break ;case 4:chaxun();/cout請輸入帳號：endl;/查詢system(cls);break;case 5:guashi();system(cls);return;case 6: xiugai();sy

10、stem(cls);break;case 7:cunyonghu();cunzhanghu();cunguanli();exit(1);case 0:return;elsecout密碼錯誤！ n;p-setstate(p-getstate()+1); /如果密碼錯誤，在以前基礎(chǔ)上加狀態(tài)一并存盤cunyonghu();i+;goto Lab;void display() /打印函數(shù)p= head;while(p!= NULL)cout用戶名：p-getmingzi()endl普通密碼： getmima1()uname;for(user *p= head; p!= NULL;p= p-next)i

11、f(!strcmp(uname,p-getmingzi()if(p-getstate() 0 )coutvv該賬戶已經(jīng)被凍結(jié)！ n;i+;goto Lab;else break;if(!p)coutvv該用戶不存在，請重新輸入！ n;i+;goto Lab;int x = 0;coutvv請輸入密碼：n;while(ch=getch()!= -1 & ch!= r)passx+= ch;putchar(*);passx=0;if(!strcmp(133, pass)while(1)system(cls);int x;coutendlendlendl;coutcoutvv=歡迎使用本銀行=vve

12、ndl;coutx;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;case 6:xiugai1();system(cls);break;case 7:xiugaiyh();system(cls);break;case 8:c

13、unyonghu();cunzhanghu();cunguanli();exit(1);case 0:return;elsecoutvvn 密碼錯誤！ n;i+;goto Lab;1) 密碼錯誤：請輸入用戶名:123請輸入密碼：密碼錯誤！請輸入用戶名:2)密碼正確：= = = = = = = = = = = = = 歡迎使用本銀行f =開1銷2XXXXX查3XXXXX修改密碼4XXXXX刪除賬戶5餐餐餐餐餐修改賬戶】戌態(tài)6餐餐餐餐餐修改用戶斗戌態(tài)7餐餐餐餐餐保存匸冃戶信息8返回二級0XXXXX請輸入您的選擇:開戶功能：使用該功能可以擁有自己的賬戶，使用銀行系統(tǒng)void kaihu()char

14、zhanghao20;/用戶帳號char id20;/身份證號碼char mima20;/普通用戶密碼int s= 0;/狀態(tài)初始化為 0，等于 3 時賬戶凍結(jié)coutvvtt增加用戶操作中n;coutzhanghao;coutvv請輸入用戶的身份證號碼：n;cinid;coutvv，請輸入普通用戶的密碼：n;cinmima;oz= new zhanghu;oz-setzhanghao(zhanghao);oz-setid(id);oz-setmima(mima);oz-setleixing(s);oz-next = headz;headz= oz;coutvv注冊完成！ n;system(p

15、ause);銷戶功能：取消沒有用了的賬戶。void xiaohu () /注銷一個帳戶char ch;char s20;int n=0;coutvv請輸入用戶名：；cins;for(pz= headz； pz!= NULL； pz=pz-next)if(!strcmp(headz-getzhanghao(), s)n=1；break；else if(!strcmp(pz-next-getzhanghao(), s) break；if(pz)coutvv該用戶已經(jīng)找到，請確認刪除(y/n)：cinch；if(ch=y| ch=Y)if(n=1) headz= headz-next；elsepz-

16、next= pz-next-next；coutvv刪除成功！ n;system(pause)；delete pz-next;/ 釋放節(jié)點空間if(!pz)coutvv沒有找到該賬戶！ n;掛失功能：void duzhanghu()int v; /狀態(tài) char u20;/ 帳號 char w20; / 身份證號碼 char g20;/ 普通用戶密碼int n; double x;ifstream fin(銀行賬戶.txt);if(!fin)coutvv銀行賬戶文件打開失敗！ n;elsefinn;for(int i=0; ivuwgx;oz= new zhanghu; oz-setleixin

17、g(v); oz-setzhanghao(u); oz-setid(w); oz-setmima(g); oz-setyue(x); oz-next= headz;headz= oz;fin.close(); coutvv銀行賬戶打開成功！ n;請輸入帳號:xixi該用戶己經(jīng)找到，請確認是否掛失(y/n) y 掛失完成！請按任意鍵繼續(xù) 類的定義class zhanghu/賬戶類private:charzhanghao20;/帳號charid20;/身份證號碼charmima20;/普通用戶密碼doubleyue;/余額intleixing;/賬戶類型public:zhanghu()yue= 0

18、;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;void setyue(double a4)yue=a4;int getleixing()return leixing;void setleix

19、ing(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()return mingzi;void setmingzi(char a)strcpy(mingzi,a);char* getmima1()return mim

20、a1;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;/ 用戶名char g20;/ 普通用戶密碼int n;ifstream fin(” 銀行用戶.txt);if(!fin)coutvv銀行用戶文件打開失??！ n;elsefi

21、nn;for(int i=0; ivug;o= new user;o-setstate(v);o-setmingzi(u);o-setmima1(g);o-next= head;head= o;coutvv銀行用戶打開成功！ n;void cunyonghu()/將用戶信息存入ofstream fout(” 銀行用戶.txt); if(!fout)coutvv”打開文件失敗vvendl;return;int i=0;p= head;while(p!=NULL)計算鏈表中共有多少個節(jié)點 i+; p=p-next;foutvvivvn;p=head;while(p!=NULL)/計算文件中共有多少

22、個數(shù)據(jù)foutvvp-getstate()vvt; foutvvp-getmingzi()vvt; foutvvp-getmima1()vvn; p=p-next;/coutn;for(int i=0; ivuwgx; 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();coutvv銀行賬戶打開成功！ n;void cunzhanghu()/void cunzhanghu()/將賬

23、戶信息存入if(!fout)if(!fout)coutvv”打開文件失敗vvendl;return;int i=0;pz= headz;while(pz!=NULL)計算鏈表中共有多少個節(jié)點i+;pz=pz-next;foutvvivvn;pz=headz;while(pz!=NULL) /計算文件中共有多少個數(shù)據(jù)foutvvpz-getleixing()vvt; foutvvpz-getzhanghao()vvt; foutvvpz-getid()vvt; foutvvpz-getmima()vvt; foutvvpz-getyue()vvendl;pz=pz-next;/coutvv文件存入成功!vvendl;fout.close();3 系統(tǒng)測試各功能運行時界面及說明。主菜單：注冊用戶，普通用戶登錄，管理員登錄和退出登錄。12 3 0入先戶戶錄先 進噸用用囚登噸 迎光冊通理岀先 歡鍥注蚯星目退先圖一：主窗口