实验3 二叉树的操作及应用
- 格式：docx
- 大小：15.83 KB
- 文档页数：7
实验3 二叉树的操作及应用
PB13000818 焦孟娇
实验目的：
1. 熟练掌握递归程序设计的方法。
2. 掌握二叉树的特性和基本算法。
问题描述：
二叉树是一种基本且常用的数据结构。二叉树的很多基本算法都可以用递归的形式来表述。本实验要求实现二叉树的如下操作：创建、销毁、复制、打印显示、先中后序遍历、查找元素、层序遍历、求二叉树的深度、宽度、结点数和叶子个数等。
实验内容：
一、队列的抽象数据类型定义为：
Queue operation
{
数据对象：
数据关系：
基本操作：
InitQueue(&S)
操作结果：构造一个空队列S
QueueLength(S)
初始条件：队列S已存在
操作结果：返回S的元素个数，即队列的长度
QueueEmpty(S)
初始条件：队列S已存在
操作结果：若S为空队列，则返回TRUE，否则FALSE
EnQueue(&S, e)
初始条件：队列S已存在
操作结果：插入元素e为队列新元素
DeQueue(&S, &e)
初始条件：队列S已存在且非空 操作结果：删除S的队头元素，并用e返回其值
GetHead(S, &e)
初始条件：队列S已存在且非空
操作结果：用e返回S的队头元素
ClearQueue(&S)
初始条件：队列S已存在
操作结果：将S清为空队列
DeleteQueue(&S)
初始条件：队列S已存在
操作结果：队列S被销毁
Print(S)
初始条件：队列S已存在
操作结果：输出队列S
} Queue operation
BiTree operation{
InitBiTree( &T )
// 操作结果：构造空二叉树T。
DestroyBiTree( &T )
// 初始条件：二叉树T已存在。
// 操作结果：销毁二叉树T。
CreateBiTree( &T, definition )
// 初始条件：definition给出二叉树T的定义。
// 操作结果：按definiton构造二叉树T。
ClearBiTree( &T )
// 初始条件：二叉树T存在。
// 操作结果：将二叉树T清为空树。
BiTreeEmpty( T )
// 初始条件：二叉树T存在。
// 操作结果：若T为空二叉树，则返回TRUE，否则返回FALSE。
BiTreeDepth( T )
// 初始条件：二叉树T存在。
// 操作结果：返回T的深度。
Root( T )
// 初始条件：二叉树T存在。
// 操作结果：返回T的根。
Value( T, e )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的值。
Assign( T, &e, value )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：结点e赋值为value。
Parent( T, e )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：若e是T的非根结点，则返回它的双亲，否则返回“空”。
LeftChild( T, e )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
RightChild( T, e ) // 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的右孩子。若e无右孩子，则返回“空”。
LeftSibling( T, e )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的左兄弟。若e是T的左孩子或无左兄弟，则返回“空”。
RightSibling( T, e )
// 初始条件：二叉树T存在，e是T中某个结点。
// 操作结果：返回e的右兄弟。若e是T的右孩子或无右兄弟，则返回“空”。
InsertChild( T, p, LR, c )
// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1，非空二叉树c与T不相交且右子树为空。
// 操作结果：根据LR为0或1，插入c为T中p所指结点的左或右子树。p所指结点的原有左或右子树则成为c的右子树。
DeleteChild( T, p, LR )
// 初始条件：二叉树T存在，p指向T中某个结点，LR为0或1。
// 操作结果：根据LR为0或1，删除T中p所指结点的左或右子树。
PreOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：先序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
InOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：中序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
PostOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：后序遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
LevelOrderTraverse( T, visit() )
// 初始条件：二叉树T存在，Visit是对结点操作的应用函数。
// 操作结果：层次遍历T，对每个结点调用函数Visit一次且仅一次。一旦visit()失败，则操作失败。
} BiTree operation
二、详细设计
（1）常量值、元素类型、结点类型和队列类型
#define OK 1
#define ERROR 0
#define TURE 1
#define FALSE 0
#define MAX_TREE_SIZE 100//树的最大结点数
#define MAXQSIZE 100//队列的最大长度
typedef char TElemType;
typedef int Status;
typedef struct BiTNode{
TElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree;//定义二叉树结点类型
typedef struct{
BiTree *base;
int front; int rear;
}SqQueue;//定义队列的类型
（2）函数算法分析
函数原型：BiTree CreatBiTree(BiTree &T)
算法思想：以先序次序输入二叉树中结点的值创建二叉树，‘#’代表空树。
时间复杂度：O(n)。
空间复杂度：O(n)。
函数原型：Status PreOrderTraverse(BiTree T, int (*Visit)(TElemType e))
算法思想：先序遍历二叉树T 。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：Status InOrderTraverse(BiTree T, int (*Visit)(TElemType e))
算法思想：中序遍历二叉树T 。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：Status PostOrderTraverse(BiTree T, int (*Visit)(TElemType e))
算法思想：后序遍历二叉树T 。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：Status LevelOrderTraverse(BiTree T, int (*Visit)(TElemType e))
算法思想：利用队列层序遍历二叉树T。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：int NodeCount(BiTree T)
算法思想：使用递归算法计算结点个数
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：int LeafCount(BiTree T,int &leaf)
算法思想：递归计算二叉树的叶子结点个数。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：int Depth(BiTree &T)
算法思想：递归计算二叉树的深度。
时间复杂度：O(n)。
空间复杂度：O(1)。
函数原型：int Width(BiTree T,int n[],int &i)
