#include<iostream>
using namespace std;
/**
二叉树的遍历:前序,后序,中序
二叉树的非递归遍历:前序,后序,中序
参考文献:http://topic.csdn.net/t/20060802/17/4922659.html
***/
typedef struct BiTNode
{
char data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
int CreateBiTree(BiTree &T)
{
char ch;
cin.get(ch);
if(ch == ' ')
T = NULL;
else
{
if(!(T = (BiTNode*)malloc(sizeof(BiTNode))))
exit(0);
T->data = ch;
CreateBiTree(T->lchild);
CreateBiTree(T->rchild);
}
return 1;
}
int PreOrderVisit(BiTree &T)
{
if(T)
{
cout<<T->data<<endl;
PreOrderVisit(T->lchild);
PreOrderVisit(T->rchild);
return 1;
}else
return 1;
}
int MidOrderVisit(BiTree &T)
{
if(T)
{
MidOrderVisit(T->lchild);
cout<<T->data;
MidOrderVisit(T->rchild);
return 1;
}
else
return 1;
}
int LastOrderVisit(BiTree &T)
{
if(T)
{
LastOrderVisit(T->lchild);
LastOrderVisit(T->rchild);
cout<<T->data;
}
else
return 1;
}
//先序遍历二叉树:非递归
int PreOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归前序遍历树:"<<endl;
BiTree stack[100] ;
int top = -1;
while(T||top>-1)
{
while(T)
{
cout<<T->data<<" ";
stack[++top] = T;
T = T->lchild;
}
if(top>-1)
{
T = stack[top--];
T = T->rchild;
}
}
T = temp;
cout<<endl;
return 1;
}
//中序遍历二叉树:非递归
int MidOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归中序遍历树:"<<endl;
BiTree stack[100] ;
int top = -1;
while(T||top>-1)
{
while(T)
{
stack[++top] = T;
T = T->lchild;
}
if(top>-1)
{
T = stack[top--];
cout<<T->data<<" ";
T = T->rchild;
}
}
cout<<endl;
T = temp;
return 1;
}
//后序遍历二叉树:非递归
int LastOrderVisit2(BiTree &T)
{
BiTree temp = T;
cout<<"非递归后序遍历树:"<<endl;
BiTree stack[100] ;
int tag[100];
int top = -1;
while(T||top>-1)
{
while(T)
{
int pointer = ++top;
stack[pointer] = T;
tag[pointer] = 0;
T = T->lchild;
}
while(top>-1&&tag[top]==1)
{
T = stack[top--];
cout<<T->data<<" ";
}
if(top>-1)
{
tag[top] = 1;
T = stack[top];
T = T->rchild;
}else
break;
}
cout<<endl;
T = temp;
return 1;
}
int main()
{
BiTree T;
//例如:
// abc空格空格de空格g空格空格f空格空格空格
cout<<"创建树:输入数据,Enter键结束:"<<endl;
CreateBiTree(T);
/* cout<<"前序遍历树:"<<endl;
PreOrderVisit(T);
cout<<"中序遍历树:"<<endl;
MidOrderVisit(T);
cout<<"后序遍历树:"<<endl;
LastOrderVisit(T);*/
PreOrderVisit2(T);
MidOrderVisit2(T);
LastOrderVisit2(T);
}
分享到:
相关推荐
用C++写的二叉树先序遍历、中序遍历和后序遍历非递归算法
二叉树遍历问题 二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序, 中序, 后序二叉树遍历问题-前序...
用c语言写的遍历二叉树 包括前序,中序,后序
二叉树的遍历,全部用递归实现,很有规律! 二叉树的遍历,全部用递归实现,很有规律
二叉树的递归遍历,中序遍历,先序遍历,后序遍历,通过学习二叉树的遍历,可以让我们更紧一步掌握数据的遍历
栈的应用——二叉树的前序、中序、后序非递归遍历算法
C语言二叉树遍历前序非递归算法,简单易懂,正确无误
java实现 二叉树的遍历 前序遍历用到递归, 中序和后序遍历用到栈, 其实还是有一定难度的
常见的二叉树遍历,分为前序、中序、后续和层次遍历4种。 层次遍历相对比较好理解,对于前3种遍历方式概念的记忆方式应该是这样的:左和右的顺序始终是固定的—先左后右,所谓的前序、中序和后序是针对根来说的。...
用C++写的,包括二叉树的构建,二叉树的先序遍历、中序遍历和后序遍历非递归算法。
二叉树 遍历 前序 后序 c 语言 源代码
已知二叉树的中序和先序遍历可以唯一确定后序遍历、已知中序和后序遍历可以唯一确定先序遍历,但已知先序和后序,却不一定能唯一确定中序遍历。现要求根据输入的中序遍历结果及先序遍历结果,要求输出其后序遍历结果...
关于二叉树前序和后序的非递归遍历算法.rar
链式二叉树的后序创建、递归后序遍历、非递归堆栈后序遍历、后序销毁
二叉树的遍历,前序遍历 中序遍历 后序遍历
c++代码,能够根据前序序列、中序序列生成二叉树;能够一步生成,也可以一步步自动生成。 设计前序遍历,中序遍历,后序遍历,层次遍历;
二叉树的基本操作,包括前序、中序、后序遍历的递归和非递归算法,不得不下的资源
二叉树先序、中序、后序遍历非递归算法,简述了二叉树的基本算法。
对二叉树进行前序、中序、后序的遍历,解释完整,代码完好无缺,对二叉树进行全方位的遍历
二叉树前序、中序、后序三种遍历的非递归算法(C语言)