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

-.z.南京理工大学课程设计报告作者:相蒙蒙学号：1教学点:市职业大学专业:机电一体化题目:二叉树的遍历指导者：尚鲜莲评阅者：2014年4月-.z.**理工大学课程设计报告评语综合成绩：指导者评语：指导者(签字)：年月日-.z.课程设计报告摘要摘要：本文主要说明如何实现二叉树的遍历。此次二叉树的遍历基于二叉树的二叉链表存储结构。遍历方式包括：前序遍历，中序遍历，后续遍历，层序遍历。其中前序遍历和后续遍历采用非递归算法实现。编程环境为VC++，除了遍历操作外，还增加了求二叉树的深度，总结点数，每层结点数，以及最近共同祖先（LCA）问题的算法。关键词：二叉树遍历二叉树遍历目录1问题描述 51.1问题描述：创建二叉树并遍历 52、需求分析 53、概要设计 53.1．创建二叉树 53.2二叉树的非递归前序遍历示意图 53.3二叉树的后序非递归遍历示意图 64、数据结构设计 64.1二叉树结点数据类型定义 64.2二叉树数据类型定义 75、算法设计 85.1创建二叉树 85.2非递归前序遍历 85.3非递归后序遍历 95.4求二叉树的高度 105.5求二叉树每一层的结点数 105.6求两节点最近共同祖先 115.7算法流程图 126、程序测试与调试126.1函数之间的调用关系 126.2主程序 136.3测试数据 146.4测试结果 147、调试分析 178、遇到的问题及解决办法 179、心得体会 1710、参考文献 181、问题描述1.1问题描述：创建二叉树并遍历基本要求：分别运用非递归的方式完成对二叉树的先序和后序遍历输出二叉树的高度输出每一层的结点数查找结点P和结点Q的最近共同祖先需求分析1、本程序的功能包括二叉树的建立，二叉树的递归遍历，二叉树的非递归遍历，查询二叉树的深度，查询每层的结点数，查找两个结点的最近共同祖先，二叉树的打印。2、程序运行后显现提示信息，等候用户输入0—6以进入相应的操作功能。3、用户输入数据完毕，程序将输出运行结果。4、测试数据应为字符型数据。概要设计3．1创建二叉树输入数据不低于15个，用递归方法建立二叉树。3.2二叉树的非递归前序遍历示意图图3.2二叉树前序遍历示意图3.3二叉树的后序非递归遍历示意图图3.4二叉树后序遍历示意图4、数据结构设计4.1二叉树结点数据类型定义为：template<typenameT>struct BiNode{ BiNode<T>*rchild,*lchild;//指向左右孩子的指针 Tdata;//结点数据信息};4.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();//创建二叉树 TleastmanAncestor(Tva,Tvb);//求树中任意两结点最近共同祖先protected://以下函数供上面函数调用//对应相同功能voidcreat(BiNode<T>*&root);//创建voidrelease(BiNode<T>*&root);//删除 BiNode<T>*Build(Tary[],intnum,Tnone,intid*);//用数组创建二叉树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);//打印staticboolleastmanAncestor(BiNode<T>*root,Tva,Tvb,BiNode<T>*&result,BiNode<T>*parrent);//求最近共同祖先private: BiNode<T>*rootptr;};5、算法设计5.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); }}5.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; } }}5.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)}5.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.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; } } }}5.6求两节点最近共同祖先template<typenameT>TBiTree<T>::leastmanAncestor(Tn1,Tn2){returnleastmanAncestor(rootptr,n1,n2);}template<typenameT>TBiTree<T>::leastmanAncestor(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)returnleastmanAncestor(root->lchild,n1,n2);if(root->data<n1&&root->data<n2)returnleastmanAncestor(root->rchild,n1,n2);}5.7算法流程图程序初始化程序初始化用户交互用户交互用户输入选择用户输入选择求共同祖先求每层结点数求深度遍历二叉树创建二叉树求共同祖先求每层结点数求深度遍历二叉树创建二叉树结束处理并输出结果结束处理并输出结果6、程序测试与实现6.1函数之间的调用关系main()main()每层结点数求LCA求节点数深度遍历创建每层结点数求LCA求节点数深度遍历创建LCA()Levelnum()CLCA()Levelnum()Creat()Count()Depth()Inorder()PInorder()Postorder()Preorder()6.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<<"请输入你的选择：";int*; cin>>*;switch(*){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.leastm