题目:二叉排序树的实现
1 内容和要求
1） 编程实现二叉排序树， 包括生成、插入，删除；
2） 对二叉排序树进展先根、中根、 和后根非递归遍历；
3） 每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。
4） 分别用二叉排序树和数组去存储一个班(50 人以上)的成员信息(至少包括学号、姓名、成绩 3 项),比照查找效率，并说明在什么情况下二叉排序树效率高,为什么?
2 解决方案和关键代码
2.1 解决方案：
先实现二叉排序树的生成、插入、删除，编写DisplayBST函数把遍历结果用树的形状表示出来。
前中后根遍历需要用到栈的数据构造，分模块编写栈与遍历代码。
要求比照二叉排序树和数组的查找效率，首先建立一个数组存储一个班的成员信息，分别用二叉树和数组查找，利用clock〔〕函数记录查找时间来比照查找效率。
2.2关键代码
树的根本构造定义及根本函数
typedef struct
{
KeyType key;
} ElemType;
typedef struct BiTNode //定义链表
{
ElemType data;
struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree, *SElemType;
//销毁树
int DestroyBiTree(BiTree &T)
{
if (T != NULL)
free(T); return 0;
}
//清空树
int ClearBiTree(BiTree &T)
{
if (T != NULL)
{
T->lchild = NULL;
T->rchild = NULL;
T = NULL;
}
return 0;
}
//查找关键字,指针p返回
int SearchBST(BiTree T, KeyType
key, BiTree f, BiTree &p)
一、平衡二叉树的概念 平衡二叉树(Balanced binary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskii and Landis)于1962年首先提出的，所以又称为AVL树。 定义：平衡二叉树或为空树,或为如下性质的二叉排序树: （1）左右子树深度之差的绝对值不超过1; （2）左右子树仍然为平衡二叉树. 平衡因子BF=左子树深度－右子树深度. 平衡二叉树每个结点的平衡因子只能是1，0，-1。若其绝对值超过1，则该二叉排序树就是不平衡的。 如图所示为平衡树和非平衡树示意图：
二、平衡二叉树算法思想 若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。 失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树。假设用A表示失去平衡的最小子树的根结点，则调整该子树的操作可归纳为下列四种情况。 1）LL型平衡旋转法 由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。
（2）RR型平衡旋转法 由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。
（3）LR型平衡旋转法 由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。
第２７卷第１９期 ２０１１年１Ｏ月 甘肃科技 Ｇａｎｓｕ Ｓｃｉｅｎｃｅ ａｎｄ Ｔｅｃｈｎｏｌｏｇｙ ｌＺ．２７Ⅳ０．１９ Ｏｃｔ．２０１１
基于Ｃ｛［ｊ｝的二叉排序树图形显示系统研究与实现
杨政安
（兰州职业技术学院，甘肃兰州７３００７０）
摘要：介绍了二叉树在数据结构中的应用，并结合ｃ巩五言实现了二叉树的可视化功能。对二叉树的构建和输出实 现进行了说明，同时对数据结构的教学方法进行了讨论。 关键词：计算机软件；二叉树；图形显示；遍历 中图分类号：ＴＰ２９
１ 背景介绍
二叉树是树形结构的一个重要类型。许多实际
问题抽象出来的数据结构往往是二叉树的形式，即 使是一般的树也能简单地转换为二叉树，而且二叉
树的存储结构及其算法都较为简单，因此二叉树显 得特别重要。
二叉排序树（Ｂｉｎａｒｙ Ｓｏｒｔ Ｔｒｅｅ）又称二叉查找 （搜索）树（Ｂｉｎａｒｙ Ｓｅａｒｃｈ Ｔｒｅｅ）。其定义为：二叉排 序树或者是空树，或者是满足如下性质的二叉树：
１）若它的左子树非空，则左子树上所有结点的
值均小于根结点的值； ２）若它的右子树非空，则右子树上所有结点的
值均大于根结点的值； ３）左、右子树本身又各是一棵二叉排序树。
上述性质简称二叉排序树性质（ＢＳＴ性质），故
二叉排序树实际上是满足ＢＳＴ性质的二叉树。 二叉排序树在实际应用中，经常用来实现提高
数据的查寻效率，但由于概念理解上的困难，在教学
过程中，学生往往不能掌握二又树的基本操作，不能
在脑海中形成对应的模型。所以本文试图从概念人
手，用可视化的方法来对数据结构中二叉树的教学 进行改进。
２实现工具
系统采用ｃ＃编程语言进行开发，ｃ＃是微软公司 发布的一种面向对象的、运行于．ＮＥＴ Ｆｒａｍｅｗｏｒｋ之
上的高级程序设计语言，通过ｃ＃可以让开发人员快
速地建立大范围的基于ＭＳ网络平台的应用，并且
提供大量的开发工具和服务帮助开发人员开发基于 计算和通信的各种应用。基于这个特点，我们采用 Ｃ＃来开发二叉排序树图形显示系统。 ３具体设计
课程设计报告
设计题目：二叉排序树与平衡二叉树的实现
专 业
班 级
学 生
学 号
指导教师
起止时间
年 学期
目 录
1.需求分析： ........................................ 3
1.1课程设计题目、任务及要求： ......... 3
1.2课程设计思想： ................................. 3
2.概要设计： ........................................ 5
2.1二叉排序树的定义： ......................... 5
2.2二叉排序的存储结构： ..................... 5
2.3模块划分： ......................................... 5
2.4主函数流程图： ................................. 6
3.详细设计和代码： .............................. 8
3.1二叉链表： ......................................... 8
3.2顺序表： ........................................... 14
4.心得与体会： ................................... 18
1.需求分析：
1.1课程设计题目、任务及要求：
用二叉链表作存储结构：
(1)以回车('\n')为输入结束标志,输入数列L，生成一棵二叉排序树T；
(2)对二叉排序树T作中序遍历，输出结果；
(3)计算二叉排序树T查找成功的平均查找长度,输出结果；
