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

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 D, i=2,.,n 数据关系 R：若D为空集，则称为空树； 否则:

2、(1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm, 其中每一个子集本身又是一棵树,称为根root的子树。 基本操作： InitStack(SqStack &s) /初始化栈 StackElemty(SqStack &s) /判断栈是否为空 Push(SqStack &s,BiTree e) /将元素e进栈 Pop(SqStack &s,BiTree &e) /出栈，栈顶元素返回给e CreateBiTree(BiTree &t) /用先序建立一个二叉树，空格表示空树 InOrderTraverse(BiT

3、ree t,Status(* Visit)(TElemType e)/用非递归方式实现中序遍历，对每个元素调用函数visit PostorderTraverse(BiTree t) /用递归方式实现后序遍历 ADT BinaryTree3、 详细设计#include #include typedef int Status;typedef char TElemType;#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 50#define STACKINCREMENT 10typedef struct BiT

4、Node/树二叉链表的存储结构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_SIZE * sizeof(BiTree);if(!s.base) exit(OVERFLOW);s.top=s.base;s.stacksize=STACK_INIT_

5、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.stacksize+STACKINCREMENT)*sizeof(BiTree); if(!s.base) exit(OVERFLOW);s.top=s.base+s.stacksize;s.sta

6、cksize+=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)/用先序建立一个二叉树，空格表示空树TElemType ch;scanf(%c,&ch);if(ch= ) t=NULL;elseif(!(t=(BiTNode *)malloc(sizeof(BiTNode) exit(OVERFLOW);t-data=ch;

7、/生成根结点CreateBiTree(t-lchlid); /构造左子树CreateBiTree(t-rchlid); /构造右子树return OK;Status Visit(TElemType e)/访问函数printf(%c,e);return OK;Status InOrderTraverse(BiTree t,Status(* Visit)(TElemType e)/用非递归方式实现中序遍历，对每个元素调用函数visitSqStack s;InitStack(s); /建立一个栈存储二叉树的结点BiTree p=t;while(p|!StackElemty(s)if(p)/根指针进栈

8、，遍历左子树Push(s,p); p=p-lchlid;else /根指针退栈，访问根结点，遍历右子树Pop(s,p);if(!Visit(p-data) return ERROR;p=p-rchlid;printf(n);return OK;Status PostorderTraverse(BiTree t)/用递归方式实现后序遍历 if(t) PostorderTraverse(t-lchlid); /遍历左子树 PostorderTraverse(t-rchlid); /遍历右子树 printf(%c,t-data); /访问结点 return OK;void main()BiTree

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