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

数据结构 课程设计报告题 目： 二叉树的先序遍历、中序遍历、后序遍历的递归 和 非 递 归 算 法。 学生姓名： * * * 学 号： * 专业班级： 计算机科学与技术专业 *班 同组姓名： * 指导教师： *老师 设计时间： 年下学期第 周 指导老师意见： 评定成绩： 签名： 日期：目 录一、课题简介3二、系统项目设计. . . . . . . . . . . . . . .3三、系统实现31.二叉树的建立42.先序遍历4 a.递归算法7 b.非递归算法73.中序遍历6 a.递归算法7 b.非递归算法74.后序遍历6 a.递归算法7 b.非递归算法75.主菜单程序45.子菜单程序4四、系统测试181.二叉树的建立42.先序遍历4 a.递归算法7 b.非递归算法72.中序遍历6 a.递归算法7 b.非递归算法73.后序遍历6 a.递归算法7 b.非递归算法74.主菜单程序45.子菜单程序4五、小结22六、参考文献23一 课题简介：通过这个课题设计主要掌握三种遍历方法，包括前序遍历，中序遍历和后序遍历，以及后续遍历的非递归算法。二 项目设计： 非 递 归 算 法先序遍历中序遍历后序遍历退出程序退出程序后序遍历中序遍历先序遍历递 归 算 法系 统 主 界 面 图1： 系统功能模块图准 备系 统 登 录选择 遍历中 序 遍 历 后 序 遍 历 先 序 遍 历退 出 输出遍历结果 图2：系统存盘功能流程图 三 系统实现系统核心代码：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(%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 ) 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-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请输入用户名：);cinuname;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;coutgetmima1(), pass)while(1)system(cls);int a;coutendlendlendl;cout =欢迎使用本银行=endl;cout * 存 钱 1 *endl;cout * 取 钱 2 *endl;cout * 转 帐 3 *endl;cout * 查 询 4 *endl;cout * 挂 失 5 *endl;cout * 修改密码 6 *endl;cout * 保存信息 7 *endl;cout * 返回上级 0 *endl;cout *endl;cout请输入您的选择: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请输入帐号：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 coutsetstate(p-getstate()+1); /如果密码错误，在以前基础上加状态一并存盘cunyonghu();i+;goto Lab;void display() /打印函数p= head;while(p!= NULL)cout用户名：getmingzi()endl普通密码：getmima1()endl状态：getstate()next;1) 没有此用户：2）用户密码错误：3）密码正确：3.后序遍历：检查该用户是否可以使用本系统，三次密码错误则退出登录系统。void manage() / 管理员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() 0 ) cout该账户已经被冻结！n;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;coutendlendlendl;cout =欢迎使用本银行=endl;cout * 开 户 1 *endl;cout * 销 户 2 *endl;cout * 查 看 3 *endl;cout * 修改密码 4 *endl;cout * 删除账户 5 *endl;cout * 修改账户状态 6 *endl;cout * 修改用户状态 7 *endl;cout * 保存用户信息 8 *endl;cout * 返回上级 0 *endl;cout *endl;cout请输入您的选择: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;case 6: xiugai1();system(cls); break;case 7: xiugaiyh();system(cls); break;case 8:cunyonghu();cunzhanghu();cunguanli();exit(1);case 0:return;else coutn密码错误！n;i+;goto Lab;1) 密码错误：2）密码正确：开户功能：使用该功能可以拥有自己的账户，使用银行系统void kaihu()char zhanghao20; /用户帐号char id20; /身份证号码char mima20; /普通用户密码 int s= 0; /状态初始化为0，等于3时账户冻结couttt增加用户操作中n;coutzhanghao;coutid;coutmima;oz= new zhanghu;oz-setzhanghao(zhanghao);oz-setid(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; couts;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)coutch;if(ch=y| ch=Y)if(n=1) headz= headz-next;else pz-next= pz-next-next;coutnext;/ 释放节点空间if(!pz)cout没有找到该账户！n;挂失功能：void duzhanghu() int v; /状态char u20;/ 帐号char w20; /身份证号码char g20;/ 普通用户密码int n; double x;ifstream fin(银行账户.txt);if(!fin)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();cout银行账户打开成功！n;类的定义class zhanghu /账户类private:char zhanghao20; /帐号char id20; /身份证号码char mima20; /普通用户密码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;void 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()return 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;/ 用户名char g20;/ 普通用户密码int n;ifstream fin(银行用户.txt);if(!fin)coutn;for(int i=0; ivug;o= new user;o-setstate(v);o-setmingzi(u);o-setmima1(g);o-next= head;head= o;cout银行用户打开成功！n;void cunyonghu() /将用户信息存入ofstream fout(银行用户.txt);if(!fout)cout打开文件失败next;foutin;p=head;while(p!=NULL) /计算文件中共有多少个数据foutgetstate()t;foutgetmingzi()t;foutgetmima1()next;/cout文件存入成功!endl;fout.close();void duzhanghu() /将账户信息读出 int v; /状态char u20;/ 帐号char w20; /身份证号码char g20;/ 普通用户密码int n; double x;ifstream fin(银行账户.txt);if(!fin)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();cout银行账户打开成功！n;void cunzhanghu() /将账户信息存入ofstream fout(银行账户.txt);if(!fout)cout打开文件失败next;foutin;pz=headz;while(pz!=NULL) /计算文件中共有多少个数据foutgetleixing()t;foutgetzhanghao()t;foutgetid()t;foutgetmima()t;foutgetyue()next; /cout