用非递归算法遍历二叉树.docVIP

用非递归算法遍历二叉树 #includestdio.h #define NULL 0 #define max 40 int counter=0; typedef struct btreenode {int data; struct btreenode *lchild; struct btreenode *rchild; }bnode; int stack[max],top=0; bnode *creat(int x,bnode *lbt,bnode *rbt) {bnode *p; p=(bnode*)malloc(sizeof(bnode)); p-data=x; p-lchild=lbt; p-rchild=rbt; return(p); } bnode *ins_lchild(bnode *p,int x) {bnode *q; if(p==NULL) ? printf(Illegal insert.); else {q=(bnode*)malloc(sizeof(bnode)); ? q-data=x; ? q-lchild=NULL; ? q-rchild=NULL; ? if(p-lchild!=NULL) ? q-rchild=p-lchild; ? p-lchild=q; } } bnode *ins_rchild(bnode *p,int x) {bnode *q; if(p==NULL) printf(Illegal insert); else ? {q=(bnode*)malloc(sizeof(bnode)); ? q-data=x; ? q-lchild=NULL; ? q-rchild=NULL; ? if(p-rchild!=NULL) ? q-lchild=p-rchild; ? p-rchild=q; ? } } void prorder(bnode *p) {if(p==NULL) return; printf(%d\t%u\t%d\t%u\t%u\n,++counter,p,p-data,p-lchild,p-rchild); if(p-lchild!=NULL) ? prorder(p-lchild); if(p-rchild!=NULL) ? prorder(p-rchild); } void preorder(bnode *p) {printf(\npreorder travel:\n); while(!(p==NULLtop==NULL)) {if(p!=NULL) ? {printf(%d,p-data); ? push(p); ? p=p-lchild; ? } ? else ? {p=(bnode *)pop(); ? p=p-rchild; ? } } } void inorder(bnode *p) {printf(\ninorder travel\n); while(!(p==NULLtop==NULL)) {while(p!=NULL) ? {push(p); ? p=p-lchild; ? } ? p=(bnode*)pop(); ? printf(%d,p-data); ? p=p-rchild; } } void postorder(bnode *root) {bnode *p=root; unsigned sign; printf(\npostorder travel:\n); do {if(p!=NULL) {push(p); ? push(1); ? p=p-lchild; ? } else while(top!=NULL) ? {sign=pop(); ? p=(bnode*)pop(); ? if(sign==1) ? {push(p); ? ? push(2); ? ? p=p-rchild; ? ? break; ? ? } ? else ? if(sign==2) ? ? {printf(%d,p-data); ? ? p=NULL; ? ? } ? } ? } while(p!=NULL||top!=NULL); } push(s) { top++; ? stack[top]=s; ? } pop() {top--; return(stack[top+1]); } main() {bnode *bt,*p,*q; int x; printf(input root:); scanf(%d,x); p=creat(x,NULL,NULL); bt=p; scanf(%d,x); while(x!=-1) {p=bt; q=p; while(x!=p-dataq!=NULL) ? {p=q; ? if(xp-data) ? ? q=p-lchild;