按给定的先序序列来建立二叉树#严选优质

1、课程标题：按指定的第一个顺序创建二进制树课程：10计算机2班名称：熊必润学号：10070518完成日期：12月2日星期五1、需求分析1、标题要求1.1存储结构：二进制树存储结构的二进制链路列表1.2创建二进制树：按指定顺序创建二进制树1.3输出二进制树：以中间和结尾顺序输出二进制树的节点2、测试数据：A b $ d g $ $ c e $ h $ $ f $ ($表示空格字符)二、摘要设计Adt binary tree数据对象d: d是具有相同特性的数据元素的集合。数据关系：R1=| ai-1，ai-d，I=2，n如果数据关系r: d为空集合，则称为空树。否则，(1)在d中具有唯一的数据元素根

2、(称为根)(2) n1中，剩馀节点不相交的m (m0)的有限集t1，T2，可以分割为TM。其中，每个子集本身是根根的另一棵树，称为子树。基本任务：初始化InitStack(SqStack s) /堆栈StackElemty(SqStack s) /检查堆栈是否为空将Push(SqStack s，BiTree e) /元素e导入到堆栈中Pop(SqStack s，BiTree e) /退出堆栈时，堆栈顶部的元素将返回eCreateBiTree(BiTree t) /首先创建表示空树的二进制树(以空格表示)Inorder traverse (bi tree t，status (* visit) (

3、t elemtype e)/以非递归方式实现中间顺序遍历，为每个元素调用函数visitPostorderTraverse(BiTree t) /递归回溯实施 ADT BinaryTree3、详细设计#include#includeTypedef int StatusTypedef char TElemType#define OK 1#define ERROR 0#define OVERFLOW -2#define STACK_INIT_SIZE 50#define STACKINCREMENT 10Typedef struct BiTNode/树二进制列表存储结构TElemType dataS

4、truct BiTNode *lchlid、* rchlidBiTNode，* BiTreeTypedef struct/堆栈中的存储结构BiTree * baseBiTree * topInt stacksize SqStackStatus InitStack(SqStack s)/初始化堆栈s . base=(bi tree *)malloc(stack _ init _ size * sizeof(bi tree)；If(！s . base)exit(OVERFLOW)；s . top=s . base；S.stacksize=STACK _ INIT _ SIZEReturn OKSt

5、atus StackElemty(SqStack s)/检查堆栈是否为空If(s.base)！=s.top)Return ERRORReturn OK状态推送(SqStack s，BiTree e)/堆叠元素eIf(s.top-s.base=s.stacksize)/指定其他S.base=(bi tree *) realloc (s.base，(s . stack size stack increment)* size of(bi tree)；If(！s . base)exit(OVERFLOW)；s . top=s . base s . stacksize；s . stack size=st

6、ack increment；* s . top=e；Return OK状态端口(SqStack s，BiTree e)/退出堆栈时，堆栈顶部的元素将返回eif(s . top=s . base)return ERROR；e=*-s . top；Return OKStatus CreateBiTree(BiTree t)/首先创建包含空格的二进制树，表示空树TElemType chScanf(%c ，ch)；if(ch=)t=NULL；ElseIf(！(t=(bitnode *)malloc(size of(bitnode)exit(OVERFLOW)；t-data=ch；/创建根节点creat

7、e bitree(t-lch lid)；/配置左侧子树create bitree(t-rch lid)；/组织右侧的子树Return OKStatus Visit(TElemType e)访问/函数printf(“% c”，e)；Return OKStatus in order traverse (bi tree t，status (* visit) (t elemtype e)以非递归方式实现/中间顺序遍历，为每个元素调用函数visitsq stack s；init stack(s)；/创建存储二进制树的堆栈节点BiTree p=t；While(p|！StackElemty(s)If(p)/

8、根指针进入堆栈，通过左侧子树Push(s，p)；p=p-lch lid；Else/根指针将堆叠，访问根节点并通过右侧子树Pop(s，p)；If(！visit(p-data)return ERROR；p=p-rch lid；printf(“ n”)；Return OK状态控制器转换器(bi tree t)/递归遍历If(t)postor der traverse(t-lch lid)；/遍历左侧子树postor der traverse(t-rch lid)；/遍历右侧子树printf(“% c”，t-data)；/存取节点Return OKVoid main()BiTree t；Printf

9、(:n请输入文字字串。 n )；create bitree(t)；Printf(中间遍历结果为： n )；InOrderTraverse(t，Visit)；Printf(后遍历结果为： n )；postor der traverse(t)；printf(“ n”)；4、调试分析1、调用基本函数时，请注意函数参数类型的更改，以便程序成为Pop和Push2、运行程序时，必须正确输入才能得到结果3，定义常数，在其他点编号之后4、在与白字遍历相关的非递归方式下编写时出错。递归调用请注意5、分号、引号、书写问题等一些详细信息6、编程时一定要有耐心，程序不能一次成功编写，要找出错误并改正，必须经过持续的调试过程7、时间复杂性：Initcstack () o (1)StackElemty() O(1)