课程题目:按给定的先序序列来建立二叉树
1、需求分析
1、题目要求
1.1 存储结构: 以二叉链表作为二叉树的存储结构
1.2 二叉树的创建：以给定的先序序列来创建二叉树
1.3 输出二叉树: 以中序和后序序列输出二叉树的结点
2、测试数据：
A B $ D G $ $ $ C E $ H $ $ F $ $（$表示空格符号）
二、概要设计
杨澜的b什么样ADT BinaryTree {
数据对象D： D是具有相同特性的数据元素的集合。 数据关系： R1＝{ <ai-1 ,ai >|ai-1 ,ai ∈D, i=2,...,n }
数据关系 R：若D为空集，则称为空树；
否则:(1) 在D中存在唯一的称为根的数据元素root,
(2) 当n>1时，其余结点可分为m (m>0)个互不相交的有限集T1, T2, …, Tm, 其中每一个子集本身又是一棵树,称为根root的子树。
基本操作：
InitStack(SqStack &s) //初始化栈
新标准大学英语综合教程3答案 StackElemty(SqStack &s) //判断栈是否为空
Push(SqStack &s,BiTree e) //将元素e进栈
Pop(SqStack &s,BiTree &e) //出栈，栈顶元素返回给e
CreateBiTree(BiTree &t) //用先序建立一个二叉树，空格表示空树
InOrderTraver(BiTree t,Status(* Visit)(TElemType e))//用非递归方式实现中序遍历，对每个元素调用函数visit
PostorderTraver(BiTree t) //用递归方式实现后序遍历
} ADT BinaryTree
3、详细设计
#include <stdio.h>
#include <stdlib.h>
typedef int Status;
typedef char TElemType;
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define STACK_INIT_SIZE 50
#define STACKINCREMENT 10
typedef struct BiTNode
{//树二叉链表的存储结构
TElemType data;
struct BiTNode *lchlid,*rchlid;
}BiTNode,*BiTree;
typedef struct
{//栈的存储结构
BiTree *ba;
BiTree *top;
int stacksize;
}SqStack;
Status InitStack(SqStack &s)
{//captcha初始化栈
s.ba=(BiTree *)malloc(STACK_INIT_SIZE * sizeof(BiTree));
if(!s.ba) exit(OVERFLOW);
s.top=s.ba;
s.stacksize=STACK_INIT_SIZE;
turn signal
return OK;
}
Status StackElemty(SqStack &s)
{//判断栈是否为空
if(s.ba!=s.top)
return ERROR;
return OK;
}
Status Push(SqStack &s,BiTree e)
{//将元素e进栈
p-s.ba>=s.stacksize)
{ //追加分配
s.ba=(BiTree *)realloc(s.ba,(s.stacksize+STACKINCREMENT)*sizeof(BiTree));
if(!s.ba) exit(OVERFLOW);
s.top=s.ba+s.stacksize;
s.stacksize+=STACKINCREMENT;
}
*s.top++=e;
return OK;
}
Status Pop(SqStack &s,BiTree &e)
{//出栈，栈顶元素返回给e
p==s.ba) return ERROR;
e=*--s.top;
return OK;
}
Status CreateBiTree(BiTree &t)
{//用先序建立一个二叉树，空格表示空树
TElemType ch;
scanf("%c",&ch);
if(ch==' ') t=NULL;
el
{
if(!(t=(BiTNode *)malloc(sizeof(BiTNode))))
英文情景对话 exit(OVERFLOW);
t->data=ch; //生成根结点
CreateBiTree(t->lchlid); //构造左子树
CreateBiTree(t->rchlid); //构造右子树
}
always怎么读
return OK;
}
Status Visit(TElemType e)
{//访问函数
printf("%c",e);
return OK;
}
Status InOrderTraver(BiTree t,Status(* Visit)(TElemType e))
{//用非递归方式实现中序遍历，对每个元素调用函数visit
SqStack s;
电影院的英文 InitStack(s); //建立一个栈存储二叉树的结点
BiTree p=t;
while(p||!StackElemty(s))
{
if(p)
{//根指针进栈，遍历左子树
Push(s,p);
p=p->lchlid;
}
chinapay el
{//根指针退栈，访问根结点，遍历右子树
Pop(s,p);
if(!Visit(p->data)) return ERROR;
p=p->rchlid;
}
}
printf("\n");
return OK;
}
Status PostorderTraver(BiTree t)
{//用递归方式实现后序遍历
if(t)
{
PostorderTraver(t->lchlid); //遍历左子树
PostorderTraver(t->rchlid); //遍历右子树
printf("%c",t->data); //访问结点
exam
}
return OK;
}
void main()
{
BiTree t;
printf("请输入一串字符:\n");
CreateBiTree(t);
printf("中序遍历结果为:\n");
InOrderTraver(t,Visit);
printf("后序遍历结果为:\n");
PostorderTraver(t);
parkour怎么读
printf("\n");
}
4、调试分析
1、调用基本函数时要注意函数参数类型的变化，如此程序中Pop和Push
2、运行程序时要正确输入，才能有结果
3、define一个常量时，后面不用加分号
4、关于后序遍历，用非递归的方式编写时出现错误，改写成递归调用了
5、要注意一些细节，比如分号，引号、还有书写问题
6、编程时一定要耐心，程序不可能一次编写成功，需要经过不断调试才能发现并改正错误
7、时间复杂度：
InitStack( ) O(1)
StackElemty( ) O(1)
Push( ) O(1)
Pop( ) O(1)
CreateBiTree( ) O(n)
InOrderTraver( ) O(n)
PostorderTraver( ) O(n)
5、测试结果
六、附录
源程序文件名清单：
stdio.h //标准输入输出函数头文件
stdlib.h //标准库头文件
