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

《按给定的先序序列来建立二叉树.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、ai-1,ai∈D,i=2,...,n}数据关系R：若D为空集，则称为空树；否则:(1)在D

3、中存在唯一的称为根的数据元素root,(2)当n>1时，其余结点可分为m(m>0)个互不相交的有限集T1,T2,…,Tm,其中每一个子集本身又是一棵树,称为根root的子树。基本操作：InitStack(SqStack&s)//初始化栈StackElemty(SqStack&s)//判断栈是否为空Push(SqStack&s,BiTreee)//将元素e进栈Pop(SqStack&s,BiTree&e)//出栈，栈顶元素返回给eCreateBiTree(BiTree&t)//用先序建立一个二叉树，空格表示空树InOrderTraverse(BiTreet,Sta

4、tus(*Visit)(TElemTypee))//用非递归方式实现中序遍历，对每个元素调用函数visitPostorderTraverse(BiTreet)//用递归方式实现后序遍历}ADTBinaryTree三、详细设计#include#includetypedefintStatus;typedefcharTElemType;#defineOK1#defineERROR0#defineOVERFLOW-2#defineSTACK_INIT_SIZE50#defineSTACKINCREMENT10typedefstruc

5、tBiTNode{//树二叉链表的存储结构TElemTypedata;structBiTNode*lchlid,*rchlid;}BiTNode,*BiTree;typedefstruct{//栈的存储结构BiTree*base;BiTree*top;intstacksize;}SqStack;StatusInitStack(SqStack&s){//初始化栈s.base=(BiTree*)malloc(STACK_INIT_SIZE*sizeof(BiTree));if(!s.base)exit(OVERFLOW);s.top=s.base;s.stacksi

6、ze=STACK_INIT_SIZE;returnOK;}StatusStackElemty(SqStack&s){//判断栈是否为空if(s.base!=s.top)returnERROR;returnOK;}StatusPush(SqStack&s,BiTreee){//将元素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.

7、top=s.base+s.stacksize;s.stacksize+=STACKINCREMENT;}*s.top++=e;returnOK;}StatusPop(SqStack&s,BiTree&e){//出栈，栈顶元素返回给eif(s.top==s.base)returnERROR;e=*--s.top;returnOK;}StatusCreateBiTree(BiTree&t){//用先序建立一个二叉树，空格表示空树TElemTypech;scanf("%c",&ch);if(ch=='')t=NULL;else{if(!(t=(BiTNode*)mal

8、loc(sizeof(BiTNode))))exit(OVERFLOW);t->data=ch;//生成根结点CreateBiTree(t->lchlid);//构造左子树CreateBiTree(t->rchlid);//构造右子树}returnOK;}StatusVisit(TElemTypee){//访问函数printf("%c",e);returnOK;}StatusInOrderTraverse(BiTreet,Status(*Visit)(TElemTypee)){//用非递归方式实现中序遍历，对每个元素调用函数visitSqStacks;InitS

9、tack(s);//建立