数据结构-二叉树的遍历(北华大学吕磊).doc

《数据结构-二叉树的遍历(北华大学吕磊).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、#include#include#include#defineOK1#defineERROR0#defineOVERFLOW-1#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE10typedefstructBiTNode{chardata;structBiTNode*lChild,*rChild;}BiTNode,*BiTree;typedefstructSqStack{BiTN

2、ode*base;BiTNode*top;intstacksize;}SqStack;//栈类型voidInitStack(SqStack*S)//创建栈{S->base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode));S->top=S->base;S->stacksize=STACK_INIT_SIZE;}intStackEmpty(SqStack*S)//判断栈是否非空{if(S->top==S->base)returnOK;elsereturnERROR;

3、}voidPush(SqStack*S,BiTNodee)//进栈{if(S->top-S->base>=S->stacksize){S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)=e;S->top++;}BiTNodePop(SqStack*S)//出栈{S->to

4、p--;return*S->top;}typedefBiTreeQElemType;//设栈元素为二叉树的指针类型typedefstruct{QElemType*base;intfront;//头指针,若队列不空,指向队列头元素intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置}SqQueue;intInitQueue(SqQueue*Q)//创建队列{(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)ex

5、it(OVERFLOW);(*Q).front=(*Q).rear=0;returnOK;}intQueueEmpty(SqQueueQ)//判断队列是否为空{if(Q.front==Q.rear)returnOK;elsereturnERROR;}intEnQueue(SqQueue*Q,QElemTypee)//插入元素e为Q的新的队尾元素{if(((*Q).rear+1)%MAXQSIZE==(*Q).front)returnERROR;(*Q).base[(*Q).rear]=e;(*Q).rear=((

6、*Q).rear+1)%MAXQSIZE;returnOK;}intDeQueue(SqQueue*Q,QElemType*e)//删除Q的队头元素,用e返回其值{if((*Q).front==(*Q).rear)returnERROR;*e=(*Q).base[(*Q).front];(*Q).front=((*Q).front+1)%MAXQSIZE;returnOK;}intCreateBiTree(BiTree&T)//按先序次序输入二叉中树结点的值，#表示空树构造{charch;scanf("%c",&

7、ch);if(ch=='#')T=NULL;else{if(!(T=(BiTree)malloc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CreateBiTree(T->rChild);}returnOK;}voidPreOrderTraverse(BiTreeT)//先序遍历二叉树的递归算法{if(T){printf("%c",T->data);PreOrderTraverse(T->lChild);PreOrder

8、Traverse(T->rChild);}}voidInOrderTraverse(BiTreeT)//中序遍历二叉树的递归算法{if(T){InOrderTraverse(T->lChild);printf("%c",T->data);InOrderTraverse(T->rChild);}}voidPostOrderTraverse(BiTreeT)//后序遍历二叉树