Abo

数据结构课程设计-平衡二叉树

当年的数据结构课程设计-平衡二叉树,想了想还是放上来吧,当初费尽心思,怕是如今都已看不懂了இ௰இ


write-593333_1280

“那片笑声让我想起我的那些花儿,在我生命每个角落静静为我开着~”


        

需求分析

“平衡二叉树操作演示”系统是利用平衡二叉树实现一个动态查找表的三种基本功能:查找、插入和删除,同时,还能拓展实现新的功能:初始化、求深度、求最大最小结点、先中后序及层序遍历、打印平衡二叉树、判空、合并和分裂平衡二叉树等功能,并通过括号表示方法和凹入表表示方法将动态查找表和平衡二叉树的详细信息展示给用户知晓;同时,还要求系统界面设计简洁明了、用户操作简单方便,提高系统实用性与运行效率。

说明:使用anyview或者codeblock运行;输入值形式是数字,无论对功能的选则还是对数据的录入,都是以数字的形式进行输入,如若超过规定范围程序将直接结束。

概要设计

接口设计

Status InitBBST(BBSTree &T)

初始化平衡二叉树

void DestroyBBSTree(BBSTree &T)

销毁平衡二叉树

Status BBSTreeEmpty(BBSTree T)

判空平衡二叉树

void PrintTree(BBSTree &T)

打印平衡二叉树

void CreateBBST(BBSTree &T)

输入结点数目,动态创建一棵平衡二叉树

Status InsertAVL(BBSTree &T, RcdType e, Status &taller)

平衡二叉树的插入操作,将e插入到T中

插入成功返回TRUE,失败返回FALSE

Status DeleteAVL(BBSTree &t, RcdType e, Status &shorter)

平衡二叉树的删除操作,将e从T中删除

删除成功返回TRUE,失败返回FALSE

void L_Rotate(BBSTree &p)

对p左旋操作

void R_Rotate(BBSTree &p)

对p右旋操作

void LeftBalance(BBSTree &T)

对T左平衡操作

void RightBalance(BBSTree &T)

对T右平衡操作

Status PreOrder(BBSTree T)

递归先序遍历输出

Status InOrder(BBSTree T)

递归中序遍历输出

Status PostOrder(BBSTree T)

递归后序遍历输出

void PreOrderTravese_I(BBSTree T)

非递归先序遍历输出

void InOrderTraverse_I(BBSTree T)

非递归中序遍历输出

void LastOrderTravese_I(BBSTree T)

非递归后序遍历输出

void LevelOrederTraverse_Print(BBSTree T)

层次遍历输出

BBSTree SearchBBST(BBSTree T,RcdType key)

二叉平衡树查找的递归实现

BBSTree SearchBBST_I(BBSTree T,RcdType e)

二叉平衡树查找的非递归实现

BBSTree FindMin(BBSTree T)

寻找平衡二叉树最小元素所在结点地址

BBSTree FindMax(BBSTree T)

寻找平衡二叉树最大元素所在结点地址

int BBSTreeDepth(BBSTree T)

求平衡二叉树的深度

void MergeBBST(BBSTree &T1, BBSTree T2)

合并两棵平衡二叉树

void SpiltBBST(BBSTree T, RcdType key, BBSTree &T1, BBSTree &T2)

按关键值key分裂T成两棵二叉树

主程序与各接口函数的调用

int main(){

​ BBSTree T = NULL;

​ int choice;

​ printf(“================================================\n”);

​ printf(“*平衡二叉树*\n”);

​ printf(“================================================\n”);

​ printf(“ 1:创建一棵平衡二叉树\n”);

​ printf(“ 2:平衡二叉树的插入\n”);

​ printf(“ 3:平衡二叉树的删除\n”);

​ printf(“ 4:平衡二叉树的查找\n”);

​ printf(“ 5:平衡二叉树的遍历\n”);

​ printf(“ 6:求平衡二叉树的深度\n”);

​ printf(“ 7:合并平衡二叉树\n”);

​ printf(“ 8:分裂平衡二叉树\n”);

​ printf(“ 请根据上述说明选择所需操作1-8: “);

​ scanf(“%d”,&choice);

​ while(choice > 0 && choice <= 3)

​ {

​ if(choice == 1)

​ {

​ if(OK == InitBBST(T));

​ CreateBBST(T);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T,0);

​ printf(“\n”);

​ PrintTree1(T);

​ printf(“\n请重新输入你的选择: “);

​ scanf(“%d”,&choice);

​ }

​ if(choice == 2)

​ {

​ int num;

​ RcdType s;

​ Status taller = TRUE;

​ printf(“请输入要插入的元素:”);

​ scanf(“%d”,&num);

​ s = num;

​ InsertAVL(T,s,taller);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T,0);

​ PrintTree1(T);

​ printf(“\n请重新输入你的选择: “);

​ scanf(“%d”,&choice);

​ }

