平衡二叉树匹配课程设计精选.doc
文本预览下载声明
课程设计报告
题目： 平衡二叉树匹配
班级 信计1512 姓名 朱伟光 蔡闽龙 李建峰 张衍炳 陈家彤 学号 201521143045 201521143046 201521143047 201521143048 201521143049 完成日期 2017.01.19
需求分析
1.根据输入的任意个不同的数字序列，判断是否和第一个序列模板为同一棵平衡二叉树。
2.输入的第一行数据的第一个数n（1=n=100000)表示有n个需要判断;第二个数m为序列的长度。接下去一行为一个模板序列（数字不能重复）需要判断的序列。
3.根据输入的序列构造出一棵平衡二叉树（以树的基准）。
4.通过遍历平衡二叉树的先序序列，和模板的序列比较，看是否为相同的平衡二叉树。
5.输出“YES”表示该判断的序列和模板序列一样，即和模板为同一棵平衡二叉树；反之，则为输出“NO”。
概要设计
1、设定抽象数据类型定义：
ADT BinaryTree{
数据对象D：D是具有相同特性的数据元素的集合。
数据关系R：
若D=?，则R=?，称BinaryTree为空二叉树；
若D≠?，则R≠?，称BinaryTree为非空二叉树。
基本操作P：
InsertBST(T,int e)
初始条件：树T存在，e为关键字。
操作结果：若树T中不存在等于关键字e的数据元素，则插入e，并返回“TRUE”，否则返回“FALSE”。
PreOrderTraverse(T)
初始条件：二叉树T存在。
操作结果：先序遍历T。
}
本程序主要包含三个模块：
主程序模块：
int main()
{
初始化；
输入数据；
处理命令；
输出结果；
}
树模块——实现平衡二叉树的抽象数据类型
判断模块——实现对各个序列与模板序列的比较判断
判断是否一样的伪码算法：
for循环
{ 定义一个计数的变量，且初始值为0；
for循环
{ 若该需要判断的序列是否与模板序列相同
若相同，则计数变量加一；
}
若计数变量的值等于序列长度
则输出“YES”；
否则，输出“NO”；
}
详细设计
1、平衡二叉树的类型：
typedef struct BiTNode //平衡二叉树的二叉链表存储表示
{
int data; //数据域
struct BiTNode *lchild, *rchild; //左右孩子指针
}BiTNode,*BiTree;
2、输出序列的存储类型：
int *SFXT; //序列的存储数组
SFXT = new int[num];
3、关键字的存储类型：
int *key; //关键字存储数组
key = new int[m];
插入算法：
Status SerchBST(BiTree T, int key,BiTree f,BiTree p) //在根指针T所指平衡二叉树中 //递归中递归地查找其关键字等于key的数据元素，若查找成功
//则指针p指向该数据元素结点，并返回TURE，否则指针P指向查找路径上访问的最后一//个结点并返回FALSE，指针f指向T的双亲，其初始调用值为NULL
{
if (!T)
{
p = f;
return FALSE;
} //查找不成功
else if (key == T-data)
{
p = T;
return TRUE;
} //查找成功
else if (key T-data)
return SerchBST(T-lchild, key, T, p); //在左子树中继续查找
else
return SerchBST(T-rchild
显示全部