二叉树遍历 前序遍历 后序遍历 中序遍历 非递归前序遍历

#include<iostream>

using namespace std;

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);

PreOrderVisit2(T);

MidOrderVisit2(T);

LastOrderVisit2(T);

}