树与二叉树的转换及二叉树的遍历 设计报告

信息与电气工程学院软件算法综合设计说明书（20/20学年第学期）题目树与二叉树的转换及二叉树的遍历专业班级_计算机科学与技术09级1班姓名学号指导教师设计周数1周设计成绩2011年07月日树的应用课程设计题目实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。要求：遍历的内容应是千姿百态的。课程设计目的及基本要求《数据结构》课程设计是计算机科学与技术专业集中实践性环节之一，是学习完《数据结构》课程后进行的一次全面的综合练习。其目的就是要达到理论与实际应用相结合，使学生能够根据数据对象的特性，学会数据组织的方法，能把现实世界中的实际问题在计算机内部表示出来，并培养良好的程序设计技能。课程设计教材及主要参考资料：严慰敏编《数据结构习题集》清华大学出版社胡学军编《数据结构》高等教育出版社教学参考书严慰敏编《数据结构习题集》清华大学出版社胡学军编《数据结构》高等教育出版社目录一、设计目的二、问题描述三、需求分析四、概要设计五、详细设计六、调试分析七、用户使用说明八、测试结果九、总结及分析《数据结构》课程设计----树与二叉树的转换及二叉树的遍历设计目的通过课程设计，巩固所学的理论知识，培养综合运用所学知识解决实际问题的能力。根据实际问题的具体情况，结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相映的存储结构，并能设计出解决问题的有效算法。问题描述要求：实现树与二叉树的转换的实现。以及树的前序、后序的递归、非递归算法，层次序的非递归算法的实现，应包含建树的实现。需求分析本程序的功能是对任意二叉树进行递归前序遍历和后序遍历，用栈实现非递归的前序、和后序遍历，还有对树的层序遍历以及树与二叉树的转换。本程序要求用户以字符输入，若要实现终端结点，最后以回车键建入数据。本程序的结果将依次打印出递归前序遍历和后序遍历，用栈实现非递归的前序和中序遍历和后序遍历，和线索化层序遍历，输入树及树传换成二叉树。概要设计二叉树创建用链表实现创建一个树结点的结构体，从键盘输入数据，存入数组。把下标为2*i+1的值存入左孩子，为2*i+2的存入右孩子。BiNodecreat()，BiNodestree_creat(char*a,intk)。

图1、二叉树的创建树与二叉树的转换算法转换时结点的第一个孩子变为它的左孩子，兄弟节点变为他的右孩子。voidexchange（）,classTree先序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）访问根结点；（2）先序遍历左子树；（3）先序遍历右子树。voidPreOrder(BiNoderoot)。判断结点是否YN按前根遍历方式遍历左子树按前根遍历方式遍历左子树访问根结点结束开始判断结点是否YN按前根遍历方式遍历左子树按前根遍历方式遍历左子树访问根结点结束开始4.4.中序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）中序遍历左子树；（2）访问根结点；（3）中序判断结点是否空YN按中根遍历方式遍历左子树按中根遍历方式遍历右子树访问根结点结束开始判断结点是否空YN按中根遍历方式遍历左子树按中根遍历方式遍历右子树访问根结点结束开始后序遍历二叉树的递归算法若二叉树为空，则空操作；否则（1）后序遍历左子树；（2）后序遍历右子树。（3）访问根结点；voidPostOrder(BiNoderoot)。

图4、后序递归遍历先序非递归算法BiNode根指针，若BiNode!=NULL对于非递归算法，引入栈模拟递归工作栈，初始时栈为空。问题:如何用栈来保存信息，使得在先序遍历过左子树后，能利用栈顶信息获取BiNode的右子树的根指针？voidF_PreOrder(BiNoderoot)

图5、前序非递归遍历中序非递归算法BiNode是要遍历树的根指针，中序遍历要求在遍历完左子树后，访问根，再遍历右子树。问题：如何用栈来保存信息，使得在中序遍历过左子树后，能利用栈顶信息获取BiNode

