以二叉链表作为二叉树的存储结构,按给定的先序序列来建立二叉树

课程题目:按给定的先序序列来建立二叉树一、需求分析1、题目要求1.1存储结构:以二叉链表作为二叉树的存储结构1.2二叉树的创建：以给定的先序序列来创建二叉树1.3输出二叉树:以中序和后序序列输出二叉树的结点2、测试数据：AB$DG$$$CE$H$$F$$（$表示空格符号）二、概要设计ADTBinaryTree{数据对象D：D是具有相同特性的数据元素的集合。数据关系：R1＝{ai-1,ai|ai-1,ai∈D,i=2,...,n}数据关系R：若D为空集，则称为空树；否则:(1)在D中存在唯一的称为根的数据元素root,(2)当n1时，其余结点可分为m(m0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵树,称为根root的子树。基本操作：InitStack(SqStack&s)//初始化栈StackElemty(SqStack&s)//判断栈是否为空Push(SqStack&s,BiTreee)//将元素e进栈Pop(SqStack&s,BiTree&e)//出栈，栈顶元素返回给eCreateBiTree(BiTree&t)//用先序建立一个二叉树，空格表示空树InOrderTraverse(BiTreet,Status(*Visit)(TElemTypee))//用非递归方式实现中序遍历，对每个元素调用函数visitPostorderTraverse(BiTreet)//用递归方式实现后序遍历}ADTBinaryTree三、详细设计#includestdio.h#includestdlib.htypedefintStatus;typedefcharTElemType;#defineOK1#defineERROR0#defineOVERFLOW-2#defineSTACK_INIT_SIZE50#defineSTACKINCREMENT10typedefstructBiTNode{//树二叉链表的存储结构TElemTypedata;structBiTNode*lchlid,*rchlid;}BiTNode,*BiTree;typedefstruct{//栈的存储结构BiTree*base;BiTree*top;intstacksize;}SqStack;StatusInitStack(SqStack&s){//初始化栈s.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}StatusStackElemty(SqStack&s){//判断栈是否为空if(s.base!=s.top)returnERROR;returnOK;}StatusPush(SqStack&s,BiTreee){//将元素e进栈if(s.top-s.base=s.stacksize){//追加分配s.base=(BiTree*)realloc(s.base,(s.stacksize+STACKINCREMENT)*sizeof(BiTree));if(!s.base)exit(OVERFLOW);s.top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}StatusPop(SqStack&s,BiTree&e){//出栈，栈顶元素返回给eif(s.top==s.base)returnERROR;e=*--s.top;returnOK;}StatusCreateBiTree(BiTree&t){//用先序建立一个二叉树，空格表示空树TElemTypech;scanf(%c,&ch);if(ch=='')t=NULL;else{if(!(t=(BiTNode*)malloc(sizeof(BiTNode))))exit(OVERFLOW);t-data=ch;//生成根结点CreateBiTree(t-lchlid);//构造左子树CreateBiTree(t-rchlid);//构造右子树}returnOK;}StatusVisit(TElemTypee){//访问函数printf(%c,e);returnOK;}StatusInOrderTraverse(BiTreet,Status(*Visit)(TElemTypee)){//用非递归方式实现中序遍历，对每个元素调用函数visitSqStacks;InitStack(s);//建立一个栈存储二叉树的结点BiTreep=t;while(p||!StackElemty(s)){if(p){//根指针进栈，遍历左子树Push(s,p);p=p-lchlid;}else{//根指针退栈，访问根结点，遍历右子树Pop(s,p);if(!Visit(p-data))returnERROR;p=p-rchlid;}}printf(\n);returnOK;}StatusPostorderTraverse(BiTreet){//用递归方式实现后序遍历if(t){PostorderTraverse(t-lchlid);//遍历左子树PostorderTraverse(t-rchlid);//遍历右子树printf(%c,t-data);//访问结点}returnOK;}voidmain(){BiTreet;printf(请输入一串字符:\n);CreateBiTree(t);printf(中序遍历结果为:\n);InOrderTraverse(t,Visit);printf(后序遍历结果为:\n);PostorderTraverse(t);printf(\n);}四、调试分析1、调用基本函数时要注意函数参数类型的变化，如此程序中Pop和Push2、运行程序时要正确输入，才能有结果3、define一个常量时，后面不用加分号4、关于后序遍历，用非递归的方式编写时出现错误，改写成递归调用了5、要注意一些细节，比如分号，引号、还有书写问题6、编程时一定要耐心，程序不可能一次编写成功，需要经过不断调试才能发现并改正错误7、时间复杂度：InitStack()O(1)StackElemty()O(1)Push()O(1)Pop()O(1)CreateBiTree()O(n)InOrderTraverse()O(n)PostorderTraverse()O(n)五、测试结果六、附录源程序文件名清单：stdio.h//标准输入输出函数头文件stdlib.h//标准库头文件