二叉树的递归非递归建立与非递归遍历.doc

/*二叉树的递归与非递归建立，非递归先序与后序的遍历*/*编程者：YDLZL */*本人比较笨,花了一晚上功夫才完全调试好了,为了让更多的人少花点时间,决定共享*/#include #define Maxsize 20typedef char datatype;typedef struct BTreeNode datatype data; struct BTreeNode *Lchild; struct BTreeNode *Rchild; BTree;/*先序递归建立二叉树 */BTree *CreatBTree() BTree *T; char ch; scanf(%c,&ch); getchar(); if(ch=#) T=NULL ; else T=(BTree *)malloc(sizeof(struct BTreeNode); T-data = ch; T-Lchild=CreatBTree(); /*构造左子树 */ T-Rchild=CreatBTree(); /*构造左子树 */ return T;/*/*先序非递归建立二叉树算法*/*/BTree *creatree(char *s) BTree *stackMaxsize,*p,*T,*q; int top=-1,k=0,j=0; char ch; ch=sj; T=(BTree *)malloc(sizeof(struct BTreeNode); T=NULL; while(ch!=#) switch(ch) case (:stack+top=p;k=1;break; case ): top-;break; case ,: k=2;break; default:p=(BTree *)malloc(sizeof(struct BTreeNode); p-data=ch;p-Lchild=p-Rchild=NULL; if(T=NULL) T=p; else switch(k) case 1:q=(BTree *)malloc(sizeof(struct BTreeNode);q=stacktop;q-Lchild=p;break; case 2:q=(BTree *)malloc(sizeof(struct BTreeNode);q=stacktop;q-Rchild=p;break; j+; ch=sj; return T;/*先序非递归遍历算法*/PreOrder(BTree *T) BTree *p; BTree stackMaxsize; int top=0; p=T; /*stack empty,over*/ while(p!=NULL | top!=0) while(p!=NULL) printf(%c, p-data); stacktop+=*p; p=p-Lchild; if (top!=0) *p=stack-top; p=p-Rchild; /*/*后序遍历的非递归算法 */*/PostOrder(BTree *T) BTree *p,*q; BTree stackMaxsize; char flag; int top=0; p=T; /*q=(BTree *)malloc(sizeof(struct BTreeNode); */ q=NULL; while (p|top!=0) if(p!=q) while(p) top+; stacktop=*p; if(p-Lchild)p=p-Lchild;else p=p-Rchild; if (top=0)break; *q=stacktop; if(q-Rchild=p) *p=stacktop;top-; printf(%c,p-data); p=q; flag= p-data; else p=q-Rchild; if (flag= p-data) *p=stacktop;top-; printf(%c,p-data); p=q; flag= p-data; main() BTree *T; char *s; /* T= CreatBTree();*/ printf(input a tree-string n); scanf(%s,s); T=creatree(s); PreO