指针？voidF_inOrder(BiNoderoot)。判断结点是否空判数组是否空判数组或结点是否空YNNYYN输出结点值root=s[top—]root=root->rchilds[++top]=root结点的值变为它的左孩子申请一个BiNode数组]inttop=0结束开始判断结点是否空判数组是否空判数组或结点是否空YNNYYN输出结点值root=s[top—]root=root->rchilds[++top]=root结点的值变为它的左孩子申请一个BiNode数组]inttop=0结束开始BiNode是要遍历树的根指针，后序遍历要求在遍历完左右子树后，再访问根。需要判断根结点的左右子树是否均遍历过。voidF_PostOrder(BiNoderoot)。

图7、后序非递归遍历层次序遍历算法按照树的层次从左到右访问树的结点，层序遍历用于保存结点的容器是队列。voidLevelOrder(BiNoderoot)。图8、层序遍历详细设计源程序:debug.h#ifndefI_DEBUG_H_#defineI_DEBUG_HclassNoMem//异常类public:NoMem(){}protected:private:classOutOfBoundspublic:OutOfBounds(){}protected:private:#endifLinkedQueue.h#ifndefI_LINKEDQUEUE_H_#defineI_LINKEDQUEUE_H_#include"Node.h”#include"debug.h”template<classT>classLinkedQueue{public:LinkedQueue(){front=rear=0;}~LinkedQueue();boolIsEmpty()const{return((front)?false:true);}boolIsFull()const;TFirst()const;TLast()const;LinkedQueue<T>&Add(constT&x);LinkedQueue<T>&Delete(T&x);protected:private:Node<T>*front;Node<T>*rear;};template<classT>LinkedQueue<T>::~LinkedQueue(){Node<T>*next;while(front){next=front->link;deletefront;front=next;}}template<classT>boolLinkedQueue<T>::IsFull()const{Node<T>*p;try{p=newNode<T>;deletep;returnfalse;}catch(NoMem){returnfalse;}}template<classT>TLinkedQueue<T>::First()const{if(IsEmpty())throwOutOfBounds();returnfront->data;}template<classT>TLinkedQueue<T>::Last()const{if(IsEmpty())throwOutOfBounds();returnrear->data;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Add(constT&x){Node<T>*p=newNode<T>;p->data=x;p->link=0;if(front)rear->link=p;elsefront=p;rear=p;return*this;}template<classT>LinkedQueue<T>&LinkedQueue<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=front->data;Node<T>*p=front;front=front->link;deletep;return*this;#endifstack.h#include"debug.h”template<classT>classSNode{public:Tdata;SNode<T>*link;protected:private:};template<classT>classStack{public:Stack(){top=0;}~Stack();boolIsEmpty()const{returntop==0;}boolIsFull()const;TTop()const;SNode<T>*TopAddress()const{returntop;}Stack<T>&Add(constT&x);Stack<T>&Delete(T&x);voidOutPut();protected:private:SNode<T>*top;};template<classT>Stack<T>::~Stack(){SNode<T>*next;while(top){next=top->link;deletetop;top=next;}}template<classT>boolStack<T>::IsFull()const{try{SNode<T>*p=newNode<T>;deletep;returnfalse;}catch(NoMem){returntrue;}}template<classT>TStack<T>::Top()const{if(IsEmpty())throwOutOfBounds();returntop->data;}template<classT>Stack<T>&Stack<T>::Add(constT&x){SNode<T>*p=newSNode<T>;p->data=x;p->link=top;top=p;return*this;}template<classT>Stack<T>&Stack<T>::Delete(T&x){if(IsEmpty())throwOutOfBounds();x=top->data;SNode<T>*p=top;top=top->link;deletep;return*this;}template<classT>voidStack<T>::OutPut(){SNode<T>*p=top;while(p){cout<<p->data;p=p->link;if(p)cout<<”->”cout<<endl;Node.h#ifndefI_NODE_H_#defineI_NODE_H_template<classT>classLinkedQueue;template<classT>classNode{friendclassLinkedQueue<T>;public:protected:private:Tdata;Node<T>*link;};#endiftreenode.h#ifndefI_TREENODE_H_#defineI_TREENODE_H_template<classT>classTree;template<classT>classTreeNode{friendclassTree<T>;public:TreeNode(){first_child=next_brother=0,children_num=0;}TreeNode(constT&e){data=e;first_child=next_brother=0;children_num=0;}protected:private:Tdata;TreeNode<T>*first_child,*next_brother;intchildrennum;#endiftree.h#ifndefI_TREE_H_#defineI_TREE_H_#include<iostream>#include<vector>#include"LinkedQueue.h”#include"stack.h”#include"treenode.h”usingnamespacestd;template<classT>classTree{public:Tree(){root=0;floor=0;}~Tree(){}voidInputTree();voidShowTree();voidShow_BinaryTree();voidShowPath();voidShow_BPath();voidDeleteTree();protected:private:voidDeleteNode(TreeNode<T>*p);voidSearchPath(TreeNode<T>*p,Stack<T>&mystack);voidSearch_BPath(TreeNode<T>*p,Stack<T>&mystack);voidPrint_BNode(TreeNode<T>*p,intc,vector<bool>&isend,boolRorL);voidPrintNode(TreeNode<T>*p,intc,vector<bool>&isend);TreeNode<T>*root;int*floor;};〃析构函数"""""""""""""""""""""""""""""""""""""""""""*******************************************template<classT>voidTree<T>::DeleteTree(){cout<<"销毁所建的树：〃<<endl<<endl;delete[floor;Stack<TreeNode<T>*>node_stack;DeleteNode(root);}template<classT>voidTree<T>::DeleteNode(TreeNode<T>*p){if(!p){return;}if(!p->first_child&&!p->next_brother){cout<<"删除节点"<<p->data<<"!"<<endl;deletep;return;}DeleteNode(p->first_child);p->first_child=0;DeleteNode(p->next_brother);p->next_brother=0;DeleteNode(p);p=0;}""""""""""""""""""""""""""""""""""""""""""""""""""""""""********************************************************//输入树""""""""""""""""""""""""""""""""""""""""""""""""""""""""********************************************************template<classT>voidTree<T>::InputTree(){LinkedQueue<TreeNode<T>*>Node_Q;Tnode_data=0;cout<<"请输入你要建立的树的高度："<<endl;intnum;cin>>num;if(num==0){cout<<"空树!"<<endl;exit(1);}if(num<0)throwOutOfBounds();floor=newint[num+1];floor[0]=num;cout<<"请输入你要建立的树的根节点数据："<<endl;cin>>node_data;TreeNode<T>*now,*mid;root=newTreeNode<T>(node_data);TreeNode<T>*last=root;boolbegin=true;floor[1]=1;Node_Q.Add(root);for(inti=2;i<=floor[0];i++)//每一层i{floor[i]=0;last=Node_Q.First();for(intj=1;j<=floor[i-1]&&last;j++)//每一层里每个节点j{cout<<"请输入节点"<<last->data<<"的子节点，并以#结束："<<endl;cin>>node_data;while(node_data!='#'){if(begin){now=newTreeNode<T>(node_data);last->first_child=now;begin=false;Node_Q.Add(now);}else{mid=newTreeNode<T>(node_data);now->next_brother=mid;now=mid;Node_Q.Add(now);}last->children_num++;floor[i]++;cin>>node_data;}if(!Node_Q.IsEmpty()){Node_Q.Delete(last);}if(!Node_Q.IsEmpty())last=Node_Q.First();begin=true;}}}个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个//输出树*个*个*******************************************************************template<classT>voidTree<T>::ShowTree(){cout<<"您输入的树是："<<endl;if(!root){cout<<"空树!"<<endl;exit(1);}TreeNode<T>*p=root;boolbegin=true;vector<bool>bIsEnd;bIsEnd.push_back(0);cout<<"Root:"<<root->data<<endl;for(inti=1;i<=floor[2];i++){if(i==floor[2])bIsEnd[0]=1;if(begin){p=p->first_child;begin=false;}elsep=p->next_brother;PrintNode(p,1,bIsEnd);}cout<<endl;}template<classT>voidTree<T>::PrintNode(TreeNode<T>*p,intc,vector<bool>&isend){for(intj=0;j<c;j++){//-LFIif(isend[j]==0)if(j!=c-1)cout<<"I";elsecout<<"卜”；elseif(j!=c-1)cout<<"";elsecout<<"L";if(j!=c-1)cout<<"";elsecout<<"—";}if(p)cout<<""<<p->data;cout<<endl;boolbegin=true;intlen=p->children_num;for(inti=1;i<=len;i++){if(isend.size()==c)isend.push_back(0);elseisend[c]=0;if(i==len)if(isend.size()==c)isend.push_back(1);elseisend[c]=1;if(begin){p=p->first_child;begin=false;}elsep=p->next_brother;PrintNode(p,c+1,isend);}}个***************************************************************//输出树的路径template<classT>voidTree<T>::ShowPath(){cout<<"树的路径是:"<<endl;if(!root){cout<<root->data<<endl;return;}Stack<T>mystack;mystack.Add(root->data);SearchPath(root->first_child,mystack);}template<classT>voidTree<T>::SearchPath(TreeNode<T>*p,Stack<T>&mystack){if(p)mystack.Add(p->data);elsereturn;if(!p->first_child){mystack.OutPut();}SearchPath(p->first_child,mystack);Tmid;mystack.Delete(mid);SearchPath(p->next_brother,mystack);}"""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""*********************************************************************//输出二叉树*个*个*******************************************************************template<classT>voidTree<T>::Show_BinaryTree(){cout<<"转化成二叉树是："<<endl;if(!root){cout<<"空树!"<<endl;exit(1);}TreeNode<T>*p=root;vector<bool>bIsEnd;bIsEnd.push_back(0);cout<<"Root:"<<root->data<<endl;bIsEnd[0]=1;{p=p->first_child;}Print_BNode(p,1,bIsEnd,false);cout<<endl;}template<classT>voidTree<T>::Print_BNode(TreeNode<T>*p,intc,vector<bool>&isend,boolRorL){if(!p){return;}for(intj=0;j<c;j++){//-LFIif(isend[j]==0)if(j!=c-1)cout<<"I";elsecout<<"卜”；elseif(j!=c-1)cout<<"";elsecout<<"L";if(j!=c-1)cout<<"";elsecout<<"—";}cout<<""<<p->data;if(RorL){cout<<"R";}elsecout<<"L";cout<<endl;intlen;if(p->first_child&&p->next_brother){len=2;}elseif(!p->first_child&&!p->next_brother){len=0;}elselen=1;for(inti=1;i<=len;i++){if(isend.size()==c)isend.push_back(0);elseisend[c]=0;if(i==len)if(isend.size()==c)isend.push_back(1);elseisend[c]=1;if(len==2){if(i==1){Print_BNode(p->first_child,c+1,isend,false);p=p->next_brother;}elsePrint_BNode(p,c+1,isend,true);}elseif(len==1){if(p->first_child)Print_BNode(p->first_child,c+1,isend,false);if(p->next_brother){Print_BNode(p->next_brother,c+1,isend,true);}}}}//""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""""个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个个〃输出二叉树路径""""""""""""""""""""""""""""""""""""""""""""""""""""""""*个*个****************************************************template<classT>voidTree<T>::Show_BPath(){cout<<"二叉树的路径是:"<<endl;Stack<T>mystack;mystack.Add(root->data);Search_BPath(root->first_child,mystack);}template<classT>voidTree<T>::Search_BPath(TreeNode<T>*p,Stack<T>&mystack){if(!p){return;}mystack.Add(p->data);Tmid;if(!p->first_child&&!p->next_brother){mystack.OutPut();}SNode<T>*now=mystack.TopAddress();Search_BPath(p->first_child,mystack);while(mystack.TopAddress()!=now){mystack.Delete(mid);}Search_BPath(p->next_brother,mystack);}#endifmain3.cpp#include<iostream>usingnamespacestd;#include<stdlib.h>#include<math.h>#definemaxIsize100#include"tree.h”#defineLENsizeof(structbtree)intmaxI=1;typedefstructbtree//二叉树节点结构体{btree*lchild,*rchild;chardata;}*BiNode;typedefstructStackElemType//栈的结构体{BiNodeptr;intflag;}StackElemType;BiNodep;//二叉树的建立BiNodestree_creat(char*a,intk){BiNoderoot;maxI++;if(a[k]=='\0'||k>maxIsize)returnNULL;//判断树是否为空else{root=(BiNode)malloc(LEN);//动态申请节点root->data=a[k];root->lchild=stree_creat(a,2*k+1);//递归调用为左孩子赋值root->rchild=stree_creat(a,2*k+2);//递归调用为右子赋值returnroot;//返回根节点指针}}voidprint(BiNoderoot)//输出所创建的二叉树{BiNodeh[maxIsize]={NULL};doubletop=0,j=0,m=0;intbase=0,n=0,k=0,topInt=0;h[topInt]=root;j=log(maxI+1)/log(2)-1;if(pow(2,j+1)-1<maxI)j++;cout<<"你刚输入的是：\n”;while(h[base]!=NULL)//把二叉树的值依次存入数组{h[++topInt]=h[base]->lchild;h[++topInt]=h[base]->rchild;base++;}for(topInt=0,top=0;h[k]!=NULL;topInt++)//按层输出{m=pow(2,j)-top;//计算每行输出的空格数if(top!=0)m=m-top;for(n=0;n<m;n++)cout<<"";for(base=0;base<pow(2,top)&&h[k]!=NULL;base++)//控制每层输出的个数{if(h[k]->data=='0')cout<<〃[〃<<〃]〃；//当为空时输出:]elsecout<<h[k]->data<<"";k++;}cout<<"\n";for(n=0;n<(m-1);n++)cout<<"";for(base=0;base<pow(2,top)&&h[k]!=NULL;base++)cout<<"/"<<"|";cout<<"\n";top+=1;}}〃二叉树的后序遍历递归算法voidPostOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{PostOrder(root->lchild);PostOrder(root->rchild);if(root-〉data=='0');elsecout<<"["<<root->data<<"]";}}〃二叉树的中序遍历递归算法voidInOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{InOrder(root->lchild);if(root->data=='0');elsecout<<"["<<root->data<<"]";InOrder(root->rchild);}}〃二叉树的前序递归遍历算法voidPreOrder(BiNoderoot){if(root==NULL)return;//递归调用的约束条件else{if(root->data=='0');elsecout<<"["<<root->data<<"]";PreOrder(root->lchild);PreOrder(root->rchild);}}〃二叉树的前序遍历非递归算法voidF_PreOrder(BiNoderoot){BiNodes[maxIsize];//申请一个BiNode数组inttop=0;//采用顺序栈，并假定不会发生上溢do{while(root!=NULL)//当结点不为空时{if(root->data=='0');elsecout<<"["<<root->data<<"]";s[++top]=root;//依次将结点压入栈root=root->lchild;//根赋值为它的左孩子}if(top>0)//当节点为空但栈顶不为零时{root=s[top--];//栈顶下移把栈顶元素负给根结点root=root->rchild;//根赋值为它的右子}}while(root!=NULL||top>0);}//中序非递归遍历算法voidF_inOrder(BiNoderoot){BiNodes[maxIsize];//申请一个BiNode数组inttop=0;〃采用顺序栈，并假定不会发生上溢do{while(root!=NULL)//当结点不为空时{s[++top]=root;//依次将结点压入栈root=root->lchild;//根赋值为它的左孩子}if(top>0)//当节点为空但栈顶不为零时{root=s[top];//把栈顶元素负给根结点if(root->data=='0');elsecout<<"["<<root->data<<"]";//输出根结点root=s[top--];//栈顶下移把栈顶元素负给根结点root=root->rchild;//根赋值为它的右子}}while(root!=NULL||top>0);}//后序非递归遍历算法voidF_PostOrder(BiNoderoot){//申请一个StackElemType数组StackElemTypes[maxIsize];BiNodep=root;inttop=0;do{while(p!=NULL)//当结点不为空时{s[top].flag=0;//标记位负为零s[top].ptr=p;//将树的结点依次压入栈中p=p->lchild;//树沿左子树下移top++;}while(s[top-1].flag==1)//当栈的最上面元素标记位为一时输出{if(s[topT].ptr-〉data=='0')top--;elsecout<<"["<<s[--top].ptr->data<<”]”;}if(top>0)//当节点为空但栈顶不为零时{s[top-1].flag=1;//栈的最上面元素标记位赋值为一p=s[top-1].ptr;//栈的最上面元素树结点赋给pp=p->rchild;//树沿右子树下移}}while(top>0);}//层序遍算法voidLevelOrder(BiNoderoot){BiNodes[maxIsize];//申请一个BiNode数组intmaxI,i=0;s[0]=root;//数组首元赋为根结点while(root!=NULL)//当结点不空时{s[2*i+1]=root->lchild;//左孩子赋给下标为2*i+1的数组员s[2*i+2]=root->rchild;//右孩子赋给下标为2*i+1的数组员i++；root=s[i];//root变为当前数组元素的值maxI=i;}for(i=0;i<maxI;i++){if(s[i]->data=='0');elsecout<<":"<<s[i]->data<<"]";//依次输出}}voidPause(){cout<<endl<<endl<<endl;system("pause");cout<<endl<<endl<<endl;}//树转换为二叉树voidexchange(){Tree<char>myTree1;//实例化一个TreeclassmyTree1.InputTree();//调用InputTree()函数Pause();myTree1.ShowTree();//调用ShowTree()函数Pause();myTree1.Show_BinaryTree();//调用Show_BinaryTree()函数Pause();}//输入二叉树信息的函数BiNodecreat(){BiNodep=NULL;cout<<"请输入你的二叉树(请按层次由上往下从左到右依次输入并按#结束，如果节点为空请输入'0',本遍历器仅支持单字符)，输入为:\n";inti=0,j=0;charb[maxIsize]={'#'},n;〃当输入不为'#'时给数组赋值do{cin>>n;if(n!='#')b[i]=n;i++;}while(n!='#');p=stree_creat(b,0);//创建树print(p);//输出树returnp;}//主函数intmain(){intk;cout<<"\n"cout<<"\ncout<<"|欢迎使用树的多种遍历器cout<<"|树与二叉树的转换cout<<"|cout<<"\n";do{cout<<"\n";cout<<"\n1.创建二叉树";cout<<"\n2.前序递归遍历算法";cout<<"\n3.中序递归遍历算法";cout<<"\n4.后序递归遍历算法";cout<<"\n5.前序非递归遍历算法";cout<<"\n6.中序非递归遍历算法";cout<<"\n7.后序非递归遍历算法";cout<<"\n8.层序非递归遍历算法";cout<<"\n9.树与二叉树的转换"；cout<<"\n10.退出操作\n”;cout<<"请选择你要进行的操作(数字键)：〃；cin>>k;switch(k){case1:{p=creat();//调用creat()创建二叉树}break;case2:{cout<<"二叉树的前序递归遍历："；PreOrder(p);//调用PreOrder(p)前序遍历}break;case3:{cout<<"二叉树的中序递归遍历："；InOrder(p);〃调用InOrder(p)中序遍历}break;case4:{cout<<"二叉树的后序递归遍历："；PostOrder(p);//调用PostOrder(p)后序遍历}break;case5:{cout<<"二叉树前序非递归遍历:";F_PreOrder(p);〃调用F_PreOrder(p)前序遍历}break;case6:{cout<<"二叉树中序非递归遍历："；F_inOrder(p);〃调用F_inOrder(p)中序遍历}break;case7:{cout<<"二叉树后序非递归遍历:";F_PostOrder(p);}break;case8:{cout<<"二叉树层序非递归遍历:";LevelOrder(p);}break;case9:{exchange();//调用exchange()实现树与二叉树的转换deletep;returnmain();//返回主函数}break;}}while(k>=0&&k<9);return0;}调试分析二叉树遍历中用到的最重要的一个思想就是递归调用，这次作业使我们对递归有了深入的理解，尤其是对退回上一层后应执行的语