按给定的先序序列来建

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

2、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) /用先序建立一个二叉树，空格

3、表示空树InOrderTraverse(BiTree t,Status(* Visit)(TElemType e)/ 用非递归方式实现中 序遍历，对每个元素调用函数 visitPostorderTraverse(BiTree t) / 用 递归方式实现后序遍历 ADT BinaryTree三、详细设计 #include #include typedef int Status;typedef char TElemType; #define OK 1#define ERROR 0#define OVERFLOW -2 #define STACK_INIT_SIZE 50 #define STACK

4、INCREMENT 10 typedef 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_SIZE * sizeof(BiTree);if(!s.base) exit(OVERFLO

5、W); 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.stacksize+STACKINCREM ENT)*sizeof(BiTree);if(!s.base) e

6、xit(OVERFLOW);s.top=s.base+s.stacksize; s.stacksize+=STACKINCREMENT;*s.top+=e;return OK;Status Pop(SqStack &s,BiTree &e)/ 出栈，栈顶元素返回给 eif(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*)mal

7、loc(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 InOrderTraverse(BiTree t,Status(* Visit)(TElemType e)/ 用非递归方式实现中序遍历，对每个元素调 用函数 visitSqStack s;InitStack(s); / 建立一个栈存储

8、二叉树的 结点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 OK;Status PostorderTraverse(BiTree t)/ 用递归方式实现后序遍历 if(t)PostorderTraverse(t-lchlid); / 历左子树PostorderTraverse(t-rchlid); / 历右子树p

9、rintf(%c,t-data); / 访问结点 return OK;void main()BiTree t;printf( 请输入一串字符 :n);CreateBiTree(t);printf( 中序遍历结果为 :n);InOrderTraverse(t,Visit);printf( 后序遍历结果为 :n);PostorderTraverse(t);printf(n);四、调试分析1 、调用基本函数时要注意函数参数类型的变 化，如此程序中 Pop 和 Push2 、运行程序时要正确输入，才能有结果3 、 define 一个常量时，后面不用加分号4 、关于后序遍历， 用非递归的方式编写时出 现错误，改写成递归调用了5、要注意一些细节，比如分号，引号、还有 书写问题6、编程时一定要耐心， 程序不可能一次编写 成功，需要经过不断调试才能发现并改正错误In itStack( )0(1)StackElemty( )0(1)Push( )0(1)Pop( )0(1)CreateBiTree( )0(n)In OrderTraverse( ) O( n) PostorderTraverse( ) O( n)五、测试