数据结构实验叉树的创建与遍历.docVIP

PAGE  PAGE 3 实验五 二叉树的创建与遍历 实验目的： 通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。 实验内容与要求： 基于二叉链表存储结构实现二叉树的基本运算，要求： ⑴能建立非空二叉树； ⑵实现二叉树的先、中、后序递归遍历算法； ⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法； ⑷记录运行结果并对递归算法和非递归算法的效率加以分析。 算法设计： #include stdio.h #include stdlib.h #include malloc.h #define OK 1 #define ERROR 0 #define OVERFLOW -1 #define STACK_INIT_SIZE 100 #define STACKINCREMENT 10 #define MAXQSIZE 10 typedef struct BiTNode { char data; struct BiTNode *lChild,*rChild; }BiTNode,*BiTree; typedef struct SqStack { BiTNode *base; BiTNode *top; int stacksize; } SqStack;//栈类型 void InitStack(SqStack *S)//创建栈 { S-base=(BiTNode*)malloc(STACK_INIT_SIZE*sizeof(BiTNode)); S-top=S-base; S-stacksize=STACK_INIT_SIZE; } int StackEmpty(SqStack *S)//判断栈是否非空 { if(S-top == S-base ) return OK; else return ERROR; } void Push(SqStack *S,BiTNode e)//进栈 { 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++; } BiTNode Pop(SqStack *S)//出栈 { S-top --; return *S-top; } typedef BiTree QElemType; //设栈元素为二叉树的指针类型 typedef struct { QElemType *base; int front; //头指针,若队列不空,指向队列头元素 int rear; //尾指针,若队列不空,指向队列尾元素的下一个位置 }SqQueue; int InitQueue(SqQueue *Q)//创建队列 { (*Q).base=(QElemType *)malloc(MAXQSIZE*sizeof(QElemType)); if(!(*Q).base) exit(OVERFLOW); (*Q).front=(*Q).rear=0; return OK; } int QueueEmpty(SqQueue Q)//判断队列是否为空 { if(Q.front==Q.rear) return OK; else return ERROR; } int EnQueue(SqQueue *Q,QElemType e) //插入元素e为Q的新的队尾元素 { if(((*Q).rear+1)%MAXQSIZE==(*Q).front) return ERROR; (*Q).base[(*Q).rear]=e; (*Q).rear=((*Q).rear+1)%MAXQSIZE; return OK; } int DeQueue(SqQueue *Q,QElemType *e)//删除Q的队头元素,用e返回其值 { if((*Q).front==(*Q).rear) return ERROR; *e=(*Q).base[(*Q).front]; (*Q).front=((*Q).front+1)%MAXQSIZE; return OK; } int CreateBiTr