广工数据结构课设-平衡二叉树演示(文档尾部含源码下载地址)课案.doc

课程设计报告

课程名称 数据结构课程设计
学 院 计算机学院
专业班级 计科9班
学 号
学生姓名
指导教师 苏庆

2015 年 7 月 6 日

一、 需求分析
程序《平衡二叉树的演示》是对平衡二叉树的创建、插入、删除、查找、合并、分裂功能的实现，以及用凹入表的形式将其展示给用户。
（1） 输入的形式是数字，无论对功能的选则还是对数据的录入，都是以数 字的形式进行输入，无需使用文件保存数据。输入值得范围在使用过程 中会有说明。
（2） 输出的形式是在Dos界面进行输出，
（3） 程序所能达到的功能：
A.创建一棵非空平衡二叉树
B.创建一棵空的平衡二叉树
C.向平衡二叉树中添加结点
D.从平衡二叉树中删除结点
E.在平衡二叉树中查找结点
F.以凹入表的形式输出一棵二叉树
G.以括号表示法输出一棵二叉树
附加功能：
F.合并两棵平衡二叉树
H.分裂一棵平衡二叉树

二、 概要设计
（1） 本程序涉及到的数据类型有：链栈，链队列，平衡二叉树，
结构体数组
（2）主程序是负责对各个功能进行展示，然后根据输入来选择进行相对应 的功能，代码如下：
int main(){
int m;
BBSTree T = NULL;
SetColor();
InitView();
printf("\n\t\t\t 请输入你的选择：");
scanf("%d",&m);
getchar();
while(1){
switch(m){
case 1:
T = item_1();
break;
case 2:
item_2(T);
break;
case 3:
item_3(T);
break;
case 4:
item_4(T);
break;
case 5:
item_5(T);
break;
case 6:
item_6();
break;
case 7:
item_7();
break;
}
if(m==8){
item_8();
break;
}else if(m>8||m<1){
system("CLS");
InitView();
printf("\n\t\t\t 输入错误，请重新输入!!\n");
}
printf("\n\t\t\t 请输入你的选择：");
scanf("%d",&m);
getchar();
}
return 0;
}
（3） 各模块之间的关系

三、详细设计
（1） 数据类型的定义
/*存放输入数据的数组结构体*/
typedef struct ArrayNode{
RcdType data;
ArrayNode *next;
}ArrayNode, *Array;

/*平衡二叉树结构体*/
typedef struct BBSTNode{
RcdType data;
int bf;
BBSTNode *lchild, *rchild;
}BBSTNode,*BBSTree;

/*链队列结构体*/
typedef struct LQNode{
BBSTree elem;
struct LQNode *next;
}LQNode, *QueuePtr;

/*队列结点结构体*/
typedef struct{
QueuePtr front;
QueuePtr rear;
}LQueue;

/*栈结点结构体*/
typedef struct LSNode{
BBSTree data; //数据域
struct LSNode *next; //指针域
}LSNode, *LStack; //结点和链栈类型
（2） 伪代码：
A. 建树操作
begin
BBSTree T
Array a
a = GetInputToArray(); //获取到输入的数组
While a!=NULL{
InsertAVL(T, a->data)
a = > a->next
}
End
B.插入结点
begin
if(NULL==T){
T->data = e
T->bf = EH
T->lchild = NULL
T->rchild = NULL
}else if(e==T->data){ //书中已存在和e相等的结点
return FALSE;
}else if(e<T->data){
if(!InsertAVL(T->lchild, e)) return FALSE;
if(TRUE==taller){
switch(T->bf){
case LH: LeftBalance(T); taller = FALSE; break;
case EH: T->bf = LH; taller = TRUE; break;
case RH: T->bf = EH; taller = FALSE; break;
}
}
}else{
if(FALSE==InsertAVL(T->rchild, e)) return FALSE;
if(TRUE==taller){
switch(T->bf){
case LH: T->bf = EH; taller = FALSE; break;
case EH: T->bf = RH; taller = TRUE; break;
case RH: RightBalance(T); taller = FALSE; break;
}
}
}
return TRUE;
End
C.删除操作
begin
//当被删结点是有两个孩子，且其前驱结点是左孩子时，tag=1
static int tag = 0;
if(t == NULL){
return FALSE; //如果不存在元素，返回失败
}else if(e==t->data){
BBSTNode *q = NULL;
//如果该结点只有一个孩子，则将自子树取代该结点
if(t->lchild == NULL){
q = t;
t = t->rchild;
free(q);
shorter = TRUE;
}
else if(t->rchild == NULL){
q = t;
t = t->lchild;
free(q);
shorter = TRUE;
}
//如果被删结点有两个孩子，则找到结点的前驱结点，
//并将前驱结点的值赋给该结点，然后删除前驱结点
else{
q = t->lchild;
while(q->rchild){
q = q->rchild;
}
t->data = q->data;
if(t->lchild->data==q->data){
tag = 1;
}
DeleteAVL(t->lchild, q->data, shorter);
if(tag==1){
BBSTree r = t->rchild;
if(NULL==r) t->bf = 0;
else{
switch(r->bf){
case EH: t->bf=-1;break;
default: RightBalance(t);break;
}
}
}
}
}else if(e<t->data){ //左子树中继续查找
if(!DeleteAVL(t->lchild, e, shorter)){
return FALSE;
}
//删除完结点之后，调整结点的平衡因子
if(shorter&&(tag==0)) {
switch(t->bf){
case LH:
t->bf = EH;
shorter = TRUE;
break;
case EH:
t->bf = RH;
shorter = FALSE;
break;
//如果本来就是右子树较高，删除之后就不平衡，需要做右平衡操作
case RH:
RightBalance(t); //右平衡处理
if(t->rchild->bf == EH)
shorter = FALSE;
else
shorter = TRUE;
break;
}
}
}else if(e>t->data){ //右子树中继续查找
if(!DeleteAVL(t->rchild, e, shorter)){
return FALSE;
}
//删除完结点之后，调整结点的平衡因子
if(shorter&&(tag==0)) {
switch(t->bf){
case LH:
LeftBalance(t); //左平衡处理
if(t->lchild->bf == EH)
shorter = FALSE;
else
shorter = TRUE;
break;
case EH:
t->bf = LH;
shorter = FALSE;
break;
case RH:
t->bf = EH;
shorter = TRUE;
break;
}
}
if(tag==1){
int depthLeft = BBSTreeDepth(t->lchild);
int depthRight = BBSTreeDepth(t->rchild);
t->bf = depthLeft - depthRight;
}
}
return TRUE;
End
D.查找操作
Begin
if(T==NULL) return NULL;
if(e==T->data){
return T;
}else if(e>T->data){
return SearchAVL(T->rchild, e);
}else {
return SearchAVL(T->lchild, e);
}
End
E.合并操作
Begin
Status taller = TRUE;
Array a = NULL;
a = GetArrayFromTree(T2);
while(a!=NULL){
taller = TRUE;
InsertAVL(T1, a->data, taller);
a = a->next;
}
return T1;
End
F.分裂操作
Begin
Array a = NULL;
Status taller;
a = GetArrayFromTree(Tt1); //获取到树转化为的数组
if(Tt1==NULL) return FALSE;
else{
while(a!=NULL){
if(a->data<=x){
taller = TRUE;
InsertAVL(Tt2, a->data, taller);
a = a->next;
}else {
taller = TRUE;
InsertAVL(Tt3, a->data, taller);
a = a->next;
}
}
}
return TRUE;
End
（3） 关系图
A. 建树操作

