后根递归和非递归遍历二叉树.cpp

用后根递归和非递归两种不同的方法来遍历二叉树。

#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef int ElemType;
typedef struct BNode      /*二叉树结点结构*/
{ElemType data;
 struct BNode *lch,*rch;
}BNode;
typedef struct    /*栈的顺序存储结构，服务于中序非递归遍历*/
{BNode *a[MAXSIZE];
 int top;
}sqstack;
BNode *creat_bt();
void preorder(BNode *p);
void postorder(BNode *p);
void postorderz(BNode *t);
BNode *s[10];int s2[20];
BNode *t,*p,*q;int z,i,j,k,e,x;
void main()
{
do
{printf("\n\n");
printf("\n\n  1.建立二叉树 ");
printf("\n\n  2.后序递归遍历二叉树  ");
printf("\n\n  3.后序非递归遍历二叉树  ");
printf("\n\n  4.结束程序运行  ");
printf("\n===================================");
printf("\n   请输入您的选择（1，2，3，4）：");scanf("%d",&k);
switch(k)
{case 1:{printf("\n s输入（00）结束:");
          t=creat_bt();
		  preorder(t);
}break;

case 2:{printf("\n 后根递归遍历 postorder:");postorder(t);
	   }break;
case 3:{printf("\n 后根非递归遍历 postorderz:");postorderz(t);
	   }break;
case 4:exit(0);
	   }
       printf("\n----------------");
    }while(k>=1&&k<4);
  printf("\n            再见！");scanf("%d",&z);
}/*main*/
BNode *creat_bt()   /*利用二叉树性质5，借助一维数组V建立二叉树*/
{BNode *t,*p,*v[20];
printf("\n i data=?");scanf("%d%d",&i,&e);
while(i!=0&&e!=0)
{p=(BNode *)malloc(sizeof(BNode));
 p->data=e;;p->lch=NULL;p->rch=NULL;
 v[i]=p;
 if(i==1)t=p;
 else{j=i/2;
  if(i%2==0)v[j]->lch=p; else v[j]->rch=p;
 }
 printf("\n i data=?");scanf("%d%d",&i,&e);
}
return(t);
}/*creat_bt*/

void preorder(BNode *p)
{if(p){ printf("%3d",p->data);
 preorder(p->lch);
 preorder(p->rch);
}
}/*preorder*/

void postorder(BNode *p)
{if(p!=NULL){postorder(p->lch);
             postorder(p->rch);
       printf("%6d",p->data);
	   
}
}/*postorder*/
void postorderz(BNode *p)
{q=p;int top=0;int x=1;
  printf("\n 后根遍历:\n");
	  do{while(q!=NULL){top++; s[top]=q;
	                     s2[top]=1; 
						 q=q->lch;
	  }
	  if(top==0) x=0;
	     else{if(s2[top]==1){s2[top]=2;
		                    q=s[top];q=q->rch;
		 }
		 else {q=s[top];
		        s2[top]=0;top--;
				printf("%6d",q->data);
				q=NULL;
		 }
		 }
	  }while (x);
	printf("\n");
}/*postorderz*/