二叉树的先序遍历、中序遍历、后序遍历的递归和非递归算法(共41页).doc

精选优质文档-倾情为你奉上 数据结构 课程设计报告题 目： 二叉树的先序遍历、中序遍历、后序遍历的递归 和 非 递 归 算 法。 学生姓名： * * * 学 号： * 专业班级： 计算机科学与技术专业 *班 同组姓名： * 指导教师： *老师 设计时间： 年下学期第 周 指导老师意见： 评定成绩： 签名： 日期：目 录二、系统项目设计. . . . . . . . . . . . . . .31.二叉树的建立42.先序遍历4 a.递归算法7 b.非递归算法73.中序遍历6 a.递归算法7 b.非递归算法74.后序遍历6 a.递归算法7 b.非递归算法75.主菜单程序45.子菜单程序41.二叉树的建立42.先序遍历4 a.递归算法7 b.非递归算法72.中序遍历6 a.递归算法7 b.非递归算法73.后序遍历6 a.递归算法7 b.非递归算法74.主菜单程序45.子菜单程序4六、参考文献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请输入用户名：");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 && 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<<" * 取 钱 2 *"<<endl;cout<<" * 转 帐 3 *"<<endl;cout<<" * 查 询 4 *"<<endl;cout<<" * 挂 失 5 *"<<endl;cout<<" * 修改密码 6 *"<<endl;cout<<" * 保存信息 7 *"<<endl;cout<<" * 返回上级 0 *"<<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<<"请输入帐号："<<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); /如果密码错误，在以前基础上加状态一并存盘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）密码正确：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"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<<endl<<endl<<endl;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<<"请输入您的选择:"<<endl;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;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; /身份证号码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->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; cout<<"请输入用户名："cin>>s;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)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");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>>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 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)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"void 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<<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)cout<<"银行账户文件打开失败！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!=NULL) /计算文件中共有多少个数据fout<<pz->getleixing()<<'t'fout<<pz->getzhanghao()<<'t'fout<<pz->getid()<<'t'fout<<pz->getmima()<<'t'fout<<pz->getyue()<<endl;pz=pz->next; /cout<<"文件存入成功!"<<endl;fout.close();3 系统测试各功能运行时界面及说明。1 主菜单：注册用户，普通用户登录，管理员登录和退出登录。 图一：主窗口2 普通用户：存钱，取钱，转账，查询，挂失，修改密码，保存信息，返回。 图二：普通用户登录窗口3 管理员：开户，销户，查看，修改密码、账户、状态，保存，返回。 图三：管理员登录窗口4 管理员的查看：查看某账户所以信息，按时间查看业务信息。 图四：管理员查看窗口 4 小 结通过为期两周的课程设计使我对银行管理系统和C+有了更深的认识和理解，也使我更加明白C+在程序设计中的重要性和地位。要想学好它要重在实践，要通过不断的上机操作才能更好的学习它，通过实践，我也发现我的好多不足之处，对各种控制结构及语句、数组的基本与高级应用、指针数组、字符数组、动态数组、函数的定义、调用方式；函数在编程中的具体应用；以及变量存储特征与标识符的作用域，通过实践，使我在这些方面有了认识和提高。课程设计它是一项任务，更是一种挑战和历练。在课程设计中，为了使用时方便，着重对不足方面的知识进行了分析与理解，在这一过程中对文件的操作有了很大的提高。通过实际的演练，可以增强对知识的理解和运用能力。我认为： 1 本系统没有做到精细的查询与模糊查询，查询时也可以设计按照月份查询等等。假如实现用户可以更好的了解自己账户的信息。2 本系统没有做到自动生成帐号，银行的帐号应该是系统自动生成。3 代码可以减少很多重复的。我的编程能力还很弱，以后要好好加油。 5 参考文献1. C+面向对象程序设计教程（第3版） 陈维兴 林小茶 编著 清华大学出版社2. C程序设计教程 谭浩强 著 清华大学出版社3. 例子代码专心-专注-专业