二叉树实习报告 二叉树 实验报告.docx

实习报告
题目：树及其应用一一二叉树的遍历
班级：09软件1班姓名：Fantasy学号：0925113040完成日期：
需求分析
编写程序，对给定的一棵二叉树进行先，中，后三种次序的遍历
以二叉链表为存储结构，实t()){
〃初始条件：二叉树T存在，Visit是对结点操作的应用函数
〃操作结果：层序遍历T,对每个结点调用函数Visit-次且仅一次
}ADTBinaryTree
2•设定栈的抽象数据类型定义：
ADTStack{
数据对象：D={ai|aiGCharSet,1=1,2n,n^O}
数据关系：R"{<ai-l,ai>|ai-l,aiWD,I=2,...,n}
基本操作：
lnitStack(&S)
操作结果：构造一个空栈S。
DestroyStack(&S)
初始条件：栈S已存在
操作结果：销毁栈S。
ClearStack(&S)
初始条件：栈S已存在操作结果：清空栈S。
StackLength(S)
初始条件：栈S已存在
操作结果：返回栈S的长度。
StackEmpty(S)
初始条件：栈S已存在
操作结果：若S为空栈，则返回true,否则返回falseo
GetTop(S,&e)
初始条件：栈S已存在
操作结果：若栈S不空，则以e返回栈顶元素。
Push(&S,e)
初始条件：栈S已存在
操作结果：在栈S的栈顶插入新的栈顶元素e°
Pop(&S,e)
初始条件：栈S已存在
操作结果：删除栈S的栈顶元素，并以e返回其值。
StackTraverse(S,visit())
初始条件：栈S已存在
操作结果：从栈底到栈顶依次对S中的每个元素调用函数visit()。
}ADTStack
3•设定队列的抽象数据类型定义：
ADTQueue{
数据对象：D={ai|aiGCharSet,1=1,2n,n^O}
数据关系:Rl={<ai-l,ai>|ai-l,aieDJ=2,...,n}
约定其中al端为对猎头，an端为队列尾
基本操作：
InitQueue(&Q);
操作结果：构造一个空队列
DestroyQueue(&Q);
初始条件：队列Q已存在
操作结果：队列Q被销毁，不再存在
ClearQueue(&Q);
初始条件：队列Q已存在
操作结果：将Q清为空队列
QueueEmpty(Q);
初始条件：队列Q已存在
操作结果：若队列Q为空队列，则返回TRUE。否则返回FALSE
QueueLength(Q)
初始条件：队列Q已存在
操作结果：返回Q的元素个数，即队列的长度
GetHead(Q,&e);
初始条件：队列Q已存在
操作结果：用e返回Q的队头元素
EnQueue(&Q,e);
初始条件：队列Q已存在
操作结果：插入元素e为Q的新的队尾元素
DeQueue(&Q,&e);
初始条件：Q为非空队列
操作结果：删除Q的对头元素，并用e返回其值
QueueTraverse(Q,Visit());
初始条件：Q已存在且非空；
操作结果：从对头到队尾，依次对Q的每个元素调用函数Visit()—次且仅一次,一旦Visit()失败，则操作失败。
}ADTQueue4；本程序有3个模块,模块之间的调用关系如下
详细设计
二叉树类型
typedefcharTEIemType;〃二叉树存储的数据类型
typedefstructBiTNode{〃二叉树的结点定义TEIemTypedata;
BiTNode*lchildz*rchild;//左右孩子指针
}BiTNode,*BiTree;
//基本操作的函数原型说明(部分)
StatusCreateBiTree(BiTree&T);
〃按先序次序输入二叉树中节点的值(一个字符)字符表示空树〃构造二叉链表表示的二叉树
StatusPreOrderTraverse(BiTreeTzStatus(*Visit(TelemTypee)));
〃采用二叉链表存储结构，Visit是对节点操作的应用函数、〃先序遍历二叉树To对每个节点调用函数Visit一次且仅一次〃一旦Visit()失败。则操作失败
StatusInOrderTraversefBiTreeTStatus(*Visit(TelemTypee)));
〃采用二叉链表存储结构，Visit是对节点操作的应用函数、〃中序遍历二叉树To对每个节点调用函数Visit一次且仅一次〃一旦Visit()失败。则操作失败
StatusPostOrderTraverse(BiTreeTStatus(*Visit(TelemTypee)));
〃采用二叉链表存储结