B.添加结点操作

C.删除结点操作

D.查找结点操作

E.合并操作

F.分裂操作

四、 调试分析
1. 调试过程中所遇到的问题：
运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题，但是换了个编译器还是同样的问题，后来我上网查询了有关资料，大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉，一条一条测试，调试过程很漫长，最后才发现是内存泄露和空指针异常，将指针不适用之后指向为NULL，才把问题解决了。
2. 经验和体会
a) 在做一个比较大的程序过程中，应该学会边编写程序边运行，即当你完成了一个比较小的功能时便对其调试，这样有助于我们高效地完成项目，而且在调试BUG的过程也可以大大减小其难度。
b) 必须要有良好的编程习惯。首先编码风格一定要规范，这样不仅有利于读者和编程者对代码的阅读， 更有利于对代码的维护。其次要对代码要细心，比较一些指针的初始化和不需要时指为空，这些都是可以极大减少我们出现BUG的几率。
c) 写的程序一定要人性化，现在的应用都讲究与人交互的重要性，其避免不了使用各种炫酷的图形界面，但我们要考虑的是，即便是C语言，没有什么图形界面，我们也一定要考虑人性化的问题。
五、 使用说明
1. 本程序的可执行文件是：平衡二叉树的演示.exe
2. 双击exe文件，进入主界面：

3. 然后我们应该先创建一棵非空二叉树或者是空的二叉树，输入1或者2， 按回车键，此处我们输入1，如下：

4. 此时，程序提示我们输入树的序列，我们可以以此输入数字，不同数字用 空格隔开，按回车表示输入完成，例如，我们输入10 20 30 40 50 60回车， 得到如下，程序提示我们创建成功，并输出了该平衡二叉树，此时按任意 键返回。

5. 返回到了首页，此时我们可以输入3，往此树中添加结点，按回车确认。
此时，程序会把平衡二叉树展示出来，然后提示用户输入要删除的元素， 假如我们要添加5，输入5，按回车。

6. 此时提示添加失败，是因为5重复了，假如我们重新添加，选择功能3， 此时添加8，按回车，得到如下：

7. 提示添加成功，此时我们再此时删除功能，我们选择功能4，得到如下 界面，假如我们要删除4，输入4，按回车：

8. 得到界面如下，提示删除成功，我们发现平衡二叉树更新了，每个节 点的平衡因子也更新了。
9.我们再输入5，测试查找功能。提示输入查找元素，我们输入6。

10. 程序便把原来的平衡二叉树和以查找结点为根节点的子树都输出来。 此时我们再运行合并平衡二叉树的功能。选择6，回车。

11. 此时系统提示我们输入第一棵树的序列，假如我们输入1 2 3 4 5
然后系统会提示我们输入第二棵树的序列，假如我们输入 7 8 9

12. 程序会把T1 T2 T3用括号表示法输出
13. 此时提示按回车会输出要合并的两棵树和合并后的树的凹入表

14. 我们再输入7来此时分裂一棵平衡二叉树的功能

15. 此时提示我们输入树的序列，输入完将提示我们输入x的值，即树T将分裂成一棵均是小于等于x的树，和一棵均大于x的树。假如我们测试数据是：
T: 1 2 3 4 5 6 7 8 9 10 x:5
此时输出的是：

16. 最后便是退出功能，选择8，程序提示我们是否退出，
输入Y（y）退出程序，输入N（n）返回主界面

六、 测试结果
测试数据：
平衡二叉树T: 1 2 3 4 5 6 7 8 9 10
添加元素：11
删除元素：5
查找元素：8

添加11

删除8

测试数据
T1：5 8 4 10 62 T2：5 6 20 34
合并两树得到：

测试数据
T: -20 80 90 1 0 6 8 x :5
分裂平衡二叉树得到：

七、 附录
源程序文件名清单：
dataStruction.cpp //源程序代码
AVL_head.h //自定义的头文件
平衡二叉树的演示.exe//可执行文件

源码下载地址：