数据结构实验报告.doc

华南农业大学信息学院
综合性、设计性实验
起止日期:2011秋
学院
软件学院
专业班级
10软件工程7班
学号
201031000704
姓名
黄定康
实
验
题
目
实现平衡二叉排序树的各种算法
自
我
评
价
项目
算法设计
独立完成情况
算法熟练程度
测试通过
成功
失败
独立
帮助
掌握
了解
不懂
插入新结点
√
√
√
√
前序、中序、后序遍历二叉树(递归)
√
√
√
√
前序、中序、后序遍历的非递归算法
√
√
√
√
层次遍历二叉树
√
√
√
√
在二叉树中查找给定关键字
√
√
√
√
交换各结点的左右子树
√
√
√
√
求二叉树的深度
√
√
√
√
叶子结点数
√
√
√
√
删除某结点
√
√
√
√
A---------完成实验要求的全部功能并运行通过,算法有一定的新意,程序代码符合书写规范,实验报告叙述清晰完整,有详尽的分析和总结。
B---------完成实验要求的全部功能,程序代码符合书写规范,实验报告叙述清晰完整。
C---------完成实验要求的大部分功能,实验报告良好。
D---------未按时完成实验,或者抄袭。
成绩
教师签名:杨秋妹
实验报告
题目:实现平衡二叉排序树的各种算法
班级:10软件工程7班
姓名:黄定康
学号:201031000704
完成日期:2011/12/07
(一)分析题目要求
(1)函数说明
void R_rotate(ptr& t) -右旋转函数,从T开始做右旋转
int coutdeep(ptr t)-计算深度函数
void L_rotate(ptr& t)-左旋转函数
void leftbalance(ptr&t)-左平衡函数,从T开始做左平衡处理
void rightbalance(ptr&t)-右平衡函数
int insertAVL(ptr& t,int e,int & taller)-插入结点函数
void preorder(ptr t)-(递归)先序遍历
void preorder_2(ptr t)-(非递归)先序遍历
void inorder(ptr t)-(递归)中序遍历
void inorder_2(ptr t)-(非递归)中序遍历
void posorder(ptr t)-(递归)后序遍历
void posorder_2(ptr t)-(非递归)后序遍历
void dfs(ptr t,int type)-(递归)深度优先遍历(包含中序先序后续)
void dfs_2(ptr t,int type)-(递归) 深度优先遍历
int bfs(ptr t)-层次便利
int delete_node(ptr& t,int&shorter,int temp);-删除结点函数
int Delete(ptr& t,int shorter)-删除结点函数
int transfer(ptr&t)-左右子树交换函数
int countleaf(ptr t)-计算叶节点
int checkup(ptr t,int temp)- 从树t中查找temp是否存在,存在返回1否则返回0
int main()-主函数
void show_menu(ptr t)-简单的菜单函数
输入形式及输入值范围
输入形式:当树没创建时,先在第一行输入树的节点数目n,第二行再输入n个大于0的不重复整数,以空格隔开。删除结点时,直接输入要删除结点的值。
输入范围:所有int类型的大于零的值,注意不能重复输入。
(3)输出形式
输出形式:各种遍历形式输出均用空格隔开,删除结点时,若成功,打印成功信息,若失败,则打印失败的信息。
(4)程序所能达到的功能
程序里面的函数可以实现平衡二叉树的以下功能:
(1) 插入新结点
(2) 前序、中序、后序遍历二叉树(递归)
(3) 前序、中序、后序遍历的非递归算法
(4) 层次遍历二叉树
(5) 在二叉树中查找给定关键字
(6) 交换各结点的左右子树
(7) 求二叉树的深度
(8) 叶子结点数
(9) 删除某结点
(二)解题思路
(1)插入的思路:插入基于一般二叉排序树的插入,但在插入的同时考虑是否破坏平衡。在结构体中假如balance function(BF),来记录当前结点的平衡情况。
(2)删除的思路:在删除结点的时候,删除之前先考虑删除之后是否影响该子树的平衡结构,再回溯考虑是否影响整棵AVL树的平衡。调整后再删除。
(3)遍历的思路:非递归的遍历都用了栈作为辅助的结构