非递归遍历树
先序非递归遍历二叉树，中序非递归遍历二叉树，后序非递归遍历二叉树及双栈法。
先序非递归遍历二叉树
先序非递归遍历比较简单，感觉与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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-10-19|，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录