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

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

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

2、eSTACK_INIT_SIZE100#defineSTACKINCREMENT10#defineMAXQSIZE10typedefstructBiTNode{chardata;structBiTNode*lChild,*rChild;}BiTNode,*BiTree;typedefstructSqStack{BiTNode*base;BiTNode*top;intstacksize;}SqStack;//栈类型voidInitStack(SqStack*S)//创建栈{S->base=(BiTNode*)malloc(STACK_INIT_SIZ

3、E*sizeof(BiTNode));S->top=S->base;S->stacksize=STACK_INIT_SIZE;}intStackEmpty(SqStack*S)//判断栈是否非空{if(S->top==S->base)returnOK;elsereturnERROR;}voidPush(SqStack*S,BiTNodee)//进栈{if(S->top-S->base>=S->stacksize){S->base=(BiTNode*)realloc(S->base,(S->stacksize+STACKINCREMENT)*size

4、of(BiTNode));S->top=S->base+S->stacksize;S->stacksize+=STACKINCREMENT;}*(S->top)=e;S->top++;}BiTNodePop(SqStack*S)//出栈{S->top--;return*S->top;}typedefBiTreeQElemType;//设栈元素为二叉树的指针类型typedefstruct{QElemType*base;intfront;//头指针,若队列不空,指向队列头元素intrear;//尾指针,若队列不空,指向队列尾元素的下一个位置}SqQue

5、ue;intInitQueue(SqQueue*Q)//创建队列{(*Q).base=(QElemType*)malloc(MAXQSIZE*sizeof(QElemType));if(!(*Q).base)exit(OVERFLOW);(*Q).front=(*Q).rear=0;returnOK;}intQueueEmpty(SqQueueQ)//判断队列是否为空{if(Q.front==Q.rear)returnOK;elsereturnERROR;}intEnQueue(SqQueue*Q,QElemTypee)//插入元素e为Q的新的队尾

6、元素{if(((*Q).rear+1)%MAXQSIZE==(*Q).front)returnERROR;(*Q).base[(*Q).rear]=e;(*Q).rear=((*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;}

7、intCreateBiTree(BiTree&T)//按先序次序输入二叉中树结点的值，#表示空树构造{charch;scanf("%c",&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){print

8、f("%c",T->data);PreOrderTraverse(T->lChild);PreOrderTraverse(