二叉树的遍历课程设计(C++)含源代码

数据结构课程数据结构课程设计《数据结构》课程设计设计题目：二叉树的遍历姓名：陈雷学号：211001047专业：计算机科学与技术院系：计算机科学与技术班级：1002指导教师：吴克力2012年3月1日摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC++，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键字：二叉树遍历非递归C++LCAAbstract:Thispapermainlydescribeshowtoimplementbinarytreetraversal.Thebinarytreetraversalisbasedonbinarytreebinarystoragestructure.Traversalmethodincludes:preordertraversal,inordertraversal,postordertraversal,levelordertraversal.Theformerpreordertraversalandpostorderuseofnon-recursivealgorithm.ProgrammingenvironmentisVC++,inadditiontotraversaloperation,alsoincreasedforsolvingthebinarytreedepth、summarypointsandeachlayerofnodes,aswellasthemostrecentcommonancestor(LCA)algorithm.Keywords:binarytreetraversalnon-recursiveC++LCA目录4一、问题描述4问题描述：创建二叉树并遍历4基本要求：4二、需求4三、概要设计41．创建二叉树42．二叉树的非递归前序遍历示意图53．二叉树的后序非递归遍历示意图5四、数据结构设计51．二叉树结点数据类型定义为：52．二叉树数据类型定义为：6五、算法设计61、创建二叉树72、非递归前序遍历73、非递归后序遍历84、求二叉树的高度95、求二叉树每一层的结点数96、求两节点最近共同祖先106、算法图11六、程序测试与实现111、函数之间的调用关系112、主程序133、测试数据134、测试结果14七、调试分析15八、遇到的问题及解决办法15九、心得体会15十、参考文献一、问题描述问题描述：创建二叉树并遍历基本要求：1、分别运用非递归的方式完成对二叉树的先序和后序遍历2、输出二叉树的高度3、输出每一层的结点数4、查找结点P和结点Q的最近共同祖先二、需求分析1．本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2．程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。3．用户输入数据完毕，程序将输出运行结果。4．测试数据应为字符型数据。三、概要设计1．创建二叉树输入数据不低于15个，用递归方法建立二叉树。2．二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3．二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图四、数据结构设计1．二叉树结点数据类型定义为：template<typenameT>structBiNode{BiNode<T>*rchild,*lchild;//指向左右孩子的指针Tdata;//结点数据信息};2．二叉树数据类型定义为：template<typenameT>classBiTree{template<typenameT>friendostream&operator<<(ostream&os,BiTree<T>&bt);public:BiTree();//无参构造函数BiTree(intm){};//有参空构造函数BiTree(Tary[],intnum,Tnone);//有参构造函数~BiTree();//析构函数voidpreorder();//递归前序遍历voidinorder();//递归中序遍历voidpostorder();//递归后续遍历voidlevelorder();//层序遍历intcount();//计算二叉树的结点数intdepth();//计算二叉树的深度voiddisplay(ostream&os);//打印二叉树，有层次voidLevelNum();//计算每一层结点数voidPreOrder();//非递归前序遍历voidPostOrder();//非递归后序遍历voidcreat();//创建二叉树TleastCommanAncestor(Tva,Tvb);//求树中任意两结点最近共同祖先protected://以下函数供上面函数调用//对应相同功能voidcreat(BiNode<T>*&root);//创建voidrelease(BiNode<T>*&root);//删除BiNode<T>*Build(Tary[],intnum,Tnone,intidx);//用数组创建二叉树voidPreOrder(BiNode<T>*root);//前序遍历voidPostOrder(BiNode<T>*root);//后续遍历voidLevelNum(BiNode<T>*root);//层序遍历voidpreorder(BiNode<T>*root);//递归前序遍历voidinorder(BiNode<T>*root);//递归中序遍历voidpostorder(BiNode<T>*root);//递归后续遍历voidlevelorder(BiNode<T>*root);//层序遍历intcount(BiNode<T>*root);//计算结点数intdepth(BiNode<T>*root);//计算深度voiddisplay(ostream&os,BiNode<T>*root,intdep);//打印staticboolleastCommanAncestor(BiNode<T>*root,Tva,Tvb,BiNode<T>*&result,BiNode<T>*parrent);//求最近共同祖先private:BiNode<T>*rootptr;};五、算法设计1、创建二叉树//实现外部递归调用voidBiTree<T>::creat(){creat(rootptr);}//类体内递归创建二叉树template<typenameT>voidBiTree<T>::creat(BiNode<T>*&root){Titem;cin>>item;if(item=='#')root=NULL;else{root=newBiNode<T>;root->data=item;creat(root->lchild);creat(root->rchild);}}2、非递归前序遍历template<typenameT>voidBiTree<T>::PreOrder(){PreOrder(rootptr);}template<typenameT>voidBiTree<T>::PreOrder(BiNode<T>*root){stack<BiNode<T>*>s;while(root!=NULL||!s.empty()){while(root){cout<<root->data;s.push(root);root=root->lchild;}if(!s.empty()){root=s.top();s.pop();root=root->rchild;}}}3、非递归后序遍历template<typenameT>voidBiTree<T>::PostOrder(){PostOrder(rootptr);}template<typenameT>voidBiTree<T>::PostOrder(BiNode<T>*root){stack<BiNode<T>*>s;//定义栈，节点类型为TreeNodeBiNode<T>*p=root;BiNode<T>*pre=NULL;//pre表示最近一次访问的结点while(p||!s.empty()){//沿着左孩子方向走到最左下。while(p){s.push(p);p=p->lchild;}//getthetopelementofthestackp=s.top();//如果p没有右孩子或者其右孩子刚刚被访问过if(p->rchild==NULL||p->rchild==pre){//visitthiselementandthenpopitcout<<p->data;s.pop();pre=p;p=NULL;}else{p=p->rchild;}}//endofwhile(p||st.size()!=0)}4、求二叉树的高度template<typenameT>intBiTree<T>::depth(){returndepth(rootptr);}template<typenameT>intBiTree<T>::depth(BiNode<T>*root){intrdep,ldep;if(root==NULL)return0;else{ldep=depth(root->lchild);rdep=depth(root->rchild);return(rdep>ldep?rdep:ldep)+1;}}5、求二叉树每一层的结点数template<typenameT>voidBiTree<T>::LevelNum(){LevelNum(rootptr);}template<typenameT>voidBiTree<T>::LevelNum(BiNode<T>*root){queue<BiNode<T>*>q;intfront,rear,first,last,level;front=rear=first=0;last=level=1;if(root){q.push(root);rear++;while(front<rear){root=q.front();q.pop();front++;if(root->lchild){q.push(root->lchild);rear++;}if(root->rchild){q.push(root->rchild);rear++;}if(front==last){cout<<"第"<<level<<"层有"<<last-first<<"个结点"<<endl;level++;last=rear;first=front;}}}}6、求两节点最近共同祖先template<typenameT>TBiTree<T>::leastCommanAncestor(Tn1,Tn2){returnleastCommanAncestor(rootptr,n1,n2);}template<typenameT>TBiTree<T>::leastCommanAncestor(BiNode<T>*root,Tn1,Tn2){if(root==NULL||root->data==n1||root->data==n2)return-1;if((root->rchild!=NULL)&&(root->rchild->data==n1||root->rchild->data==n2))returnroot->data;if((root->lchild!=NULL)&&(root->lchild->data==n1||root->lchild->data==n2))returnroot->data;if(root->data>n1&&root->data<n2)returnroot->data;if(root->data>n1&&root->data>n2)returnleastCommanAncestor(root->lchild,n1,n2);if(root->data<n1&&root->data<n2)returnleastCommanAncestor(root->rchild,n1,n2);}6、算法流程图六、程序测试与实现1、函数之间的调用关系2、主程序voidmain(){BiTree<char>Tree(1);while(1){cout<<"\t\t欢迎使用本系统！！"<<endl;cout<<"\t\t########################################"<<endl;cout<<"\t\t##"<<endl;cout<<"\t\t#1--创建一颗二叉树并显示#"<<endl;cout<<"\t\t#2--遍历二叉树#"<<endl;cout<<"\t\t#3--查询二叉树的深度和结点数#"<<endl;cout<<"\t\t#4--查询每层结点数#"<<endl;cout<<"\t\t#5--查找两节点P和Q的最近共同祖先#"<<endl;cout<<"\t\t#6--退出#"<<endl;cout<<"\t\t##"<<endl;cout<<"\t\t########################################"<<endl;cout<<"请输入你的选择：";intx;cin>>x;switch(x){case1:{cout<<"请输入二叉树的前序遍历："<<endl;cout<<"（以#作为分支结尾，例如：AB##C##）"<<endl;Tree.creat();cout<<Tree;cout<<endl;}break;case2:{cout<<endl;cout<<"前序遍历为：";Tree.PreOrder();cout<<endl;cout<<"中序遍历为：";Tree.inorder();cout<<endl;cout<<"后序遍历为：";Tree.PostOrder();cout<<endl;cout<<"层序遍历为：";Tree.levelorder();cout<<endl;cout<<endl;}break;case3:{cout<<"树的深度为："<<Tree.depth()<<endl;cout<<"树的结点数："<<Tree.count()<<endl;cout<<endl;}break;case4:{Tree.LevelNum();}break;case5:{charch1,ch2;cout<<"请输入P数据信息：";cin>>ch1;cout<<"请输入Q数据信息：";cin>>ch2;cout<<ch1<<"和"<<ch2<<"的最近共同祖先是"<<Tree.leastCommanAncestor(ch1,ch2)<<endl;}break;case6:return;break;default:cout<<"请输入正确的选择！！！"<<endl;break;}}}3、测试数据AB#CD###E#FGH##K###4、测试结果七、调试分析创建二叉树：依次输入二叉树前序遍历序列，构建相应的二叉树。二叉树遍历：递归算法、非递归算法测试，调用相应函数进行测试，结果正确。求二叉树深度和结点数：创建一个二叉树，调用相关函数，测试结果正确。计算每层结点数：调用levelNum()函数，测试结果正确。求最近共同祖先：调用LCA()函数，测试结果正确。八、遇到的问题及解决办法调试时遇到诸多问题，其中最主要的问题是死循环问题，在非递归遍历时，容易进入死循环，经过查找资料、分步调试最终找到循环结束条件，顺利解决各个难题。九、心得体会通过本次课程设计，我发现，有关一个课题的所有知识不仅仅是在课本上，多查阅一些资料能够更好的完成课题，这就需要一种能力，即自学能力。本次课程设计还让我认识到自己的缺点。本次选的课题是二叉树的遍历，因为本学期所学的就是二叉树等数据结构，所以认为比较适合。刚开始认为会很简单，但到后来就出现一些难以解决的问题，就像老师请教，并查阅相关资料。经过慢慢的调试，最终测试成功。这次课程设计让我所学到的数据结构知识发挥的淋漓尽致，而且还拓展了我的知识面，使我更加熟练的掌握各种方法。总之，这次课程设计增强了我的自学能力，拓展了我的知识面，让我对数据结构更加了解。十、参考文献《C++程序设计》（第二版）吴乃陵况迎辉《数据结构C++版》王红梅main()创建遍历求节点数深度每层结点数求LCAPostorder()Inorder()Creat()Preorder()Depth()Count()Levelnum()LCA()程序初始化用户交互用户输入选择创建二叉树遍历二叉树求深度求每层结点数求共同祖先处理并输出结果结束PAGE5