二叉树遍历 前序遍历 后序遍历 中序遍历 非递归前序遍历 二叉树遍历非递归
程序员文章站
2022-07-10 10:16:56
...
#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);
}
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);
}
上一篇: java 二叉树遍历
下一篇: 二叉树的遍历