#include <bits/stdc++.h>
using namespace std;
struct Tree{
int data;
bool tag;
Tree *lchild, *rchild;
};
Tree* CreatTree(){
Tree* root=new Tree;
cin>>root->data;
if(root->data==-1) root=NULL;
else{
root->lchild=CreatTree();
root->rchild=CreatTree();
}
return root;
}
void MidTreval(Tree *t){
stack<Tree*> s;
Tree *p=t;
while(p||!s.empty()){
if(p){
s.push(p);
p=p->lchild;
}
else{
p=s.top();
cout<<p->data<<' ';
s.pop();
p=p->rchild;
}
}
}
void PreTreval(Tree* t){
stack<Tree*> s;
Tree *p=t;
while(p||!s.empty()){
if(p){
cout<<p->data<<' ';
s.push(p);
p=p->lchild;
}
else{
p=s.top();
s.pop();
p=p->rchild;
}
}
}
void PostTreval(Tree *t){
stack<Tree*> s;
s.push(t);
Tree* p;
while(!s.empty()){
p=s.top();
if(p->lchild&&!p->lchild->tag) s.push(p->lchild);
else{
p->tag=1;
if(p->rchild&&!p->rchild->tag) s.push(p->rchild);
else{
cout<<p->data<<' ';
s.pop();
}
}
}
}
void LayerTreval(Tree *t){
queue<Tree*> q;
q.push(t);
while(!q.empty()){
Tree *p=q.front();
q.pop();
cout<<p->data<<' ';
if(p->lchild) q.push(p->lchild);
if(p->rchild) q.push(p->rchild);
}
}
int main(){
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
Tree* root=CreatTree();
LayerTreval(root);
return 0;
}
遍历二叉树的非递归写法
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
推荐阅读更多精彩内容
- 方法一：递归遍历 方法二：非递归遍历算法思想：使用栈。 内层循环用来存储节点，外层循环将内层循环的存储不断地转至节...
- 二叉树层次遍历 按照二叉树中的层次从左到右依次遍历每层中的结点。具体的实现思路是：通过使用队列的数据结构，从树的根...
- 一、生成二叉树 新建一个类： 生成二叉树方法： 生成二叉树： 二、前序遍历 前序遍历：访问顺序是【根节点】-【左孩...
