数据结构叉树作业.doc

实验目的： 通过上机实验进一步掌握栈、队列、二叉树的存储结构及基本操作的实现方法。 实验内容与要求： 基于二叉链表存储结构实现二叉树的基本运算，要求： ⑴能建立非空二叉树； ⑵实现二叉树的先、中、后序递归遍历算法； ⑶实现二叉树的非递归的先（或中、或后）序遍历算法及层序遍历算法； ⑷记录运行结果并对递归算法和非递归算法的效率加以分析。 数据结构设计： 逻辑结构：树形结构 存储结构：链式存储结构 算法设计： #include stdio.h #include windows.h #define OK 1 #define ERROR 0 //使用二叉链表存储形式 typedef struct BiTNode { char data; struct BiTNode *lchild,*rchild; }BiTNode,*BiTree; //这里是将指向节点的指针放到栈里,而通过调试是 //可以看到指针指向的值的,所以不是将树放进去了 typedef struct { BiTree *base; BiTree *top; int stacksize; }SqStack; typedef struct { BiTree *base; int front; int rear; }SqQueue; int InitStack(SqStack S) { S.base = (BiTree *)malloc(100*sizeof(BiTree)); if( !S.base) exit(2); S.top = S.base; S.stacksize = 100; return OK; } int GetTop(SqStack S,BiTree e) { if(S.top == S.base ) return ERROR; e = *(S.top-1); return OK; } int PUSH(SqStack S ,BiTree e) { if(S.top-S.base = S.stacksize) { S.base = (BiTree *)realloc(S.base,(S.stacksize + 10)*sizeof(BiTree) ); if(!S.base) exit(2); S.top = S.base + S.stacksize; S.stacksize = S.stacksize+10; } *S.top++ = e; return OK; } int POP(SqStack S,BiTree e) { if(S.top == S.base) return ERROR; e = *--S.top; return OK; } int StackEmpty(SqStack S) { if (S.base == NULL) return ERROR; if (S.base == S.top) return OK; return ERROR; } //队列的东西伤不起啊 int InitQueue(SqQueue Q) { Q.base = (BiTree *)malloc(100*sizeof(BiTree)); if(!Q.base) exit(2); Q.front=Q.rear = 0; return OK; } int EnQueue(SqQueue Q,BiTree e) { if( (Q.rear+1) % 100 == Q.front) return ERROR; Q.base[Q.rear] = e; Q.rear = ( Q.rear+1 ) % 100; return OK; } int DeQueue(SqQueue Q,BiTree e) { if(Q.front == Q.rear) return ERROR; e = Q.base[Q.front]; Q.front = (Q.front+1) % 100; return OK; } int QueueEmpty(SqQueue Q) { if (Q.base == NULL) return ERROR; if (Q.front == Q.rear) return OK; return ERROR; } BiTree CreateBiTree(BiTree T) { // 算法6.4 // 按先序次序输入二叉树中结点的值（一个字符），空格字符表示空树， // 构造二叉链表表示的二叉树T。 char ch; scanf(%