数据结构实验五二叉树的创建与遍历

《数据结构实验五二叉树的创建与遍历》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、实验五二叉树的创建与遍历实验目的：通过上机实验进一步掌握栈、队列、二叉树的存储结构及基木操作的实现方法。实验内容与要求：基于二义链表存储结构实现二义树的基本运算，要求：⑴能建立非空二叉树；⑵实现二叉树的先、屮、后序递归遍历算法；⑶实现二叉树的非递归的先(或中、或后)序遍历算法及层序遍历算法；⑷记录运行结果并对递归算法和非递归算法的效率加以分析。算法设计：#includevoidPush(SqStack*S,B汀Nodee)〃进栈#include#include

2、#defineOK1#defineERROR0#defineOVERFLOW-1#dcfincSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE10typedefstructBiTNode{chardata;structBiTNode*lChild,*rChild;沖汀Node,*B汀ree;typedefstructSqStack{BiTNode*basc;BiTNode*top;intstacksize;}SqS

3、tack;〃栈类型voidInitStack(SqStack*S)〃创建栈{S->base=(B汀Node*)malloc(STACK」N1T_SIZE*sizeof(BiTNode));S・>top二S・>base;S->stacksizc=STACK_INIT_SIZE;}intStackEmpty(SqStack*S)〃判断栈是否非空{if(S->top==S->basc)returnOK;elsereturnERROR;if(S->top-S->base>=S->stacksize){S-

4、>base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*sizeof(BiTNode));S->top=S->base+S->stacksize;S->stacksizc+二STACKINCREMENT;}*(S->top)=e;S・>top++;)BiTNodePop(SqStack*S)〃出栈{S->topreturn*S->top;)typedefBiTreeQElemType;〃设栈元素为二叉树的指针类型typedefst

5、ruct{QElemType*base;intfront;//头指针，若队列不空，指向队歹!J头元素intrear;〃尾指针，若队列不空，指向队列尾元素的下一个位置JSqQueue;intInitQueue(SqQueue*Q)〃创建队列{(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).basc)exit(OVERFLOW);(*Q).front=(*Q).rear=0;returnOK;}intQucucEmpt

6、y(SqQucucQ)〃判断队列是否为空{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=((*Q).rear+1)%MAXQSIZE;returnOK;}intDcQucuc(SqQucuc*Q,

7、QElcmTypc*c)〃删除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",&ch);if(ch==,#,)T=NULL;else{if(!(T=(BiTree)mall

8、oc(sizeof(BiTNode))))exit(OVERFLOW);T->data=ch;CreateBiTree(T->lChild);CrcatcBiTrcc(T->rChild);}returnOK;voidPreOrderTraverse(BiTreeT)〃先序遍历二义树的递归算法{if(T){printf(“％c”,T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(T->rChild);})voidInOrde