以二叉链表作为二叉树的存储结构,按给定的先序序列来建立二叉树.doc

课程题目:按给定的先序序列来建立二叉树 需求分析 1、题目要求 1.1 存储结构: 以二叉链表作为二叉树的存储结构 1.2 二叉树的创建：以给定的先序序列来创建二叉树 1.3 输出二叉树: 以中序和后序序列输出二叉树的结点 2、测试数据： A B $ D G $ $ $ C E $ H $ $ F $ $（$表示空格符号） 二、概要设计 ADT BinaryTree { 数据对象D： D是具有相同特性的数据元素的集合。 数据关系： R1＝{ ai-1 ,ai |ai-1 ,ai ∈D, i=2,...,n } 数据关系 R：若D为空集，则称为空树； 否则:(1) 在D中存在唯一的称为根的数据元素root, (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, …, Tm, 其中每一个子集本身又是一棵树,称为根root的子树。 } ADT BinaryTree 详细设计 #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 *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_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.stacksize+=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; else { if(!(t=(BiTNode *)malloc(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)) {//用非递归方式实现中序遍历，对每个元素调用函数visit SqStack s; InitStack(s); //建立一个栈存储二叉树的结点 BiTree p=t; while(p||!StackElemty(s)) {