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

1、精選優(yōu)質文檔-傾情為你奉上 數(shù)據(jù)結構 課程設計報告題 目： 二叉樹的先序遍歷、中序遍歷、后序遍歷的遞歸 和 非 遞 歸 算 法。 學生姓名： * * * 學 號： * 專業(yè)班級： 計算機科學與技術專業(yè) *班 同組姓名： * 指導教師： *老師 設計時間： 年下學期第 周 指導老師意見： 評定成績： 簽名： 日期：目 錄二、系統(tǒng)項目設計. . . . . . . . . . . . . . .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六、參考文獻23一 課題簡介：通過這個課題設計主要掌握三種遍歷方法，包括前序遍歷，中序遍歷和后序遍歷，以及后續(xù)遍歷的非遞歸算法。二 項目設計： 非 遞 歸 算 法先序遍歷中序遍歷后序遍歷退出程序退出程序后序遍歷中序遍歷先序遍歷遞 歸 算 法系 統(tǒng) 主 界 面 圖1： 系統(tǒng)功能模塊圖準 備系 統(tǒng) 登 錄選擇 遍歷中 序 遍 歷 后 序 遍 歷 先 序 遍 歷退 出 輸出遍歷結果 圖2：系統(tǒng)存盤功能流程圖 三 系統(tǒng)實

3、現(xiàn)系統(tǒng)核心代碼：1.二叉樹的建立：二叉樹的遍歷算法需要先建立二叉樹，二叉樹的建立需要建立棧和數(shù)組棧和數(shù)組的建立：typedef struct node /*結點定義*/ 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)，如果沒有該用戶則重新輸入輸入，若用戶密碼輸入錯誤，三次錯誤時，退出登錄系統(tǒng)，并且該用戶被凍結。void common_user()/ 普通用戶登錄char ch;char pass20;char uname20;int i=0;Lab:if(i=3) exit(1);puts("n請輸入用戶名：");

7、cin>>uname;for(user *p= head; p!= NULL;p= p->next)if(!strcmp(uname,p->getmingzi()if(p->getstate() >=3) cout<<"該賬戶已經被凍結！n"i+; goto Lab;else break;if(!p)cout<<"該用戶不存在，請重新輸入！n"i+;goto Lab;int x = 0;cout<<"請輸入密碼：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<<" * 轉 帳 3 *"<<endl;cout<<" * 查 詢 4 *"<<endl;cout<<" * 掛 失 5 *"<<endl;cout<<" * 修改密碼 6 *"<<endl;cout<<" * 保存信息 7 *"<<endl;cout<<" * 返回上級 0 *"

10、;<<endl;cout<<" *"<<endl;cout<<"請輸入您的選擇:"<<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、;請輸入帳號："<<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<<"密碼錯誤！n"p->setstate(p->getstate()+1); /如果密碼錯誤

12、，在以前基礎上加狀態(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）用戶密碼錯誤：3）

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

14、ot;i+; goto Lab;else 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("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<<" * 返回上級 0 *"<<endl;cout<<" *"<<endl;cout<<"請輸入您的選擇:"<<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密碼錯誤！n"i+;goto Lab;1) 密碼錯誤：2）密碼正確：開戶功能：使用該功能可以擁有自己的賬戶，使用銀行系統(tǒng)void kaihu()char zhanghao20; /用戶帳號char id20; /

19、身份證號碼char mima20; /普通用戶密碼 int s= 0; /狀態(tài)初始化為0，等于3時賬戶凍結cout<<"tt增加用戶操作中n"cout<<"請輸入用戶的帳號：n"cin>>zhanghao;cout<<"請輸入用戶的身份證號碼：n"cin>>id;cout<<"請輸入普通用戶的密碼：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<<"注冊完成！n"system("pause");銷戶功能：取消沒有用了的賬戶。void xiaohu () /注銷一個帳戶char ch;char s20;int n=0; cout<<"請輸入用戶名："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<<"該用戶已經找到，請確認刪除(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é)點空間if(!pz)cout<<"沒有找到該賬戶！n"掛失功能：void duzhanghu() int v; /狀態(tài)char u20;/ 帳號char w20; /身份證號碼char g20;/ 普通用戶密碼int n; double x;ifstream fin("銀行賬戶.txt");if(!fin)cout<<"銀行賬戶文件打開失?。"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; /帳號char id20; /身份證號碼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)/計算鏈表中共有多少個節(jié)點i+;p=p->next;fout<<i<<'n'p=head;while(p!=NULL) /計算文件中共有多少個數(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;/ 帳號char w20; /身份證號碼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)/計算鏈表中共有多少個節(jié)點i+;pz=pz->next;fout<<i<<'n'pz=headz;while(pz!=N