​ if(choice == 3){

​ RcdType e;

​ Status shorter = TRUE;

​ printf(“请输入要删除的元素:”);

​ scanf(“%d”,&e);

​ DeleteAVL(T, e, shorter);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T,0);

​ PrintTree1(T);

​ printf(“\n请重新输入你的选择: “);

​ scanf(“%d”,&choice);

​ }

​ }

​ if(choice == 4){

​ int choice2;

​ printf(“40:递归查找\n41:非递归查找\n”);

​ printf(“42:查找最小元素\n43:查找最大元素\n”);

​ printf(“请选择一种查找方式:”);

​ scanf(“%d”,&choice2);

​ switch(choice2){

​ case 40:

​ int key1;

​ printf(“\n请输入欲查找元素:”);

​ scanf(“%d”,&key1);

​ if(NULL != SearchBBST(T,key1))

​ printf(“\n查找成功”);

​ else

​ printf(“\n查找失败”);

​ break;

​ case 41:

​ int key2;

​ printf(“\n请输入欲查找元素:”);

​ scanf(“%d”,&key2);

​ if(NULL != SearchBBST_I(T,key2))

​ printf(“\n查找成功”);

​ else

​ printf(“\n查找失败”);

​ break;

​ case 42:

​ BBSTree T1 = FindMin(T);

​ if(T1)

​ printf(“\n查找成功,且为%d”,T1->data);

​ break;

​ // case 43:

​ BBSTree T2 = FindMax(T);

​ if(T2)

​ printf(“\n查找成功,且为%d”,T2->data);

​ break;

​ }

​ }

​ if(choice == 5){

​ int choice2;

​ printf(“50:递归先序\n51:递归中序\n52:递归后序\n”);

​ printf(“53:非递归先序\n54:非递归中序\n55:非递归后序\n56:层次遍历\n”);

​ printf(“请选择一种遍历方式:”);

​ scanf(“%d”,&choice2);

​ switch(choice2){

​ case 50:

​ printf(“\n递归先序遍历输出:”);

​ PreOrder(T); break;

​ case 51:

​ printf(“\n递归中序遍历输出:”);

​ InOrder(T); break;

​ case 52:

​ printf(“\n递归后序遍历输出:”);

​ PostOrder(T);break;

​ case 53:

​ printf(“\n非递归先序遍历输出:”);

​ PreOrderTravese_I(T);break;

​ case 54:

​ printf(“\n非递归中序遍历输出:”);

​ InOrderTraverse_I(T); break;

​ case 55:

​ printf(“\n非递归后序遍历输出:”);

​ LastOrderTravese_I(T);

​ printf(“\n”); break;

​ case 56:

​ printf(“\n层次遍历输出:”);

​ LevelOrederTraverse_Print(T);

​ printf(“\n”); break;

​ }

​ }

​ if(choice == 6)

​ {

​ printf(“深度为:%d\n”,BBSTreeDepth(T));

​ }

​ if(choice == 7)

​ {

​ BBSTree T1,T2,T3;

​ if(OK == (InitBBST(T1))&&(InitBBST(T2))&&(InitBBST(T)))

​ {

​ printf(“请构造第一棵子树\n”);

​ CreateBBST(T1);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T1,0);

​ PrintTree1(T1);

​ printf(“\n”);

​ printf(“请构造第二棵子树\n”);

​ CreateBBST(T2);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T2,0);

​ PrintTree1(T2);

​ printf(“\n”);

