推荐回答
#include"stdio.h"#include"stdlib.h"#defineSTACK_INIT_SIZE10//栈的初始长度#defineSTACKINCREMENT5//栈的追加长度typedefstructbitree{chardata;structbitree*lchild,*rchild;}bitree;//二叉树结点定义typedefstruct{bitree**base;bitree**top;intstacksize;}sqstack;//链栈结点定义top栈顶base栈底且栈元素是指向二叉树结点的二级指针//建立一个空栈intinitstacksqstack*s{s->base=bitree*mallocSTACK_INIT_SIZE*sizeofbitree;//栈底指向开辟空间if!s->baseexit1;//抛出异常s->top=s->base;//栈顶=栈尾表示栈空s->stacksize=STACK_INIT_SIZE;//栈长度为开辟空间大小return1;}//进栈intpushsqstack*s,bitree*e{ifs->top-s->base>=s->stacksize//如果栈满追加开辟空间{s->base=bitree*reallocs->base,s->stacksize+STACKINCREMENT*sizeofbitree;if!s->baseexit1;//抛出异常s->top=s->base+s->stacksize;//感觉这一句没用s->stacksize+=STACKINCREMENT;}*s->top=e;s->top++;//进栈栈顶后移return1;}//出栈intpopsqstack*s,bitree**e{ifs->top==s->basereturn0;//栈空返回0--s->top;*e=*s->top;//栈顶前移取出栈顶元素给ereturn1;}//取栈顶intgettopsqstack*s,bitree**e//去栈顶元素注意top指向的是栈顶的后一个{ifs->top==s->basereturn0;//所以s->top-1*e=*s->top-1;return1;}/*------------------------非递归-----先序建立二叉树----------------------------------*/bitree*createprebitree{charch;bitree*ht,*p,*q;sqstack*s;s=mallocsizeofbitree;//加上这一句为s初始化开辟空间ch=getchar;ifch!=''#''&&ch!=''''/*输入二叉树先序顺序是以完全二叉树的先序顺序不是完全二叉树的把没有的结点以#表示*/{ht=bitree*mallocsizeofbitree;ht->data=ch;ht->lchild=ht->rchild=NULL;p=ht;initstacks;pushs,ht;//根节点进栈whilech=getchar!=''''//算{ifch!=''#''{q=bitree*mallocsizeofbitree;//法q->data=ch;//ifp==*s->top-1p->lchild=q;//核elsep->rchild=q;//pushs,q;p=q;//心}//else{ifp==*s->top-1p->lchild=NULL;//的elsep->rchild=NULL;//pops,&p;}//步//}//骤returnht;}elsereturnNULL;}/*--------------------------递归---------先序建立二叉树-------------------------------*/voidCreateBiTreebitree**T{//按先序次序输入二叉树中的结点的值，空格字符表示空树，//构造二叉链表表示二叉树charch;scanf"%c",&ch;ifch==''#''*T=NULL;else{*T=bitree*mallocsizeofbitree;if!*Texit1;*T->data=ch;//生成根结点CreateBiTree&*T->lchild;//构造左子树CreateBiTree&*T->rchild;//构造右子树}}/*--------------------------非递归-------中序建立二叉树-------------------------------*//*--------------------------递归---------中序建立二叉树-------------------------------*//*--------------------------非递归-------后序建立二叉树-------------------------------*//*--------------------------递归---------后序建立二叉树-------------------------------*//*-----------------------非递归------先序输出二叉树------------------------------*/voidpreordertraversebitree*h{sqstackm;initstack&m;whileh||m.base!=m.top{ifh{push&m,h;printf"%c",h->data;h=h->lchild;}else{pop&m,&h;h=h->rchild;}}}/*------------------------非递归-----中序输出二叉树----------------------------*/voidinordertraversebitree*h{sqstackm;initstack&m;whileh||m.base!=m.top{ifh{push&m,h;h=h->lchild;}else{pop&m,&h;printf"%c",h->data;h=h->rchild;}}}/*---------------------非递归----后序遍历二叉树----------------------------------*/voidpostordertraversebitree*h{sqstackm;initstack&m;whileh||m.base!=m.top{ifh{push&m,h;h=h->lchild;}else{bitree*r;//使用r结点表示访问了右子树代替标志域gettop&m,&h;ifh->rchild&&h->rchild!=r{h=h->rchild;push&m,h;h=h->lchild;}else{pop&m,&h;printf"%c",h->data;r=h;h=NULL;}}}}//层次遍历二叉树用队列哈哈以后做/*-------------------------------主过程-------------------------------*/intmain{bitree*ht;printf"先序非递归建立一个二叉树:";ifht=createprebitree!=NULL//非递归建立//CreateBiTree&ht;//ifht!=NULL//递归建立{printf"先序遍历输出二叉树:";preordertraverseht;putchar'''';printf"中序遍历输出二叉树:";inordertraverseht;putchar'''';printf"后序遍历输出二叉树:";postordertraverseht;putchar'''';}elseprintf"空二叉树";}这是先序递归和非递归建立二叉树和先、中、后的遍历输出。
梅金香2019-12-21 18:42:12
提示您：回答为网友贡献，仅供参考。