资源描述：
《用非递归算法遍历二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、用非递归算法遍历二叉树#include#defineNULL0#definemax40intcounter=0;typedefstructbtreenode{intdata;structbtreenode*lchild;structbtreenode*rchild;}bnode;intstack[max],top=0;bnode*creat(intx,bnode*lbt,bnode*rbt){bnode*p;p=(bnode*)malloc(sizeof(bnode));p->data=x;p->lchild=lbt;p->r
2、child=rbt;return(p);}bnode*ins_lchild(bnode*p,intx){bnode*q;if(p==NULL) printf("Illegalinsert.");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,intx){bnode*q;if(
3、p==NULL)printf("Illegalinsert");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; }}voidprorder(bnode*p){if(p==NULL)return;printf("%dt%ut%dt%ut%u",++counter,p,p->data,p->lchild,p->rch
4、ild);if(p->lchild!=NULL) prorder(p->lchild);if(p->rchild!=NULL) prorder(p->rchild);}voidpreorder(bnode*p){printf("preordertravel:");while(!(p==NULL&&top==NULL)){if(p!=NULL) {printf("%d",p->data); push(p); p=p->lchild; } else {p=(bnode*)pop(); p=p->rchild; }}}voidinorder(
5、bnode*p){printf("inordertravel");while(!(p==NULL&&top==NULL)){while(p!=NULL) {push(p); p=p->lchild; } p=(bnode*)pop(); printf("%d",p->data); p=p->rchild;}}voidpostorder(bnode*root){bnode*p=root;unsignedsign;printf("postordertravel:");do{if(p!=NULL){push(p); push(1);
6、p=p->lchild; }elsewhile(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
7、
8、top!=NULL);}push(s){top++; stack[top]=s; }pop(){top--;return(stack[top+1]);}main()
9、{bnode*bt,*p,*q;intx;printf("inputroot:");scanf("%d",&x);p=creat(x,NULL,NULL);bt=p;scanf("%d",&x);while(x!=-1){p=bt;q=p;while(x!=p->data&&q!=NULL) {p=q; if(xdata) q=p->lchild; else q=p->rchild;}if(x==p->data){printf("thedataisexit:"); return; }elseif(xdata) ins_lch
10、ild(p,x);else ins_rchild(p,x);scanf("%d",&x);}p=bt;printf("structureofthebi