​ printf(“合并后为:”);

​ MergeBBST(T,T1);

​ MergeBBST(T,T2);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T,0);

​ PrintTree1(T);

​ }

​ }

​ if(choice == 8)

​ {

​ BBSTree T1,T2;

​ if(OK == (InitBBST(T1))&&(InitBBST(T2)))

​ {

​ int x;

​ printf(“请输入要分裂时作为参照的关键字:”);

​ scanf(“%d”,&x);

​ SpiltBBST(T,x,T1,T2);

​ printf(“分裂后的第一棵树为:”);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T1,0);

​ PrintTree1(T1);

​ printf(“\n”);

​ printf(“分裂后的第二棵树为:”);

​ printf(“平衡二叉树表示为:\n”);

​ PrintTree(T2,0);

​ PrintTree1(T2);

​ }

​ }

}

详细设计

以下高能代码段,慎看吧(╯‵□′)╯炸弹!•••*~●

重要变量和存储结构定义

#include <stdio.h>

#include <stdlib.h>

#define LH +1 //左高

#define EH 0 //等高

#define RH -1 //右高

#define FALSE 0

#define TRUE 1

#define OK 1

#define ERROR 0

#define OVERFLOW -1

typedef int Status;

typedef int RcdType;

/平衡二叉树结构体/

typedef struct BBSTNode {

​ RcdType data;

​ int bf;

​ struct BBSTNode lchild, rchild;

}*BBSTree;

算法设计

/初始化平衡二叉树/

Status InitBBST(BBSTree &T){

​ T = NULL;

​ return OK;

}

/销毁平衡二叉树/

void DestroyBBSTree(BBSTree &T){

​ if(T != NULL){

​ DestroyBBSTree(T -> lchild);

​ DestroyBBSTree(T -> rchild);

​ free(T);

​ T = NULL;

​ }

}

/判空平衡二叉树/

Status BBSTreeEmpty(BBSTree T){

​ if(!T){

​ return TRUE;

​ }

​ else{

​ return FALSE;

​ }

}

/创建一棵平衡二叉树/

void CreateBBST(BBSTree &T)

{

​ RcdType e;

​ int num;

​ Status taller = TRUE;

​ printf(“\n请输入平衡二叉树的结点个数:”);

​ scanf(“%d”, &num);

​ getchar();

​ printf(“请顺序输入元素(按’回车键’结束):”);

​ for (int i = 0; i < num; i++) {

​ scanf(“%d”, &e);

​ InsertAVL(T, e, taller);

​ }

}

/输出平衡二叉树/

void PrintTree(BBSTree T, int nLayer){

​ if(T == NULL) {

​ return;

​ }

​ PrintTree(T->rchild, nLayer + 4);

​ for(int i = 0; i < nLayer; i++) {

​ printf(“ “);

​ }

​ printf(“%d\n”, T->data);

​ PrintTree(T->lchild, nLayer + 4);

}

/输出平衡二叉树/

void PrintTree1(BBSTree &T)

{

​ if(T)

​ {

​ printf(“%d”,T->data);

​ if(T->lchild || T->rchild)

​ {

​ printf(“(“);

​ PrintTree1(T->lchild);

​ if(T->rchild)

​ printf(“,”);

​ PrintTree1(T->rchild);

​ printf(“)”);

​ }

​ }

}

/平衡二叉树的插入操作/

/若平衡二叉树中不存在值为e的结点,则插入到T/

Status InsertAVL(BBSTree &T, RcdType e, Status &taller){

​ if(NULL==T){

​ T = (BBSTree)malloc(sizeof(BBSTNode));

​ T->data = e;

​ T->bf = EH;

​ T->lchild = NULL;

​ T->rchild = NULL;

​ }else if(e==T->data){ //书中已存在和e相等的结点

​ taller = FALSE; return FALSE;

​ }else if(edata){

​ if(FALSE==InsertAVL(T->lchild, e, taller)) 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, taller)) 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;

}

/左旋调整(右旋与之类似,不再列出)/

void L_Rotate(BBSTree &p) {

​ BBSTree rc = p -> rchild;

​ p -> rchild = rc -> lchild;

​ rc -> lchild = p;

​ p = rc;

}

