欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 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);

}