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

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(bitr

3、ee 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 bitn

4、ode/树二叉链表的存储结构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_s

5、ize;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.stac

6、ksize+=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 t

9、;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