/左平衡处理操作(右平衡与之类似,不再列出)/

void LeftBalance(BBSTree &T){

​ BBSTree lc, rd;

​ lc = T->lchild;

​ switch(lc->bf){

​ case LH:

​ T->bf = lc->bf = EH; R_Rotate(T); break;

​ case RH:

​ rd = lc->rchild;

​ switch(rd->bf){

​ case LH: T->bf = RH; lc->bf = EH; break;

​ case EH: T->bf = lc->bf = EH; break;

​ case RH: T->bf = EH; lc->bf = LH; break;

​ }

​ rd->bf = EH;

​ L_Rotate(T->lchild);

​ R_Rotate(T);

​ break;

​ }

}

/平衡二叉树的删除操作/

/平衡二叉树中存在值为key的结点,则删除/

Status DeleteAVL(BBSTree &T, RcdType e, Status &shorter){

//当被删结点是有两个孩子,且其前驱结点是左孩子时,tag=1

​ 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(edata){ //左子树中继续查找

​ 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;

}

/二叉平衡树查找的递归实现/

/若平衡二叉树中存在值为key的结点,则返回该结点指针,否则返回NULL/

BBSTree SearchBBST(BBSTree T,RcdType key) {

​ if(NULL == T)

​ return NULL;

​ if(T -> data == key)

​ return T;

​ if(T -> data > key)

​ return SearchBBST(T -> lchild,key);

​ return SearchBBST(T -> rchild,key);

}

/二叉平衡树查找的非递归实现/

/若平衡二叉树中存在值为key的结点,则返回该结点指针,否则返回NULL*/

BBSTree SearchBBST_I(BBSTree T,RcdType e) {

​ while(T) {

​ if(e < T -> data)

​ T = T -> lchild;

​ else if(e > T -> data)

​ T = T -> rchild;

​ else

​ return T;

​ }

​ return NULL;

}

/寻找平衡二叉树最小元素所在结点地址(寻找最大元素类似不再列出)/

BBSTree FindMin(BBSTree T){

​ if(T)

​ while(T -> lchild)

​ T = T -> lchild;

​ return T;

}

/递归先序遍历(中序、后序遍历类似不再列出)/

Status PreOrder(BBSTree T){

​ if(T) {

​ printf(“%5d”,T->data);

​ PreOrder(T -> lchild);

​ PreOrder(T -> rchild);

​ }

​ return OK;

}

/非递归中序遍历/

void InOrderTraverse_I(BBSTree T){

​ LStack S;

​ InitStack_LS(S);

​ BBSTree p = NULL;

​ p = GoFarLeft(T, S);

​ while(p!=NULL){

​ printf(“%d “,p->data);

​ if(p->rchild!=NULL){

​ p = GoFarLeft(p->rchild, S);

​ }

​ else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S, p);

​ else p = NULL;

​ }

}

/非递归先序遍历/

void PreOrderTravese_I(BBSTree T){

​ LStack S;

​ InitStack_LS(S);

​ BBSTree p;

​ p = VisitFarLeft(T, S); //先将左边的数据先序读取

​ while(p!=NULL){

​ if(p->rchild!=NULL) //如果最左下结点的右子树不为空

​ p = VisitFarLeft(p->rchild, S); //执行遍历该结点的左子树

​ else if(StackEmpty_LS(S)!=TRUE) Pop_LS(S,p); //如果S不为空栈,出栈

​ else p = NULL; //如果为空栈,p赋予空

​ }

}

/非递归后序遍历/

void LastOrderTravese_I(BBSTree root){

​ BBSTree p = root;

​ BBSTree stack[30];

​ int num=0;

​ BBSTree have_visited = NULL;

​ while(NULL!=p||num>0){

​ while(NULL!=p){

​ stack[num++]=p;

​ p=p->lchild;

​ }

​ p=stack[num-1];

​ if(NULL==p->rchild||have_visited==p->rchild){

​ printf(“%d “,p->data);

​ num–;

​ have_visited=p;

​ p=NULL;

​ }

​ else{

​ p=p->rchild;

​ }

​ }

​ printf(“\n”);

}

/层次遍历/

