二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法

1、精选优质文档-倾情为你奉上 数据结构 课程设计报告题 目： 二叉树的先序遍历、中序遍历、后序遍历的递归 和 非 递 归 算 法。 学生姓名： * * * 学 号： * 专业班级： 计算机科学与技术专业 *班 同组姓名： * 指导教师： *老师 设计时间： 年下学期第 周 指导老师意见： 评定成绩： 签名： 日期：目 录二、系统项目设计. . . . . . . . . . . . . . .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一 课题简介：通过这个课题设计主要掌握三种遍历方法，包括前序遍历，中序遍历和后序遍历，以及后续遍历的非递归算法。二 项目设计： 非 递 归 算 法先序遍历中序遍历后序遍历退出程序退出程序后序遍历中序遍历先序遍历递 归 算 法系 统 主 界 面 图1： 系统功能模块图准 备系 统 登 录选择 遍历中 序 遍 历 后 序 遍 历 先 序 遍 历退 出 输出遍历结果 图2：系统存盘功能流程图 三 系统实

3、现系统核心代码：1.二叉树的建立：二叉树的遍历算法需要先建立二叉树，二叉树的建立需要建立栈和数组栈和数组的建立：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.中序遍历：检查该用户是否可以使用该系统，如果没有该用户则重新输入输入，若用户密码输入错误，三次错误时，退出登录系统，并且该用户被冻结。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、，在以前基础上加状态一并存盘cunyonghu();i+;goto Lab;void display() /打印函数p= head;while(p!= NULL)cout<<"用户名："<<p->getmingzi()<<endl<<"普通密码："<<p->getmima1()<<endl<<"状态："<<p->getstate()<<endl;p=p->next;1) 没有此用户：2）用户密码错误：3）

13、密码正确：3.后序遍历：检查该用户是否可以使用本系统，三次密码错误则退出登录系统。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<<" * 修改账户状态 6 *"<<endl;cout<<" * 修改用户状态 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(); /修改状态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）密码正确：开户功能：使用该功能可以拥有自己的账户，使用银行系统void kaihu()char zhanghao20; /用户帐号char id20; /

19、身份证号码char mima20; /普通用户密码 int s= 0; /状态初始化为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;/ 释放节点空间if(!pz)cout<<"没有找到该账户！n"挂失功能：void duzhanghu() int v; /状态char u20;/ 帐号char w20; /身份证号码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; /帐号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; /账户状态 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; /状态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)/计算链表中共有多少个节点i+;p=p->next;fout<<i<<'n'p=head;while(p!=NULL) /计算文件中共有多少个数据fout<<p->getstate()<<'t'fout<

29、<p->getmingzi()<<'t'fout<<p->getmima1()<<'n'p=p->next;/cout<<"文件存入成功!"<<endl;fout.close();void duzhanghu() /将账户信息读出 int v; /状态char u20;/ 帐号char w20; /身份证号码char g20;/ 普通用户密码int n; double x;ifstream fin("银行账户.txt");if(!fin)c

30、out<<"银行账户文件打开失败！n"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)/计算链表中共有多少个节点i+;pz=pz->next;fout<<i<<'n'pz=headz;while(pz!=N