先序非递归遍历二叉树,中序非递归遍历二叉树,后序非递归遍历二叉树及双栈法。
先序非递归遍历比较简单,感觉与DFS类似,根据先序遍历的规则根左右,先将根节点压入栈,然后遍历左子树,再遍历左子树的左子树,一头走到NULL,把每次遍历的左子树的根节点依次入栈并把当前结点数据打印出来。最后为NULL,开始回溯,返回到前一结点(也就是当前结点的根节点),开始遍历右子树。依次类推。
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<iostream>
using namespace std;
struct TNode
{
int data;
TNode * rchild,*lchild;
};
int a[1000],b[1000];
int n;
//先序+中序构造二叉树
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
for(int i =0;i < n ; ++i)
{
if(a[0]==b[i])
{
T = (TNode *)malloc(sizeof(TNode));
T->data = b[i];
T->lchild = Creat(a+1,b,i);
T->rchild = Creat(a+i+1,b+i+1,n-i-1);
return T;
}
}
return NULL;
}
//先序非递归遍历
void travel_pre(TNode * T)
{
if(T==NULL)
return;
stack<TNode *> s;
TNode * p = T;
while(p!=NULL||!s.empty())
{
if(p!=NULL)
{
s.push(p);
cout<<p->data<<" ";
p = p->lchild;
}
else
{
p = s.top();
s.pop();
p = p->rchild;
}
}
}
int main()
{
TNode * Tree;
int n;
while(~scanf("%d",&n))
{
Tree = NULL;
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_pre(Tree);
}
return 0;
}
//测试样例
//输入前三行
//9
//1 2 4 7 3 5 8 9 6 //先序
//4 7 2 1 8 5 9 3 6 // 中序
//7 4 2 8 9 5 6 3 1 // 后序
仔细看代码你会发现,先序遍历和中序遍历代码差不多,关键在于打印节点数据的位置不一样。中序和先序遍历一样,从左子树一直走到NULL,当前结点为NULL时,开始从栈中弹出栈顶元素,并把栈顶元素的数据打印出来,然后遍历右结点,因为当前结点是叶节点,没有右孩子,所以再把栈顶元素弹出,并打印出来,此时当前结点为最左叶节点的根节点,然后遍历右节点,以此类推最后栈为空,遍历完毕。
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<iostream>
using namespace std;
struct TNode
{
int data;
TNode * rchild,*lchild;
};
int a[1000],b[1000];
int n;
//先序+中序构造二叉树
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
for(int i =0;i < n ; ++i)
{
if(a[0]==b[i])
{
T = (TNode *)malloc(sizeof(TNode));
T->data = b[i];
T->lchild = Creat(a+1,b,i);
T->rchild = Creat(a+i+1,b+i+1,n-i-1);
return T;
}
}
return NULL;
}
//中序遍历非递归
void travel_in(TNode * T)
{
if(T==NULL)
return;
stack<TNode *> s;
TNode * p = T;
while(p!=NULL||!s.empty())
{
if(p!=NULL)
{
s.push(p);
p = p->lchild;
}
else
{
p = s.top();
cout<<p->data<<" ";
s.pop();
p = p->rchild;
}
}
}
int main()
{
TNode * Tree;
int n;
while(~scanf("%d",&n))
{
Tree = NULL;
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_in(Tree);
}
return 0;
}
后序非递归遍历和先序中序非递归开始类似,先将左子树的左孩子的的左孩子的….每个节点压入栈。不同的是,后序遍历是走有根,有先后顺序,所以要定义一个结点变量,来记录当前结点是否被访问够。当节点为NULL时,取栈顶元素,如果当前结点的右孩子为空或者被访问过才把当前结点(根节点)打印,并作被访问记录。否则,对当前结点的右孩子遍历。
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<iostream>
using namespace std;
struct TNode
{
int data;
TNode * rchild,*lchild;
};
int a[1000],b[1000];
int n;
//先序+中序构建二叉树
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
for(int i =0;i < n ; ++i)
{
if(a[0]==b[i])
{
T = (TNode *)malloc(sizeof(TNode));
T->data = b[i];
T->lchild = Creat(a+1,b,i);
T->rchild = Creat(a+i+1,b+i+1,n-i-1);
return T;
}
}
return NULL;
}
//后序非递归
void travel_post(TNode *T)
{
stack<TNode *> s;
TNode * p = T;
TNode *visit = NULL;
while(p!=NULL||!s.empty())
{
while(p!=NULL)
{
s.push(p);
p = p->lchild;
}
p = s.top();
if(p->rchild==NULL||p->rchild==visit)
{
cout<<p->data<<" ";
visit = p;
s.pop();
p = NULL;
}
else
{
p = p->rchild;
}
}
}
int main()
{
TNode * Tree;
int n;
while(~scanf("%d",&n))
{
Tree = NULL;
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_post(Tree);
}
return 0;
}
首先将根节点p入栈1:
步骤一: 将栈1的栈顶元素赋给p,然后将p入栈2;然后先将p左结点入栈1,后将p右结点入栈1,顺序一定不能错。
步骤二:出栈2,就获得后序遍历
#include<stdio.h>
#include<stdlib.h>
#include<stack>
#include<iostream>
using namespace std;
struct TNode
{
int data;
TNode * rchild,*lchild;
};
int a[1000],b[1000];
int n;
TNode * Creat(int *a,int *b,int n)
{
TNode * T;
for(int i =0;i < n ; ++i)
{
if(a[0]==b[i])
{
T = (TNode *)malloc(sizeof(TNode));
T->data = b[i];
T->lchild = Creat(a+1,b,i);
T->rchild = Creat(a+i+1,b+i+1,n-i-1);
return T;
}
}
return NULL;
}
void travel_post(TNode *T)
{
stack<TNode *> s1;
stack<TNode *> s2;
TNode * p = T;
s1.push(p);
while(!s1.empty())
{
p = s1.top();
s1.pop();
s2.push(p);
if(p->lchild)
s1.push(p->lchild);
if(p->rchild)
s1.push(p->rchild);
}
while(!s2.empty())
{
cout<<s2.top()->data<<" ";
s2.pop();
}
}
int main()
{
TNode * Tree;
int n;
while(~scanf("%d",&n))
{
Tree = NULL;
for(int i =0;i<n;++i)
{
scanf("%d",&a[i]);
}
for(int i =0;i<n;++i)
{
scanf("%d",&b[i]);
}
Tree = Creat(a,b,n);
travel_post(Tree);
}
return 0;
}