平衡树二叉的定义-Read.DOC

山东理工大学计算机学院 课 程 设 计 （数据结构） 班 级 姓 名 学 号 指导教师 二○ ○ 六 年 七 月 六 日 课程设计任务书及成绩评定 课题名称 平衡二叉树的操作演示 题目的目的和要求： 设计进度及完成情况 日 期 内 容 6月26号 熟悉题目，查找资料 6月27号 熟悉题目，查找资料 6月28号 画出流程图，确定算法 6月29号 根据算法和资料写出相应的程序 6月30号 调试程序 7月1号 调试程序 7月2号 编写课程设计报告 主要参考文献及资料 1．数据结构 （ C语言） 曲建民 刘元红 郑陶然 清华大学出版社 2. 数据结构 （ C语言版） 严蔚敏 吴伟民 清华大学出版社 3. 数据结构题集（ C语言版）严蔚敏 吴伟民 清华大学出版社 4. 数据结构—C++实现 缪淮扣 顾训穰 沈俊/ 科学出版社 学科部主任___________（签字） Ⅵ、成绩评定： 设计成绩： （教师填写） 指导老师： （签字） 二○ 年 月 日 课程设计目录 1.问题描述及要求………………………………………………………4 2.平衡二叉树的定义及查找算法………………………………………5 3.平衡二叉树的插入算法及平衡处理…………………………………6 4.平衡二叉树的删除算法………………………………………………9 5.程序流程图…………………………………………………………10 6.C++的程序代码………………………………………………………11 7.程序测试结果………………………………………………………18 8.课程设计总结………………………………………………………20 平衡二叉树操作的演示 【问题描述】 利用平衡二叉树实现一个动态查找表。 【基本要求】 实现基本查找表的三种基本功能：查找、插入和删除。 【测试数据】 自行设定。 【实现过程与算法思想】 平衡树二叉的定义： 平衡树二叉是二叉排序树的另一种形式，其特点为：树中每个结点的左、右子树深度之差的绝对值不大于1 即 |hl-hr|=1 ; 如图所示： 一棵非平衡的二叉树 一棵平衡的二叉树 平衡树二叉的类型定义： typedef struct tree_n_t { int key; struct tree_n_t *left //左孩子指针 struct tree_n_t *right; //右孩子指针 int bf; //结点的平衡因子 } tree_node_t; 查找操作算法思想：判断当前的平衡二叉树是否为空；为空则查找失败。当该平衡二叉树不为空时先将给定的值与根节点的关键字比较，若相等，则查找成功，否则将依据给定值和根节点的关键字之间的关系，分别在左子树或右子树上进行查找（给定值根节点的关键字则在左子树继续查找；给定值根节点的关键字则在右子树继续查找），继续下去直到最后找到“定值=根节点的关键字“的节点查找成功。若找不到则查找失败。 C++语言的实现过程： obj_node_t *search(tree_node_t *tree,int query_key) {tree_node_t *temp; if(tree-left==NULL) return(NULL); else{temp=tree; while(temp-right!=NULL) { if(query_keytemp-key) temp=temp-left; else temp=temp-right; }if(temp-key==query_key) return((obj_node_t*)temp-left); else return(NULL); //查找不成功 } } 2．插入操作算法思想： ⑴若为BBST空树，则插入一个数据元素为e的新结点作为BBST的根结点,树的深度增1。 ⑵若e的关键字和BBST根结点的关键字相等，则不进行插入； ⑶若e的关键字小于BBST根结点的关键字，而且在BBST的左子树中不存在和e有相同关键字的结点，则将e 插入在BBST的左子树上，并且当插入之后的左子树深度增加（+1）时，分别就下列不同情况处理之： BBS