数据结构遍历二叉树课程设计报告

遍历二叉树目 录一、需求分析21.主功能模块22.创建树模块23.遍历树模块2二、概要设计31.功能设计3（1）创建二叉树3（2）先序递归遍历3（3）中序递归遍历3（4）后序递归遍历3（5）先序非递归遍历3（6）中序非递归遍历4（7）后序非递归遍历4（8）层序非递归遍历42.算法流程图4三、详细设计121.界面设计122.详细代码分析14（1）主模块14（2）创建树模块15（3）遍历树模块16（4）源程序清单163.调试分析35（1）调试结果35（2）算法分析36四、心得体会37五、参考文献38一、 需求分析在现实世界层次化的数据模型中，数据与数据之间的关系纷繁复杂。其中很多关系无法使用简单的线性结构表示清楚，比如祖先与后代的关系、整体与部分的关系等。于是人们借鉴自然界中树的形象创造了一种强大的非线性结构树。树形结构的具体形式有很多种，其中最常用的就是二叉树。而二叉树的多层次遍历遍历则是二叉树的重要内容。本程序用Microsoft Visual C+ 6.0编写，可以实现对二叉树的多种方式的创建、采用递归和非递归等两种方式先序、中序、后序进行遍历。1. 主功能模块通过合理的界面设计，根据提示信息，使用者可以方便快捷地运行本程序来完成创建、遍历二叉树等操作。界面美观，人性化，程序智能，安全性高。2. 创建树模块当进入程序运行界面后，根据提示输入需要建立的二叉树，共有三种方法来创建二叉树,即：1：广义表构造法、2：先序和中序构造法、3：中序和后序构造法。建立完二叉树后自动进入下一个功能模块。3. 遍历树模块 实现对该二叉树的先序递归遍历、先序非递归遍历、中序递归遍历、中序非递归遍历、后序递归遍历、后序非递归遍历、层序非递归遍历等方式的遍历操作，并输出各遍历序列。当对该二叉树进行层序非递归遍历时，直接输出该树的逻辑结构图，以便更直观地显示其层次关系。二、 概要设计1. 功能设计（1） 创建二叉树利用二叉树模板类，创建二叉树时产生类模板，调用类的构造函数来创建，修改二叉树的结构时，可以调用赋值语句直接把广义表转换成二叉树。相关类或函数如下：class BinaryTree;BinaryTree();BinaryTree& operator=(const string& str);（2） 先序递归遍历若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。相关函数如下：void PreOrderTraverse(const BinaryTreeNode* p) const;（3） 中序递归遍历若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序遍历右子树。相关函数如下：void InOrderTraverse(const BinaryTreeNode* p) const;（4） 后序递归遍历若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树；（3）访问根结点。相关函数如下：void PostOrderTraverse(const BinaryTreeNode* p) const;（5） 先序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如下：void PreOrderTraverse() const;（6） 中序非递归遍历若二叉树为空，则空操作；否则引入栈模拟递归工作栈，初始时栈为空。相关函数如下：void InOrderTraverse() const;（7） 后序非递归遍历若二叉树为空，则空操作；否则引入栈和标记模拟递归工作栈，初始时栈为空。相关函数如下：void PostOrderTraverse() const;（8） 层序非递归遍历按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。相关函数如下：void LevelOrderTraverse() const;2. 算法流程图开始结束先序和中序构造法广义表中序和后序构造法图2-1 创建二叉树开始判断结点是否空访问根结点结束按前根遍历方式遍历左子树按前根遍历方式遍历左子树YN图2-2 前序递归遍历 开始判断结点是否空按中根遍历方式遍历左子树结束访问根结点按中根遍历方式遍历右子树YN图2-3 中序递归遍历开始判断结点是否空按后根遍历方式遍历左子树结束按后根遍历方式遍历右子树访问根结点YN图2-4 后序递归遍历开始申请一个STL栈stack s判断结点是否空输出结点值p-datas.push(p)结点的值变为它的左孩子判断结点是否空p=s.pop()p=p-rchild结束判断栈或结点是否空NYNYN图2-5 先序非递归遍历开始申请一个STL栈stack s判断结点是否空s.push(p)结点的值变为它的左孩子判断结点是否空输出结点值p-datap=s.pop()p=p-rchild结束判断栈或结点是否空NYYNN图2-6 中序非递归遍历开始申请一个STL栈stack s;用一个bool变量flag标记是否访问flag=0 s.push(p)p=p-lchild top+判断标志flag是否为1输出结点的数据p-datap = s.pop()p= p-rchild结束NYYNNYYN判断结点是否空判断栈或结点是否空判断结点是否空图2-7 后序非递归遍历开始申请一个STL队列queue q结束N判断结点是否空Y判断左结点是否空q.push(p-rchild)q.push(p-lchild)判断右结点是否空q.push(root);判断队列是否为空p=q.front()；输出结点值p-data; q.pop()YYNNYN图2-8 层序非递归遍历三、 详细设计1. 界面设计图3-1 系统运行主界面图3-2 创建二叉树界面图3-3 某二叉树层序遍历界面2. 详细代码分析（1） 主模块本模块定义了系统运行主界面的相关内容和相关操作函数，源代码如下：int main()system(color A9); /设置屏幕背景和字体颜色coutendlendlendlendlendl;coutstring(35,*)遍历二叉树string(35,*)endl;coutstring(31, )1：创建二叉树endl;coutstring(31, )2：先序遍历(递归)endl;coutstring(31, )3：先序遍历(非递归)endl;coutstring(31, )4：中序遍历(递归)endl;coutstring(31, )5：中序遍历(非递归)endl;coutstring(31, )6：后序遍历(递归)endl;coutstring(31, )7：后序遍历(非递归)endl;coutstring(31, )8：层序遍历(非递归)endl;coutstring(31, )9：重新显示所有菜单endl;coutstring(31, )=0)cout(剩setw(2)second秒);coutendlendlstring(80,*);while(!isdigit(ch) /合法性判断center(您的输入有误，请重新输入：,0);ch=getch();coutchendl;BinaryTree t; /构造空二叉树while(1) /菜单操作无限循环bool mark=1; /设置重新显示所有菜单时的输出标记switch(ch).（2） 创建树模块本模块包括两个类二叉树结点类、二叉树类，源代码如下：class BinaryTreeNodeprivate:T data; /存储该结点的数据 BinaryTreeNode *parent; /存储该结点的父指针BinaryTreeNode *left; /存储该结点的左孩子指针BinaryTreeNode *right; /存储该结点的右孩子指针public:BinaryTreeNode();BinaryTreeNode(const T& t);T GetData() const;bool IsLeftChild() const;bool IsRightChild() const;BinaryTreeNode* GetParent() const;BinaryTreeNode* GetLeftChild() const;BinaryTreeNode* GetRightChild() const;BinaryTreeNode* GetLeftBrother() const; BinaryTreeNode* GetRightBrother() const;void Assign(const T& t);void SetParent(BinaryTreeNode* q);void SetLeftChild(BinaryTreeNode* q);void SetRightChild(BinaryTreeNode* q);BinaryTreeNode();class BinaryTreeprivate:BinaryTreeNode* root; /二叉树根节点public:BinaryTree(); /二叉树构造函数声明bool IsEmpty() const; /二叉树判空函数声明BinaryTreeNode* GetRoot() const; /取得根节点函数声明BinaryTree& operator=(const string& str); /二叉树赋值函数声明BinaryTree(); /二叉树析构函数声明private:void NodeCounter(const BinaryTreeNode* p,int& sum) const; /统计二叉树结点个数函数声明void Destroy(BinaryTreeNode* p); /二叉树级联释放结点内存函数声明int Depth(const BinaryTreeNode* p) const; /计算二叉树深度函数声明;（3） 遍历树模块本模块包括了各种遍历二叉树的函数，源代码如下：void LevelOrderTraverse() const; /二叉树的层序遍历(非递归)成员函数声明void PreOrderTraverse() const; /二叉树的先序遍历(非递归)成员函数声明void PreOrderTraverse(const BinaryTreeNode* p) const; /二叉树的先序遍历(递归)成员函数声明void InOrderTraverse() const; /二叉树的中序遍历(非递归)成员函数声明void InOrderTraverse(const BinaryTreeNode* p) const; /二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse() const; /二叉树的后序遍历(非递归)成员函数声明void PostOrderTraverse(const BinaryTreeNode* p) const; /二叉树的后序遍历(非递归)成员函数声明（4） 源程序清单l BinaryTreeNode.h#include#include#includetemplateclass BinaryTreeNodeprivate:T data; /存储该结点的数据BinaryTreeNode *parent; /存储该结点的父指针BinaryTreeNode *left; /存储该结点的左孩子指针BinaryTreeNode *right; /存储该结点的右孩子指针public:BinaryTreeNode();BinaryTreeNode(const T& t);T GetData() const;bool IsLeftChild() const;bool IsRightChild() const;BinaryTreeNode* GetParent() const;BinaryTreeNode* GetLeftChild() const;BinaryTreeNode* GetRightChild() const;BinaryTreeNode* GetLeftBrother() const;BinaryTreeNode* GetRightBrother() const;void Assign(const T& t);void SetParent(BinaryTreeNode* q);void SetLeftChild(BinaryTreeNode* q);void SetRightChild(BinaryTreeNode* q);BinaryTreeNode();templateBinaryTreeNode:BinaryTreeNode():data(0),parent(NULL),left(NULL),right(NULL)templateBinaryTreeNode:BinaryTreeNode(const T&t):data(t),parent(NULL),left(NULL),right(NULL)templatebool BinaryTreeNode:IsLeftChild() constreturn (this=this-parent-GetLeftChild();templatebool BinaryTreeNode:IsRightChild() constreturn (this=this-parent-GetRightChild();templateT BinaryTreeNode:GetData() constreturn data;templateBinaryTreeNode* BinaryTreeNode:GetParent() constreturn parent;templateBinaryTreeNode* BinaryTreeNode:GetLeftChild() constreturn left;templateBinaryTreeNode* BinaryTreeNode:GetRightChild() constreturn right;templateBinaryTreeNode* BinaryTreeNode:GetLeftBrother() constassert(IsRightChild();return this-parent-GetLeftChild();templateBinaryTreeNode* BinaryTreeNode:GetRightBrother() constassert(IsLeftChild();return this-parent-GetRightChild();templatevoid BinaryTreeNode:Assign(const T& t)data=t;templatevoid BinaryTreeNode:SetParent(BinaryTreeNode* q)parent=q;templatevoid BinaryTreeNode:SetLeftChild(BinaryTreeNode* q)left=q;templatevoid BinaryTreeNode:SetRightChild(BinaryTreeNode* q)right=q;templateBinaryTreeNode:BinaryTreeNode()l BinaryTree.h#include#include#include#include#include#includeBinaryTreeNode.h /二叉树结点模板类头文件using namespace std;const int MAX=1024;templateclass BinaryTreeprivate:BinaryTreeNode* root; /二叉树根节点public:BinaryTree(); /二叉树构造函数声明bool IsEmpty() const; /二叉树判空函数声明BinaryTreeNode* GetRoot() const; /取得根节点函数声明BinaryTree& operator=(const string& str); /二叉树赋值函数声明void LevelOrderTraverse() const; /二叉树的层序遍历(非递归)成员函数声明void PreOrderTraverse() const; /二叉树的先序遍历(非递归)成员函数声明void PreOrderTraverse(const BinaryTreeNode* p) const; /二叉树的先序遍历(递归)成员函数声明void InOrderTraverse() const; /二叉树的中序遍历(非递归)成员函数声明void InOrderTraverse(const BinaryTreeNode* p) const; /二叉树的中序遍历(递归)成员函数声明void PostOrderTraverse() const; /二叉树的后序遍历(非递归)成员函数声明void PostOrderTraverse(const BinaryTreeNode* p) const; /二叉树的后序遍历(非递归)成员函数声明BinaryTree(); /二叉树析构函数声明private:void NodeCounter(const BinaryTreeNode* p,int& sum) const; /统计二叉树结点个数函数声明void Destroy(BinaryTreeNode* p); /二叉树级联释放结点内存函数声明int Depth(const BinaryTreeNode* p) const; /计算二叉树深度函数声明;templateBinaryTree:BinaryTree():root(NULL) /二叉树构造函数定义templateBinaryTree& BinaryTree:operator=(const string& str) /二叉树赋值函数定义Destroy(root);root=NULL;BinaryTreeNode *indexMAX;BinaryTreeNode *p=NULL;int top=-1,sum=0,number=0;int mark=1;for(int i=0;istr.size();i+)char ch=stri;switch(ch)case (:index+top=p;mark=1;break;case ):mark=1;top-;break;case ,:mark+;break;default:p=new BinaryTreeNode(ch);sum+;if(root=NULL)root=p;elseif(mark=1)indextop-SetLeftChild(p);else if(mark=2)indextop-SetRightChild(p);NodeCounter(root,number);if(sumnumber)Destroy(root);root=NULL;return *this;templatebool BinaryTree:IsEmpty() const /二叉树判空函数定义return (root=NULL);templateBinaryTreeNode* BinaryTree:GetRoot() const /取得根节点函数定义return root;templatevoid BinaryTree:LevelOrderTraverse() const /二叉树的层序遍历(非递归)成员函数定义if(root=NULL)coutstring(15, )二叉树为空，请先创建二叉树！ endl;return;int sum=Depth(root);queueBinaryTreeNode * list;list.push(root);BinaryTreeNode *p=new BinaryTreeNode( );int number=1;while(number=pow(2,sum)-1)BinaryTreeNode* temp=list.front();list.pop();int i=floor(log10(number)/log10(2)+1;int j=number+1-pow(2,i-1);if(number=pow(2,i-1)coutstring(81-pow(2,sum)/2+pow(2,sum-i)-1, );elsecoutstring(pow(2,sum-i+1)-1, );coutGetData();if(floor(log10(number+1)/log10(2)=log10(number+1)/log10(2)coutGetLeftChild()!=NULL)list.push(temp-GetLeftChild();elselist.push(p);if(temp-GetRightChild()!=NULL)list.push(temp-GetRightChild();elselist.push(p);delete p;templatevoid BinaryTree:PreOrderTraverse(const BinaryTreeNode* p) const /二叉树的先序遍历(递归)成员函数定义if(root=NULL)cout二叉树为空，请先创建二叉树！;return;if(p=NULL)return;coutGetData();PreOrderTraverse(p-GetLeftChild();PreOrderTraverse(p-GetRightChild();templatevoid BinaryTree:PreOrderTraverse() const /二叉树的先序遍历(非递归)成员函数定义if(root=NULL)cout二叉树为空，请先创建二叉树！;return;stackBinaryTreeNode * list;BinaryTreeNode *p=root;while(!list.empty() | p!=NULL)while(p!=NULL)list.push(p);coutGetData();p=p-GetLeftChild();p=list.top();list.pop();p=p-GetRightChild();templatevoid BinaryTree:InOrderTraverse(const BinaryTreeNode* p) const /二叉树的中序遍历(递归)成员函数定义if(root=NULL)coutGetLeftChild();coutGetData();InOrderTraverse(p-GetRightChild();templatevoid BinaryTree:InOrderTraverse() const /二叉树的中序遍历(非递归)成员函数定义if(root=NULL)cout二叉树为空，请先创建二叉树！;return;stackBinaryTreeNode * list;BinaryTreeNode *p=root;while(!list.empty() | p!=NULL)while(p!=NULL)list.push(p);p=p-GetLeftChild();p=list.top();list.pop();coutGetData();p=p-GetRightChild();templatevoid BinaryTree:PostOrderTraverse(const BinaryTreeNode* p) const /二叉树的后序遍历(递归)成员函数定义if(root=NULL)coutGetLeftChild();PostOrderTraverse(p-GetRightChild();coutGetData();templatevoid BinaryTree:PostOrderTraverse() const /二叉树的后序遍历(非递归)成员函数定义if(root=NULL)cout二叉树为空，请先创建二叉树！;return;stackBinaryTreeNode * list;BinaryTreeNode *p=root;BinaryTreeNode *q;bool flag;while(!list.empty() | p!=NULL)while(p!=NULL)list.push(p);p=p-GetLeftChild();q=NULL;flag=1;while(flag & !list.empty()p=list.top();if(p-GetRightChild()=q)coutGetData();list.pop();q=p;if(list.empty()p=NULL;elsep=p-GetRightChild();flag=0;templateBinaryTree:BinaryTree() /二叉树析构函数定义Destroy(root);templatevoid BinaryTree:Destroy(BinaryTreeNode* p) /二叉树级联释放结点内存函数定义if(p!=NULL)Destroy(p-GetLeftChild();Destroy(p-GetRightChild();delete p;p=NULL;templatevoid BinaryTree:NodeCounter(const BinaryTreeNode* p,int& sum) const /统计二叉树结点个数函数定义if(p=NULL)return;sum+;NodeCounter(p-GetLeftChild(),sum);NodeCounter(p-GetRightChild(),sum);templateint BinaryTree:Depth(const BinaryTreeNode* p) const /计算二叉树深度函数声明if(p=NULL)return 0;int h1=Depth(p-GetLeftChild();int h2=Depth(p-GetRightChild();return h1h2 ? h1+1 : h2+1;l 遍历二叉树.cpp#include#include#include#include#include#includeBinaryTree.h /二叉树模板类头文件using namespace std;char limittime(int i); /限时输入函数声明void menu(int second=30); /菜单输出函数声明void center(string str,bool e=1); /居中输出函数声明bool Convert1(string s1,string s2,string& str); /先序和中序转换成广义表函数声明bool Convert2(string s1,string s2,string& str); /中序和后序转换成广义表函数声明int main()system(color A9); /设置屏幕背景和字体颜色char ch=limittime(15); /调用限时函数while(!isdigit(ch) /合法性判断center(您的输入有误，请重新输入：,0);ch=getch();coutchendl;BinaryTree t; /构造空二叉树while(1) /菜单操作无限循环bool mark=1; /设置重新显示所有菜单时的输出标记switch(ch)case 1:if(t.GetRoot()!=NULL) /进行是否要覆盖原二叉树判断center(您要重新创建二叉树吗？);center(请按回车键继续创建，其他键返回上一级。);center(请选择(回车键/其它键)：,0);char ch=getch();coutendl;if(ch!=r)center(返回上一级成功！); /调用居中输出函数break;coutendl;coutstring(15, )string(20,*)创建二叉树string(20,*)endlendl;coutstring(31, )1：广义表构造法endl;coutstring(31, )2：先序和中序构造法endl;coutstring(31, )3：中序和后序构造法endl;coutstring(31, )0：返回上一级endlendl;coutstring(15, )string(50,*)endl;center(请选择(0-3)：,0);char ch=getch();coutch=0 & ch=3) /合法性判断center(您的输入有误，请重新输入：,0);ch=getch();coutchendl;switch(ch)case 1:coutstring(15, )str;)t=str; /采用赋值法修改二叉树if(t.GetRoot()=NULL) /判断二叉树是否创建成功coutstring(15, )您的输入有误，请重新输入：;elsebreak;center(广义表构造法创建二叉树成功！);break;case 2:string str;string s1,s2;coutstring(15, )s1;coutstring(15, )s2;while(1)if(Convert1(s1,s2,str) /调用先序和中序转换成广义表函数，并返回是否创建成功break;elsecoutstring(15, )s1;coutstring(15, )s2;t=str; /采用赋值法修改二叉树center(先序和中序构造法创建二叉树成功！);break;case 3:string str;string s1,s2;coutstring(15, )s2;coutstring(15, )s1;while(1)if(Convert2(s1,s2,str) /调用中序和后序转换成广义表函数，并返回是否创建成功break;elsecoutstring(15, )s2;coutstring(15, )s1;t=str; /采用赋值法修改二叉树center(中序和后序构造法创建二叉树成功！);break;default:center(返回上一级成功！);break;case 2:coutstring(15, )string(18,*)先序遍历(递归)string(18,*)endl;coutstring(15, );t.PreOrderTraverse(t.GetRoot(); /调用二叉树的先序遍历(递归)成员函数coutendl;coutstring(15, )string(50,*)endl;break;case 3:coutstring(15, )string(17,*)先序遍历(非递归)string(17,*)endl;coutstring(15, );t.PreOrderTraverse(); /调用二叉树的先序遍历(非递归)成员函数coutendl;coutstring(15, )string(50,*)endl;break;case 4:coutstring(15, )string(18,*)中序遍历(递归)string(18,*)endl;coutstring(15, );t.InOrderTraverse(t.GetRoot(); /调用二叉树的中序遍历(递归)成员函数coutendl;coutstring(15, )string(50,*)endl;break;case 5:coutstring(15, )string(17,*)中序遍历(非递归)string(17,*)endl;coutstring(15, );t.InOrderTraverse(); /调用二叉树的中序遍历(非递归)成员函数coutendl;coutstring(15, )string(50,*)endl;break;case 6:coutstring(15, )string(18,*)后序遍历(递归)string(18,*)endl;coutstring(15, );t.PostOrderTraverse(t.GetRoot(); /调用二叉树的后序遍历(递归