数据结构课程设计二叉树遍历C++语言

淮阴工学院实践报告数据结构课程设计设计题目： 二叉树遍历 系别：计算机工程学院 专业：软件工程班级：软件1111学生姓名: 周淼学号:1111315217 起止日期:2012年指导教师： 寇海洲 摘要： 现代社会生活中，计算机扮演着重要角色，而随着计算机运行速度的不断加快，对数据的处理能力也日益增强，因此，程序所涉及的数据成爆发式增长。随之而来的问题就是如何科学有效的对数据进行操作，使得计算机的时间和空间利用率最高。针对这样的问题，我选择了二叉树对数据的各种操作作为我的课程设计主题，希望通过课程设计来提高对数据的处理能力，促进对数据结构课程的理解，在日后面向对象的程序设计中科学的规划数据结构。在本次课程设计中，二叉树的建立使用了递归算法，遍历则同时使用了递归与非递归的算法，同时，在遍历算法的实现中使用了栈结构与队列结构，这大大方便了二叉树的遍历。在前序、中序、后续遍历算法中，分别实现了递归与非递归算法，从实际应用中体验了递归这一算法的优越性。关键词：二叉树建立，递归与非递归，遍历，栈，队列

编号： 47淮阴工学院 软件工程 专业数据结构课程设计答辩记录课题名称：二叉树的算法班级软件1111学号1111315217姓名周淼答辩记录问题1：课题中涉及到哪些数据结构和算法？答：1）数组，二叉树，栈，队列，线性表2）二叉树的中序、前序、后序的递归、非递归遍历算法，层次序遍历非递归算法，栈、队列的实现算法问题2：课题研究和设计中的关键技术是什么？答：关键技术是二叉树的建立，以及栈结构、队列的算法实现问题3：课题的主要功能和模块有哪些？答：1）主要功能：根据数据建立二叉树，实现二叉树的中序、前序、后序遍历2）模块：栈的应用，队列结构的应用，二叉树的操作问题4：课题在实现过程中遇到的主要难点有哪些？答：遍历二叉树过程中栈结构以及队列的使用问题5：课题中未能实现的功能有哪些？答：以树形结构输出完全二叉树记录人：寇海洲2012年12月28日

目 录1需求分析 5二叉树与树结构 5面向对象的程序设计 5二叉树遍历的应用 5软件运行环境：版本 52概要设计 62.1总体功能结构 6数据结构部分设计 6结点结构 62.2.2二叉树结构 73详细设计 12建立二叉树 12功能描述 12算法原理 123.1.3具体程序 123.2前序遍历 133.2.1功能原理 133.2.2算法原理 133.2.3具体程序 133.3中序遍历 143.3.1功能原理 143.3.2算法原理 143.3.3具体程序 143.4后序遍历 15功能原理 153.4.2算法原理 153.4.3具体程序 16层次序非递归遍历 173.5.1功能原理 173.5.2算法原理 173.5.3具体程序 173.6栈结构 183.6.1功能原理 18算法原理 183.6.3具体程序 183.7队列结构 193.7.1功能原理 193.7.2算法原理 193.7.3具体程序 194调试与操作说明 20致 谢 23参考文献 24附录： 25

1需求分析二叉树与树结构树结构的是建立在数据逻辑结构基础上的数据结构类型，二叉树则是树结构中最常见和使用最多的类型。通过对二叉树的操作，可以实现多种数据操作，如排序、查找等。一个好的二叉树遍历算法应包含以下功能： 1）以递归和非递归方法建立二叉树或完全二叉树； 2）实现二叉树的前序遍历、中序遍历、后序遍历； 3）每种遍历算法皆以递归和非递归方法实现； 4）在具体实现时应用其他数据结构类型对数据进行操作，如：栈，队列，数组。 在面向对象的程序设计中，模板的使用很普遍，因此，如何在程序设计中使用模板使得方法的实现与定义分开，程序模块化，既方便了程序设计者，又为程序的后期维护带来便利。当数据以数组或文档形式存储在内存时，其数据之间虽有逻辑联系，却过于分散，因此，建立二叉树以存储数据并且遍历该二叉树，可以从逻辑上理顺数据之间的关系，使得原本分数的数据排列的有序且可靠。一个好的二叉树应用算法其空间复杂度与时间复杂度必然最低，这样给程序带来时间和空间上的极大优化。1.4软件运行环境

