数学与计算机学院计算机系数据结构程序设计报告
平衡二叉树
学生姓名：* *
学 好：1004681028
班 级：计算机系102
指导老师：* * *
报告日期：2011/6/26
1.平衡二叉树…………………………………………………3
1.1平衡二叉树的定义…………………………………...3考公务员看什么书
1.2平衡二叉树的构造…………………………………...3
1.3平衡二叉树查找的分析……………………………...3
2.程序功能……………………………………………………3草莓的功效与作用禁忌
3.程序结构类型………………………………………………3
4.程序函数……………………………………………………4
5.算法思想……………………………………………………5
5.1 判断二叉树的旋转方法敬若神明……………………………...5
5.2 平衡旋转处理………………………………………...5
5.3 在平衡二叉树中插入元素…………………………...5
5.4 在平衡二叉树中删除元素………………………...…5
5.5 输出平衡二叉树树形………………………………...5
5.6 销毁平衡二叉树……………………………………...5
6.程序设计总结……………………………………………….9阶段性
7.结束语………………………………………………………10
8.附录：程序清单……………………………………………10
1.六一儿童节礼物平衡二叉树
1.1平衡二叉树的定义
平衡二叉树(Balanced Binary Tree或Height-Balanced Tree)又称AVL树。它或者是一颗空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(Balanced Factor)定义为该结点的左子树的深度减去它的右子树的深度，则平衡二叉树上所有结点的平衡因子之可能是-1、0和1。只要二
叉树上有一个结点的平衡因子的绝对值大于1，则该二叉树就是不平衡的。
1.2平衡二叉树的构造
举重若轻的意思 构造一颗平衡二叉树的过程就是将一颗空树从根结点起，逐步插入或删除结点并不断对
此树进行平衡化。在构造平衡二叉树的过程中有插入和删除两大操作。在树中进行插入和删除操作都可使树失去平衡，然而要让二叉排序树由不平衡转化为平衡，操作就是对二叉树进行旋转，旋转的过程将在算法思想中详细介绍。
1.3平衡二叉树查找的分析
在平衡二叉树上进行查找的过程和二叉排序树相同，因此，在查找过程中和给定值进行比较的关键字个数不超过树的深度。因此，在平衡二叉树上进行查找的时间复杂度为O(log n).
2.程序功能
本程序的功能就是将二叉排序树转变为平衡二叉树，其操作有:创建二叉树、插入数据、
删除数据、输出、销毁二叉树和退出。
1——创 建 二 叉 树 2——插 入 数 据 3——删 除 数 据 4——输 出 5——销 毁 二 叉 树 0——退 出 |
请选择: |
|
3.程序结构类型
在本程序中主要用到两个结构类型：结构体和队列。二叉树是链式存储结构，故用结构
体来定义其结构。队列是用作输出二叉树的树形（层序输出）。
4.程序函数
4.1 main()函数：
（1）函数原形：void main()
（2）功能：显示总菜单，调用子函数
4.2 Create()函数:
（1）函数原形：void Create(BSTree &T)
（2）功能：实现二叉树的创建
4.3 Inrt()函数:
（1）函数原形：void Inrt(BSTree &T)
（2）功能：实现在二叉树中插入数据
4.4 InrtAVL()函数:
（1）函数原形：int InrtAVL(BSTree &T,int e,int &taller)
（2）功能：插入结点，并将二叉树平衡化
4.5 DeleteMenu()函数:
（1）函数原形：void DeleteMenu(BSTree &T)
（2）功能：实现在二叉树中删除数据
4.6 DeleteAVL()函数:
（1）函数原形：int DeleteAVL(BSTree &T,int e,int &shorter)
（2）功能：删除结点，并将二叉树平衡化
4.7Delete鲜活水()函数:
（1）函数原形：int Delete(BSTree &p)
（2）功能：实现删除结点
4.8 Search()函数:
（1）函数原形：void Search(BSTree &T,int e,int key)
（2）功能：在树中查找和关键字相等的结点
4.9 R_Rotate()函数:
（1）函数原形：void R_Rotate(BSTree &p)
（2）功能：对以*p为根结点的子树进行右旋平衡处理
4.10 L_Rotate()函数:
（1）函数原形：void L_Rotate(BSTree &p)
（2）功能：对以*p为根结点的子树进行左旋平衡处理
4.11 RightBalance()函数:
（1）函数原形：int RightBalance(BSTree &T)自己做奶茶怎么做
（2）功能：对以指针T所指结点为根的二叉树作右平衡旋转处理
4.12 LeftBalance()函数:
（1）函数原形：int LeftBalance(BSTree &T)
（2）功能：对以指针T所指结点为根的二叉树作左平衡旋转处理
4.13 Output()函数:
（1）函数原形：void Output(BSTree T)
（2）功能：将二叉树按中序和层序输出
4.14 Inordertraver()函数:
（1）函数原形：void Inordertraver(BSTree T)
