资源描述：
《二叉树中以广义表-(先序-中序后序)递归-中序非递归输出.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、#include#include#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineOVERFLOW-2#defineOK1#defineERROR-1#defineTRUE1#defineFALSE0typedefcharTElemType;typedefintStatus;typedefstructBiTNode{//二叉链表储存结构TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;StatusCreateBiTre
2、e(BiTree&T){//先序序列建立二叉树charch;scanf("%c",&ch);if(ch=='#')T=NULL;else{if(!(T=(BiTNode*)malloc(sizeof(BiTNode))))return(OVERFLOW);T->data=ch;CreateBiTree(T->lchild);CreateBiTree(T->rchild);}returnOK;}voidPrintBiTree(BiTree&T){//以广义表的形式输出if(T!=NULL){printf("%c",T->data);if(T->lchild!=NULL
3、
4、T->rchi
5、ld!=NULL){printf("(");PrintBiTree(T->lchild);if(T->rchild!=NULL){printf(",");}PrintBiTree(T->rchild);printf(")");}}}StatusPrintElement(TElemTypee){//访问函数printf("%c",e);returnOK;}StatusPreOrderTraverse(BiTreeT,Status(*Visit)(TElemTypee)){//先序遍历二叉树的递归算法if(T){if(Visit(T->data))//printf("(");if(Pre
6、OrderTraverse(T->lchild,Visit))//printf(",");if(PreOrderTraverse(T->rchild,Visit))//printf(")");returnOK;returnERROR;}elsereturnOK;}StatusInOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){//中序遍历二叉树的递归算法if(T){if(InOrderTraverse(T->lchild,Visit))if(Visit(T->data))if(InOrderTraverse(T->rchild,Vis
7、it))returnOK;returnERROR;}elsereturnOK;}StatusPostOrderTraverse(BiTreeT,Status(*Visit)(TElemType)){//后序遍历二叉树的递归算法if(T){if(PostOrderTraverse(T->lchild,Visit))if(PostOrderTraverse(T->rchild,Visit))if(Visit(T->data))returnOK;returnERROR;}elsereturnOK;}//中序遍历二叉树的非递归算法typedefstruct{//栈存储结构及操作BiTree*
8、base;BiTree*top;intstacksize;}Stack;StatusInitStack(Stack&S){//构造空栈S.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!S.base)exit(OVERFLOW);S.top=S.base;S.stacksize=STACK_INIT_SIZE;returnOK;}StatusGetTop(StackS,BiTree&e){//读栈顶元素if(S.top==S.base)returnERROR;e=*(S.top-1);returnOK;}StatusP
9、ush(Stack&S,BiTreee){//入栈if(S.top-S.base>=S.stacksize){S.base=(BiTree*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!S.base)exit(OVERFLOW);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;returnOK