2概要设计2.1总体功能结构 二叉树的遍历，主要包含以下功能： 1）建立二叉树：递归方法、非递归方法 2）中序遍历：递归方法、非递归方法 3）前序遍历：递归方法、非递归方法 4）后序遍历：递归方法、非递归方法 5）栈结构使用：遍历时输入临时变量以保存 6）队列结构使用：完全二叉树遍历时用以存储数据 部分设计结点结构 二叉树结点结构中包数据域（data），指针域（*leftChild，*rightChild）。结点结构的代码如下：structBinTreeNode{ //树结点 Tdata; BinTreeNode<T>*leftChild; BinTreeNode<T>*rightChild; BinTreeNode():leftChild(NULL),rightChild(NULL){} BinTreeNode(Tx,BinTreeNode<T>*l=NULL,BinTreeNode<T>*r=NULL) :leftChild(l),rightChild(r){ data=x;}栈结构结点包含数据域（data），指针域（*link），实现代码如下：structStackNode{ //栈结点 Tdata; StackNode<T>*link; StackNode(Td=0,StackNode<T>*next=NULL):link(next),data(d){}}; 队列结构结点包含数据域（data），指针域（*link），实现代码如下：structLinkNode{ Tdata; LinkNode<T>*link; LinkNode(LinkNode<T>*ptr=NULL){ link=ptr; } LinkNode(constT&item,LinkNode<T>*ptr=NULL){ data=item; link=ptr; }};};二叉树结构二叉树包含了递归、非递归建树过程，递归、非递归的前序遍历、中序遍历、后续遍历过程。二叉树的类定义包含各种操作，实现代码如下：template<typenameT>classBinaryTree{ //二叉树类定义public: BinaryTree():root(NULL){} BinaryTree(Tvalue):root(NULL){ RefValue=value; } BinaryTree(BinaryTree<T>&s){ if(this!=&s){ root=Copy(s.root); } } ~BinaryTree(){ destroy(root); } BinTreeNode<T>*Parent(BinTreeNode<T>*t){ return(root==NULL||root==t)?NULL:Parent(root,t); } BinTreeNode<T>*LeftChild(BinTreeNode<T>*t){ return(t!=NULL)?t->leftChild:NULL; } BinTreeNode<T>*RightChild(BinTreeNode<T>*t){ return(t!=NULL)?t->rightChild:NULL; } voidPreOrder(void(*visit)(BinTreeNode<T>*t)){ PreOrder(root,visit); } voidInOrder(void(*visit)(BinTreeNode<T>*t)){ InOrder(root,visit); } voidPostOrder(void(*visit)(BinTreeNode<T>*t)){ PostOrder(root,visit); } voidCreateCompBinTree(T*CBT,intnum){//建立完全二叉树 CreateCompBinTree(CBT,num,0,root); } voidlevelOrder(void(*visit)(BinTreeNode<T>*t)); //层次序遍历 voidPreOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归前序遍历 voidInOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归中序遍历 voidPostOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归后序遍历 friendistream&operator>>(istream&in,BinaryTree<T>&Tree){//输入二叉树ot); returnin; }栈结构的定义中，包含了对数据的入栈、出栈、清空等基本操作，实现代码如下template<typenameT>classLinkedStack{private: StackNode<T>*top;public: LinkedStack():top(NULL){} //无头结点 ~LinkedStack(){ makeEmpty(); } voidPush(constT&x); boolPop(T&x); boolIsEmpty()const{ returntop==NULL; } boolIsFull()const{ returnfalse; } voidmakeEmpty(); friendostream&operator<<(ostream&os,LinkedStack<T>&s) { os<<"StackSize:"<<s.getSize()<<endl; StackNode<T>*p=s.top; inti=0; while(p){ os<<++i<<":"<<p->data<<endl; p=p->link; } returnos; }};template<typenameT>voidLinkedStack<T>::makeEmpty(){ StackNode<T>*p; while(top){ p=top; top=top->link; deletep; }}队列的类定义，实现了对数据的入队、出队操作，实现代码如下：template<typenameT>classLinkedQueue{ //无头结点public: LinkedQueue(){ rear=NULL; front=NULL; } ~LinkedQueue(){ makeEmpty(); } boolEnQueue(constT&x); boolDeQueue(T&x); voidmakeEmpty(); boolIsEmpty()const{ returnfront==NULL; } friendostream&operator<<(ostream&os,LinkedQueue<T>&Q){ LinkNode<T>*p=Q.front; inti=0; while(p){ os<<"#"<<++i<<":"<<p->data<<endl; p=p->link; } os<<"QueueSize:"<<Q.getSize()<<endl; returnos; } voidoutput();protected: LinkNode<T>*front,*rear;};

3详细设计建立二叉树功能描述二叉树是程序的核心，如何合理的建立至关重要。本实例中使用递归和非递归方法分别建立二叉树，二叉树的数据来源于程序开始时建立的数组。建立后的二叉树保存，并且留作之后的遍历使用。算法原理本实例使用的是完全二叉树，首先建立头结点，并且保存数据，然后根据递归方法，分别建立其左右孩子结点，且左右孩子结点的指针域指向空。具体程序以递归方式建立二叉树，每次建立一个结点后，将其左右孩子指针域置空，成为叶子结点。具体实现代码如下：template<typenameT>voidBinaryTree<T>::CreateBinTree(istream&in,BinTreeNode<T>*&subTree){ Titem; if(in>>item){ if(item!=RefValue){ subTree=newBinTreeNode<T>(item); //CreateRoot assert(subTree); CreateBinTree(in,subTree->leftChild); //Createleftchildtree CreateBinTree(in,subTree->rightChild); //Createreghtchildtree } else { subTree=NULL; } }}//建立完全二叉树template<typenameT>voidBinaryTree<T>::CreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode<T>*&subTree){ if(rt>=num) { subTree=NULL; } else{ subTree=newBinTreeNode<T>(CBT[rt]); } CreateCompBinTree(CBT,num,2*rt+1,subTree->leftChild); CreateCompBinTree(CBT,num,2*rt+2,subTree->rightChild); }}前序遍历功能原理通过前序遍历，将二叉树中的数据按照前序遍历的结果输出，达到前序便利的目的，方便数据的使用。算法原理前序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈或队列中，等待将数据放到合适位置。具体程序1）递归算法实现：template<typenameT>voidBinaryTree<T>::PreOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ if(subTree!=NULL){ visit(subTree); PreOrder(subTree->leftChild,visit); PreOrder(subTree->rightChild,visit); }}2）非递归算法实现：template<typenameT>voidBinaryTree<T>::PreOrder1(void(*visit)(BinTreeNode<T>*t)){ LinkedStack<BinTreeNode<T>*>S; BinTreeNode<T>*p=root; S.Push(NULL); while(p!=NULL){ visit(p); //访问结点 if(p->rightChild!=NULL) S.Push(p->rightChild);//预留右指针在栈中 if(p->leftChild!=NULL) p=p->leftChild; //进左子树 elseS.Pop(p); //左子树为空，由堆栈弹出 }}中序遍历3.功能原理通过中序遍历，将二叉树中的数据按照中序序遍历的结果输出，达到中序遍历的目的，实现数据的最优，方便数据的使用。3.算法原理中序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈与队列中，等待将数据放到合适位置。3.具体程序1）递归算法实现：template<typenameT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ if(subTree!=NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); }}2）非递归算法实现：template<typenameT>voidBinaryTree<T>::InOrder1(void(*visit)(BinTreeNode<T>*t)){//非递归中序遍历LinkedStack<BinTreeNode<T>*>S; BinTreeNode<T>*p=root;while(p!=NULL||!S.IsEmpty()){ while(p!=NULL){ //遍历指针向左下移动 S.Push(p); //该子树沿途结点进栈 p=p->leftChild; } if(!S.IsEmpty()){ //栈不空时退栈 S.Pop(p); visit(p); //退栈,访问 p=p->rightChild; //遍历指针进到右子女 } }}后序遍历3.功能原理通过后序遍历，将二叉树中的数据按照后序遍历的结果输出，达到后序遍历的目的，实现数据的最优，方便数据的使用。3.算法原理后序遍历使用了递归与非递归两种方法，在程序头文件中定义了两个函数分别实现其功能。递归时，输出第一个结点数据时，找到数据，然后依次找到其后面的数据，然后依次递归输出。非递归时，使用栈和队列结构，将部分数据保存在栈与队列中，等待将数据放到合适位置。3.具体程序1）递归算法实现：template<typenameT>voidBinaryTree<T>::PostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ if(subTree!=NULL){ PostOrder(subTree->leftChild,visit); PostOrder(subTree->rightChild,visit); visit(subTree); }}2）非递归算法实现：template<typenameT>voidBinaryTree<T>::PostOrder1(void(*visit)(BinTreeNode<T>*t)){ //非递归后序遍历 LinkedStack<stkNode<T>>S; stkNode<T>w; BinTreeNode<T>*p=root;//p是遍历指针 do{ while(p!=NULL){ w.ptr=p; w.tag=stkNode<T>::L; //枚举类型定义在structstkNode中，如定义为全局性就简单了 S.Push(w); p=p->leftChild; } intcontinue1=1; while(continue1&&!S.IsEmpty()){ S.Pop(w);p=w.ptr; switch(w.tag){ //判断栈顶的tag标记 casestkNode<T>::L:w.tag=stkNode<T>::R; S.Push(w); continue1=0; p=p->rightChild;break; casestkNode<T>::R:visit(p);break; } }}while(!S.IsEmpty()); //继续遍历其他结点cout<<endl;}3.5层次序非递归遍历3.功能原理层次序非递归遍历，依据的是递归原理，每次遍历一个结点后，同时让其左右孩子入队，以便达到层次序的目的。3.算法原理每次遍历完一个结点后，检查该结点是否为叶子结点，如果是叶子结点则继续下一结点的遍历，否则其左右孩子入队，继续遍历。3.具体程序template<typenameT>voidBinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>*t)){//层次序遍历if(root==NULL)return;LinkedQueue<BinTreeNode<T>*>Q;BinTreeNode<T>*p=root;visit(p);Q.EnQueue(p); while(!Q.IsEmpty()){Q.DeQueue(p);if(p->leftChild!=NULL){ visit(p->leftChild); Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){ visit(p->rightChild); Q.EnQueue(p->rightChild);}}}3.6栈结构3.功能原理运用栈结构，在非递归算法中，未输出的数据暂时存入栈中，依据先进后出原则，方便了二叉树的遍历。3.算法原理二叉树的结点信息，保存在栈中。第一个入栈的数据元素保存在栈底，后进栈的在上方，现出栈。3.具体程序template<typenameT>voidLinkedStack<T>::Push(constT&x){ top=newStackNode<T>(x,top);}template<typenameT>boolLinkedStack<T>::Pop(T&x){ if(IsEmpty()){ returnfalse; } StackNode<T>*p=top; top=top->link; x=p->data; deletep; returntrue; }队列结构3.功能原理运用队列结构，在层次序遍历算法中，未输出的数据暂时存入队列中，依据先进先出原则，方便了二叉树的遍历。3.算法原理层次序遍历二叉树信息时，二叉树的结点信息保存在队列中。第一个入队的数据元素保存队首，后入队的元素依次连接上，先入队的先出队。3.具体程序template<typenameT>voidLinkedQueue<T>::makeEmpty(){ LinkNode<T>*p; while(front){ p=front; front=front->link; deletep; }}template<typenameT>boolLinkedQueue<T>::EnQueue(constT&x){ if(!front){ front=rear=newLinkNode<T>(x); if(!front) returnfalse; } else{ rear->link=newLinkNode<T>(x); if(!(rear->link)) returnfalse; rear=rear->link; } returntrue;}template<typenameT>boolLinkedQueue<T>::DeQueue(T&x){ if(IsEmpty()) returnfalse; LinkNode<T>*p=front; x=front->data; front=front->link; deletep; returntrue;}template<typenameT>voidLinkedQueue<T>::output(){ LinkNode<T>*p=front;inti=1; while(i<=getSize()) { cout<<p->data<<""<<endl; p=p->link;i++; }}4调试与操作说明操作说明：当程序运行后，会在控制台提示一下文字：“从数组数据建立完全二叉树:”，“输入二叉树的元素总个数:”，然后从键盘输入二叉树元素个数，紧接着系统会自动运行，得到各种遍历结果。运行截图：完全二叉树32个元素时的运行截图

总 结这次的课程设计我选择了二叉树的遍历，因为树结构是数据结构课程的典型内容，而且综合使用了多种逻辑结构，具有代表性，可以锻炼个人编程能力。在刚开始选题后，我感觉无从下手，一是因为没有实践经验，二是因为对数据结构课程的内容没有把握到位，然后在参考一些专业书籍并且学习了之前其他人的课程设计，才逐渐可以上手去自己做。在做了一小段后我发现如果不使用数组来建立二叉树是很麻烦的一件事，每个结点的信息都靠键盘输入是不合理的，于是运用了数组这一数据类型。在之后的递归算法中，我遇到的最大困难是如何实现递归，为此我参考了一本专业书籍，学会了如何正确使用递归方法，这也让我感觉到学习与应用是不可分开的。对于非递归算法，我使用了栈结构和队列结构，分别用于前序遍历、中序、后序遍历、非递归层次序遍历方法中。使用栈和队列的过程中，我在实践中又学习了栈和队列的一些知识，提高了各种逻辑结构之间的综合运用能力。在后期测试阶段，我参考了许多课程设计案例，他们都运用了switch（）语句，这样虽然看着有条理，却不适合用在二叉树的遍历上，因为遍历结果显而易见并不十分复杂，没有必要使程序复杂化，因此我采用的是程序运行输出模式。总体来说，在本次课程设计中，我深刻体会了再面向对象程序设计中数据结构的实现方法，既学到了专业知识，也体会到“温故知新”的乐趣，因此如果还有课程设计我还会积极参加，在实践中锻炼自己的能力水平。

致 谢对我来说这次课程设计的机会来之不易，首先我的父母辛苦工作，用他们赚到的血汗钱供我读书，让我有机会接受高等教育。其次，我的课程设计指导老师寇老师，冒着严寒每天早早地到机房为我指导、调试程序，从没有一句怨言。再者，我的《数据结构》授课教师周教授，从一开始接触这门课就不辞辛劳的给我传授知识，教我学的立足社会的资本。对你们，我想发自内心的说一句：谢谢你们，辛苦了！

参考文献（1）《数据结构（用面向对象方法与C++语言描述）》殷人昆清华大学出版社（2）《深入体验C++项目开发》管西京清华大学出版社（3）《C++程序员教程》(美)Deitel.P.J.,(美)Deitel,H.M.著 北京电子工业出版社

附录：程序源代码：//mian（）主函数中：#include"BinaryTree.h"#include<iostream>#include<fstream>#include<iomanip>usingnamespacestd;voidvisit(BinTreeNode<int>*t){ cout<<t->data<<"";}voidmain(){ BinaryTree<int>binTree(0); cout<<"从数组数据建立完全二叉树:\n"; cout<<"输入二叉树的元素总个数:"; longnum; cin>>num; int*CBT=newint[num]; cout<<"\n数组中数据为:\n"; for(inti=0;i<num;i++){ CBT[i]=i+1; cout<<setw(4)<<i+1; } cout<<endl; BinaryTree<int>binTree1; binTree1.CreateCompBinTree(CBT,num); cout<<"\n完全二叉树前序遍历结果:\n"; binTree1.PreOrder(visit); cout<<"\n\n完全二叉树中序遍历结果:\n"; binTree1.InOrder(visit); cout<<"\n\n完全二叉树后序遍历结果:\n"; binTree1.PostOrder(visit); cout<<"\n完全二叉树非递归前序遍历结果:\n"; binTree1.PreOrder1(visit); cout<<"\n\n完全二叉树非递归中序遍历结果:\n"; binTree1.InOrder1(visit); cout<<"\n\n完全二叉树非递归后序遍历结果:\n"; binTree1.PostOrder1(visit); cout<<"\n完全二叉树层次序遍历结果:\n"; binTree1.levelOrder(visit); cout<<endl; delete[]CBT;}#include<string>#include<cassert>#include<iostream>usingnamespacestd;#include"LinkedStack.h"#include"LinkedQueue.h"template<typenameT>structBinTreeNode{ //树结点 Tdata; BinTreeNode<T>*leftChild; BinTreeNode<T>*rightChild; BinTreeNode():leftChild(NULL),rightChild(NULL){} BinTreeNode(Tx,BinTreeNode<T>*l=NULL,BinTreeNode<T>*r=NULL) :leftChild(l),rightChild(r){ data=x; }};template<typenameT>classBinaryTree{ //二叉树类定义public: BinaryTree():root(NULL){} BinaryTree(Tvalue):root(NULL){ RefValue=value; } BinaryTree(BinaryTree<T>&s){ if(this!=&s){ root=Copy(s.root); } } ~BinaryTree(){} BinTreeNode<T>*Parent(BinTreeNode<T>*t){ return(root==NULL||root==t)?NULL:Parent(root,t); } BinTreeNode<T>*LeftChild(BinTreeNode<T>*t){ return(t!=NULL)?t->leftChild:NULL; } BinTreeNode<T>*RightChild(BinTreeNode<T>*t){ return(t!=NULL)?t->rightChild:NULL; } voidPreOrder(void(*visit)(BinTreeNode<T>*t)){ PreOrder(root,visit); } voidInOrder(void(*visit)(BinTreeNode<T>*t)){ InOrder(root,visit); } voidPostOrder(void(*visit)(BinTreeNode<T>*t)){ PostOrder(root,visit); } voidCreateCompBinTree(T*CBT,intnum){//建立完全二叉树 CreateCompBinTree(CBT,num,0,root); } voidlevelOrder(void(*visit)(BinTreeNode<T>*t)); //层次序遍历 voidPreOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归前序遍历 voidInOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归中序遍历 voidPostOrder1(void(*visit)(BinTreeNode<T>*t)); //非递归后序遍历 friendistream&operator>>(istream&in,BinaryTree<T>&Tree){//输入二叉树 Tree.CreateBinTree(in,Tree.root); returnin; } protected: BinTreeNode<T>*root; //二叉树的根指针 TRefValue; //数据输入停止标志 voidCreateBinTree(istream&in,BinTreeNode<T>*&subTree); //递归建立二叉树 voidCreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode<T>*&subTree); //建立完全二叉树 BinTreeNode<T>*Copy(BinTreeNode<T>*r); //复制二叉树r voidTraverse(BinTreeNode<T>*subTree,ostream&out); //遍历输出 voidPreOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)); //前序遍历 voidInOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)); //中序遍历 voidPostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)); //后序遍历};template<typenameT>voidBinaryTree<T>::CreateBinTree(istream&in,BinTreeNode<T>*&subTree){ //私有函数:以递归方式建立二叉树。 Titem; if(in>>item){ if(item!=RefValue){ subTree=newBinTreeNode<T>(item); //CreateRoot assert(subTree); CreateBinTree(in,subTree->leftChild); //Createleftchildtree CreateBinTree(in,subTree->rightChild); //Createreghtchildtree } else { subTree=NULL; } }}template<typenameT>voidBinaryTree<T>::CreateCompBinTree(T*CBT,intnum,intrt,BinTreeNode<T>*&subTree){ //建立完全二叉树 if(rt>=num) { subTree=NULL; } else{ subTree=newBinTreeNode<T>(CBT[rt]); CreateCompBinTree(CBT,num,2*rt+1,subTree->leftChild); CreateCompBinTree(CBT,num,2*rt+2,subTree->rightChild); }}template<typenameT>BinTreeNode<T>*BinaryTree<T>::Copy(BinTreeNode<T>*r){//递归复制二叉树 if(!r) returnNULL; BinTreeNode<T>*p=newBinTreeNode<T>(r->data); p->leftChild=Copy(r->leftChild); p->rightChild=Copy(r->rightChild); returnp;}template<typenameT>voidBinaryTree<T>::Traverse(BinTreeNode<T>*subTree,ostream&out){ //前序遍历输出结点数据 if(subTree){ out<<subTree->data<<''; Traverse(subTree->leftChild,out); Traverse(subTree->rightChild,out); }}template<typenameT>voidBinaryTree<T>::PreOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ //递归前序遍历 if(subTree!=NULL){ visit(subTree); PreOrder(subTree->leftChild,visit); PreOrder(subTree->rightChild,visit); }}template<typenameT>voidBinaryTree<T>::InOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ //递归中序遍历 if(subTree!=NULL){ InOrder(subTree->leftChild,visit); visit(subTree); InOrder(subTree->rightChild,visit); }}template<typenameT>voidBinaryTree<T>::PostOrder(BinTreeNode<T>*subTree,void(*visit)(BinTreeNode<T>*t)){ //递归后序遍历 if(subTree!=NULL){ PostOrder(subTree->leftChild,visit); PostOrder(subTree->rightChild,visit); visit(subTree); }}template<typenameT>voidBinaryTree<T>::PreOrder1(void(*visit)(BinTreeNode<T>*t)){ //非递归前序遍历 LinkedStack<BinTreeNode<T>*>S; BinTreeNode<T>*p=root; S.Push(NULL); while(p!=NULL){ visit(p); //访问结点 if(p->rightChild!=NULL) S.Push(p->rightChild);//预留右指针在栈中 if(p->leftChild!=NULL) p=p->leftChild; //进左子树 elseS.Pop(p); //左子树为空，由堆栈弹出 }}template<typenameT>voidBinaryTree<T>::InOrder1(void(*visit)(BinTreeNode<T>*t)){//非递归中序遍历LinkedStack<BinTreeNode<T>*>S; BinTreeNode<T>*p=root;while(p!=NULL||!S.IsEmpty()){ while(p!=NULL){ //遍历指针向左下移动 S.Push(p); //该子树沿途结点进栈 p=p->leftChild; } if(!S.IsEmpty()){ //栈不空时退栈 S.Pop(p); visit(p); //退栈,访问 p=p->rightChild; //遍历指针进到右子女 } }}template<typenameT>structstkNode{ BinTreeNode<T>*ptr;//树结点指针 enum{L,R}tag;//退栈标记，必须说明为枚举变量，tag移到最右边。这里最好用bool量 stkNode(BinTreeNode<T>*N=NULL){ //构造函数 ptr=N; tag=L; } };template<typenameT>voidBinaryTree<T>::PostOrder1(void(*visit)(BinTreeNode<T>*t)){ //非递归后序遍历 LinkedStack<stkNode<T>>S; stkNode<T>w; BinTreeNode<T>*p=root;//p是遍历指针 do{ while(p!=NULL){ w.ptr=p; w.tag=stkNode<T>::L; //枚举类型定义在structstkNode中，如定义为全局性就简单了 S.Push(w); p=p->leftChild; } intcontinue1=1; while(continue1&&!S.IsEmpty()){ S.Pop(w);p=w.ptr; switch(w.tag){ //判断栈顶的tag标记 casestkNode<T>::L:w.tag=stkNode<T>::R; S.Push(w); continue1=0; p=p->rightChild;break; casestkNode<T>::R:visit(p);break; } }}while(!S.IsEmpty()); //继续遍历其他结点cout<<endl;}template<typenameT>voidBinaryTree<T>::levelOrder(void(*visit)(BinTreeNode<T>*t)){//层次序遍历if(root==NULL)return;LinkedQueue<BinTreeNode<T>*>Q;BinTreeNode<T>*p=root;visit(p);Q.EnQueue(p); while(!Q.IsEmpty()){Q.DeQueue(p);if(p->leftChild!=NULL){ visit(p->leftChild); Q.EnQueue(p->leftChild);}if(p->rightChild!=NULL){ visit(p->rightChild); Q.EnQueue(p->rightChild);}}}#include<iostream>#include<cassert>usingnamespacestd;template<typenameT>structLinkNode{ Tdata; LinkNode<T>*link; LinkNode(LinkNode<T>*ptr=NULL){ link=ptr;