二叉树中序遍历递归和非递归的c++实现

二叉树的非递归遍历是由以下这个发现产生的：先序，中序，后序遍历过程经过的路线一样，只是访问各结点的时机不同，先序在第一次经过结点时就访问该结点，中序则是第二次。访问结点即是输出该结点，所以只要把该路线表述出来，三种遍历方式只不过是把输出语句放在哪里的问题。重点是如何把下图所示的路线实现出来二叉树中序遍历递归和非递归的c++实现

由于在访问过程中需要先经过一个结点，再在随后的路线中经过，可以用堆栈来表示行走路线

二叉树中序遍历递归和非递归的c++实现

用进栈表示第一次访问一个结点，出栈表示第二次访问一个结点，而行走路线则通过改变指针来实现。

为此，需要建立堆栈和二叉树两种数据结构，并给出出栈，入栈操作的实现。并写出二叉树的创建这个函数，最后就可以集中精力来实现二叉树的非递归中序遍历

/*二叉树中序遍历的递归和非递归算法*/

#include<iostream>
using namespace std;
#define maxsize 100/*定义堆栈最大容量*/
typedef struct TNode *BTree;/*定义间接访问二叉树结点的指针*/
struct TNode{
char Data;
BTree leftchild;
BTree rightchild;
};/*定义二叉树结点*/
typedef BTree ElementType;/*ElementType与BTree等同*/
typedef struct SNode *Stack;/*定义间接访问对战的指针*/
struct SNode{
ElementType Data[maxsize];
int top;
};/*定义用数组表示的堆栈数据结构*/
/*创建一个空堆栈*/
Stack CreateEmptyStack(){
Stack PtrS;
PtrS=(Stack)malloc(sizeof(struct SNode));/*定义堆栈并分配内存*/
PtrS->top=-1;/*初始化*/
return PtrS;
}
/*进栈*/
void EnterStack(ElementType x,Stack *PtrS){
if((*PtrS)->top==maxsize-1){
cout<<"full"<<endl;
return;
}/*栈满无法进入*/
(*PtrS)->Data[++((*PtrS)->top)]=x;
return;
}
/*判断栈是否为空*/
int IsStackEmpty(Stack PtrS){
if(PtrS->top==-1) return 0;/*空返回0*/
else return 1;/*不空返回1*/
}
/*出栈*/
ElementType OutStack(Stack *PtrS){
if((*PtrS)->top==-1){
cout<<"empty"<<endl;
return NULL;
}/*栈空则显示empty*/
return (*PtrS)->Data[((*PtrS)->top)--];
}
/*先序递归创建二叉树，对一棵二叉树，用#来替代每个结点缺失的孩子，然后先序遍历新的二叉树，即可保存该二叉树*/
void CreateBTree(BTree *PtrT){
char n;
cin>>n;/*输入二叉树*/
if(n=='#') (*PtrT)=NULL;/*递归边界条件*/
else{
(*PtrT)=(BTree)malloc(sizeof(struct TNode));/*为该结点分配空间*/
(*PtrT)->Data=n;/*为结点赋值*/
CreateBTree(&(*PtrT)->leftchild);
CreateBTree(&(*PtrT)->rightchild);/*递归创建左右子树*/
}
}
/*中序递归遍历二叉树*/
void RecursionInorder(BTree PtrT){
if(PtrT){
RecursionInorder(PtrT->leftchild);
cout<<PtrT->Data<<endl;/*输出即表示访问该结点*/
RecursionInorder(PtrT->rightchild);
}
}
/*中序非递归遍历二叉树*/
void NorecursionoInorder(BTree T){
Stack S;
S=CreateEmptyStack();/*创建一个栈*/
while(IsStackEmpty(S)||T){/*栈不空或者树中结点第一次访问未结束*/
while(T)
{
EnterStack(T,&S);/*压入栈*/

T=T->leftchild;/*一路向左*/

}
if(IsStackEmpty(S)){
T=OutStack(&S);/*出栈*/
cout<<T->Data<<endl;/*此时第二次访问栈顶结点，输出*/
T=T->rightchild;/*向右走*/
}
}
return;
}
int main(){
BTree Tree;
CreateBTree(&Tree);/*建立一棵二叉树*/
RecursionInorder(Tree);/*中序非递归遍历二叉树*/
NorecursionoInorder(Tree);/*中序非递归遍历二叉树*/
return 0;
}

二叉树中序遍历递归和非递归的c++实现

相关推荐