按给定的先序序列来建立二叉树

1、课程题目:按给定的先序序列来建立二叉树班级：10计算机2班 姓名：熊芸芸 学号：10070518完成日期：12月2日星期五1、 需求分析1、题目要求1.1 存储结构: 以二叉链表作为二叉树的存储结构1.2 二叉树的创建：以给定的先序序列来创建二叉树1.3 输出二叉树: 以中序和后序序列输出二叉树的结点2、测试数据：A B $ D G $ $ $ C E $ H $ $ F $ $（$表示空格符号）二、概要设计ADT BinaryTree 数据对象D： D是具有相同特性的数据元素的集合。 数据关系： R1 <ai-1 ,ai >|ai-1 ,ai D, i=2,.,n 数据关系 R：

2、若D为空集，则称为空树； 否则:(1) 在D中存在唯一的称为根的数据元素root, (2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, , Tm, 其中每一个子集本身又是一棵树,称为根root的子树。 基本操作： InitStack(SqStack &s) /初始化栈 StackElemty(SqStack &s) /判断栈是否为空 Push(SqStack &s,BiTree e) /将元素e进栈 Pop(SqStack &s,BiTree &e) /出栈，栈顶元素返回给e CreateBiTree(BiTre

3、e &t) /用先序建立一个二叉树，空格表示空树 InOrderTraverse(BiTree t,Status(* Visit)(TElemType e)/用非递归方式实现中序遍历，对每个元素调用函数visit PostorderTraverse(BiTree t) /用递归方式实现后序遍历 ADT BinaryTree3、 详细设计#include <stdio.h>#include <stdlib.h>typedef int Status;typedef char TElemType;#define OK 1#define ERROR 0#define O

4、VERFLOW -2#define STACK_INIT_SIZE 50#define STACKINCREMENT 10typedef struct BiTNode/树二叉链表的存储结构TElemType data;struct BiTNode *lchlid,*rchlid;BiTNode,*BiTree;typedef struct /栈的存储结构 BiTree *base;BiTree *top;int stacksize;SqStack;Status InitStack(SqStack &s)/初始化栈s.base=(BiTree *)malloc(STACK_INIT_SI

5、ZE * sizeof(BiTree);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;return OK;Status StackElemty(SqStack &s)/判断栈是否为空if(s.base!=s.top)return ERROR;return OK;Status Push(SqStack &s,BiTree e)/将元素e进栈if(s.top-s.base>=s.stacksize) /追加分配s.base=(BiTree *)realloc(s.base,(s.stac

6、ksize+STACKINCREMENT)*sizeof(BiTree); if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status Pop(SqStack &s,BiTree &e)/出栈，栈顶元素返回给e if(s.top=s.base) return ERROR;e=*-s.top;return OK;Status CreateBiTree(BiTree &t)/用先序建立一个二叉树，空格表示空树TElemTy

7、pe ch;scanf("%c",&ch);if(ch=' ') t=NULL;elseif(!(t=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);t->data=ch; /生成根结点CreateBiTree(t->lchlid); /构造左子树CreateBiTree(t->rchlid); /构造右子树return OK;Status Visit(TElemType e)/访问函数printf("%c",e);return OK;Status InOrder

8、Traverse(BiTree t,Status(* Visit)(TElemType e)/用非递归方式实现中序遍历，对每个元素调用函数visitSqStack s;InitStack(s); /建立一个栈存储二叉树的结点BiTree p=t;while(p|!StackElemty(s)if(p)/根指针进栈，遍历左子树Push(s,p); p=p->lchlid;else /根指针退栈，访问根结点，遍历右子树Pop(s,p);if(!Visit(p->data) return ERROR;p=p->rchlid;printf("n");return

9、OK;Status PostorderTraverse(BiTree t)/用递归方式实现后序遍历 if(t) PostorderTraverse(t->lchlid); /遍历左子树 PostorderTraverse(t->rchlid); /遍历右子树 printf("%c",t->data); /访问结点 return OK;void main()BiTree t;printf("请输入一串字符:n");CreateBiTree(t);printf("中序遍历结果为:n");InOrderTraverse(t

10、,Visit);printf("后序遍历结果为:n"); PostorderTraverse(t);printf("n");4、 调试分析 1、调用基本函数时要注意函数参数类型的变化，如此程序中Pop和Push 2、运行程序时要正确输入，才能有结果 3、define一个常量时，后面不用加分号 4、关于后序遍历，用非递归的方式编写时出现错误，改写成递归调用了5、要注意一些细节，比如分号，引号、还有书写问题6、编程时一定要耐心，程序不可能一次编写成功，需要经过不断调试才能发现并改正错误 7、时间复杂度： InitStack( ) O(1)StackElemty