void LevelOrederTraverse_Print(BBSTree T){

​ if(T==NULL){

​ printf(“这是一棵空树!”);

​ }

​ if(T!=NULL){

​ LQueue Q;

​ InitQueue_LQ(Q);

​ BBSTree p = T;

​ printf(“%d “,p->data); EnQueue_LQ(Q,p);//首先访问根结点,并将根节点入队

​ while(DeQueue_LQ(Q,p)){ //队非空时重复操作,出队

​ if(p->lchild!=NULL){ //访问左孩子并入队

​ printf(“%d “, p->lchild->data);

​ EnQueue_LQ(Q, p->lchild);

​ }

​ if(p->rchild!=NULL){ //访问右孩子并入队

​ printf(“%d “, p->rchild->data);

​ EnQueue_LQ(Q, p->rchild);

​ }

​ }

​ }

}

/求平衡二叉树的深度/

int BBSTreeDepth(BBSTree T){

​ int depthLeft, depthRight;

​ if(NULL==T) return 0;

​ else{

​ depthLeft = BBSTreeDepth(T->lchild);

​ depthRight = BBSTreeDepth(T->rchild);

​ return 1+(depthLeft > depthRight ? depthLeft : depthRight);

​ }

}

/合并平衡二叉树/

void MergeBBST(BBSTree &T1, BBSTree T2) {

​ Status taller = FALSE;

​ if (T2 != NULL) {

​ MergeBBST(T1, T2->lchild);

​ InsertAVL(T1, T2->data, taller);

​ MergeBBST(T1, T2->rchild);

​ }

}

/分裂平衡二叉树/

void SpiltBBST(BBSTree T, RcdType key, BBSTree &T1, BBSTree &T2) {

​ Status taller = FALSE;

​ if (T != NULL) {

​ SpiltBBST(T->lchild, key, T1, T2); // 递归访问左子树

​ if(T->data > key) {

​ InsertAVL(T1, T->data, taller);

​ } else {

​ InsertAVL(T2, T->data, taller);

​ }

​ SpiltBBST(T->rchild, key, T1, T2);

​ }

}

调试分析

调试过程中遇到的问题及处理方法

一开始运行过程中程序停止运行。遇到这个情况一开始我以为是编译器有问题,但是换了个编译器还是同样的问题,后来我上网查询了有关资料,大概明白了是自己的代码出现了问题。所以只能将新增的代码注释掉,一条一条测试,调试过程很漫长,最后才发现是内存泄露和空指针异常,将指针不适用之后指向为 NULL,才把问题解决了。

算法改进与设想

在对动态查找表的查找方式上,课程设计选择的是平衡二叉树,那么当查找的结点元素与关键字数量庞大的时候,就会造成平衡二叉树的高度过高,查找、添加、删除等操作的时候效率就会变得很低,而且输入后的排序与整合平衡二叉树T所需要用到的时间就会很长,所以,如果动态查找表中的元素数量庞大的时候可以优先选择B树和B+树等,可以有效降低查找树的高度,提高查找处理效率。

经验与体会

本次课程设计主要实现平衡二叉树的查找,插入和删除,增加合并和分裂的功能。许多接口的实现都是基于之前二叉树等的操作,根据平衡二叉树的特性进行改动和完善,删除的难点在于找待删除点的前驱结点和删除后对失衡情况的调节.合并和分裂平衡二叉树,一开始我是想用一个数组先把元素汇总再进行创建新的平衡二叉树,但查阅资料后,觉得这一种方法有些死板,不及直接递归访问结点元素并进行插入操作。总结来说,平衡二叉树是一种基于二叉树的抽象数据类型,平衡这一特性,给一些基本操作增加了不小的难度,值得去思考和研究。

在做一个比较大的程序过程中,应该学会边编写程序边运行,即当你完成了一个比较小的功能时便对其调试, 这样有助于我们高效地完成项目,而且在调试 BUG 的过程也可以大大减小其难度。必须要有良好的编程习惯。首先编码风格一定要规范,这样不仅有利于读者和编程者对代码的阅读,更有利于对代码的维护。其次要对代码要细心,比较一些指针的初始化和不需要时指为空,这些都是可以极大减少我们出现 BUG 的几率