自己编写的实验二叉树的后序遍历非递归算法c语言实现

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