#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
#define ElemType char
//二叉树的定义
typedef struct BiTree
{
ElemType data;
struct BiTree *lChild; //左孩子
struct BiTree *rChild; //右孩子
}BiTree,*Tree;
//堆栈的定义
typedef struct TreeStack
{
BiTree *stack[50];
int top;
}TreeStack;
//初始化堆栈,返回值为指向一个堆栈的指针
TreeStack* InitStack()
{
TreeStack *TS;
TS=(TreeStack*)malloc(sizeof(TreeStack));
TS->top=-1;
TS->stack[TS->top]=NULL;//初始化为空
return TS;
}
//入栈
void push(TreeStack *TStack,BiTree *p)
{
if(TStack->top>=-1) //堆栈不为空,将地址入栈
TStack->stack[++(TStack->top)]=p;
else
exit(1);
}
//出栈
BiTree* pop(TreeStack *TStack)
{
if(TStack->top>=0) { //堆栈不为空,出栈
return TStack->stack[TStack->top--];
// TStack->top--;
}
else
exit(1);
}
BiTree *GetTop(TreeStack *S)
{
return S->stack[S->top];
}
int FirstCreateT(Tree &T) //先序序列建立二叉树,如果成功返回1,失败返回0
{
char ch;
scanf("%c",&ch);
if(ch=='#')
T=NULL;
else
{
T=(Tree)malloc(sizeof(BiTree));
if(T!=NULL)
T->data=ch;
else
return 0; //创建失败返回0
FirstCreateT(T->lChild);
FirstCreateT(T->rChild);
}
return 1;
}
int FirstOver(BiTree *T) //先序序列遍历二叉树
{
if(T==NULL)
return 0;
printf("%c",T->data);
FirstOver(T->lChild);
FirstOver(T->rChild);
return 1;
}
int MidOver(BiTree *T) //中序序列遍历二叉树
{
if(T==NULL)
return 0;
MidOver(T->lChild);
printf("%c",T->data);
MidOver(T->rChild);
return 1;
}
int LastOver(BiTree *T) //后序序列遍历二叉树
{
if(T==NULL)
return 0;
LastOver(T->lChild);
LastOver(T->rChild);
printf("%c",T->data);
return 1;
}
/*
int MidNoT(Tree T) //以非递归方式中序遍历建立二叉树
{
BiTree *temp;
TreeStack *TS;
TS=InitStack();
temp=T;
do{
if(NULL!=temp->lChild)
{
push(temp,TS);
temp=temp->lChild;
}
if(NULL==temp->lChild)
{
printf("%c",temp->data);
if(NULL==temp->rChild)//右子树为空
temp=pop(TS);
if(NULL!=temp->rChild)
{
push(temp,TS);
temp=temp->rChild;
}
}
}while(TS->top>=0);
return 1;
}
*///错误方式
int LastOrderTravel(BiTree *T)
{
int flag=0;
BiTree *p,*temp;
p=T;
TreeStack *S;
S=InitStack();
while(p!=NULL||-1!=S->top)
{
if(NULL!=p&&flag==0)
{
push(S,p);
p=p->lChild;
}
else
{
p=GetTop(S);
if(NULL==p->rChild)
{
//pop(S,p);
p=pop(S);
temp=GetTop(S);
if(temp!=NULL){ //出于最后一个节点的考虑
if(p==temp->rChild)
flag=2; //从右边返回
else
flag=1;
}
printf("%c",p->data);
p=GetTop(S);
continue;
}
if((flag!=2)&&p->rChild!=NULL)
{
p=p->rChild;
flag=0;
}
if((flag==1&&p->rChild==NULL)||flag==2)
{
//pop(S,p);
p=pop(S);
temp=GetTop(S);//刚开始掉了 //最后一个节点他没前前驱爱爱爱
if(temp!=NULL){
if(p==temp->rChild)
flag=2; //从右边返回
else
flag=1;
}
printf("%c",p->data);
p=GetTop(S);
}
}
}
return 1;//成功返回1
}
int FirstOrderTravel(BiTree *T)
{
BiTree *p;
p=T;
TreeStack *S;
S=InitStack();
while (NULL!=p||-1!=S->top)
{
if(NULL!=p->rChild)
push(S,p->rChild);
if(NULL!=p)
{
printf("%c",p->data);
p=p->lChild;
}
if(NULL==p&&-1!=S->top)
p=pop(S);
}
return 1;
}
int MidOrderTravel(BiTree *T)
{
BiTree *p;
p=T;
TreeStack *S;
S=InitStack();
while(p||-1!=S->top)
{
if(p){push(S,p);p=p->lChild;}
else{
p=pop(S);
printf("%c",p->data);
p=p->rChild;
}
}
return 1;
}
void main()
{
Tree apple;
printf("请按照先序序列输入二叉树:");
FirstCreateT(apple);
printf("1.先序序列输出二叉树:");
FirstOver(apple);
printf("\n");
printf("2.非递归先序序列输出二叉树:");
FirstOrderTravel(apple);
printf("\n\n");
printf("1.中序序列输出二叉树:");
MidOver(apple);
printf("\n");
printf("2.非递归先序序列输出二叉树:");
MidOrderTravel(apple);
printf("\n\n");
printf("1.后序序列输出二叉树:");
LastOver(apple);
printf("\n");
printf("2.非递归先序序列输出二叉树:");
LastOrderTravel(apple);
printf("\n");
//2013年8月12日 23:30:49终于完成,感触良多哇
//测试用例:ABD##EG##H##C#F#Z##
//思路要正确,写程序前要想好各种可能性,不然调试时候发现思维漏洞很难受,最好开始就想好
//if。。。else if()如果前面那个正确了,后面那个编译器是不会判断正确如否的,要注意还有好多暂时没想到
// MidNoT(apple);
}