大二的最后一个作业，等明天再过去答辩完后，我的大二也就基本告一段落。这次的课设没有怎么用心，所以也基本就是应付式的完成的，不过其中还是有挺多东西可以学的，香港空间，因此就趁着刚写完，认真整理一下，方便以后学习。
接下进入正题
题目要求
利用平衡二叉树实现一个动态查找表
（1） 实现动态查找表的三种基本功能：查找，插入和删除；
（2） 合并两棵平衡二叉树；
（3） 把一棵平衡二叉树分裂成两棵平衡二叉树，使得在一棵树中的所有关键字都小于多等于X，另一棵树中的任一关键字都大于X。
完成说明
课设是基于c/c++语言编写的，开发平台选择的是vc6.0。（汗，我到现在都还只会用vc，当然也用过TC，不过那个古董级的真心用不惯），另外c语言也没学过界面，所以就只能用dos，凑合着看吧。
概要设计
typedef int Status;
typedef int ElemType;
typedef struct BSTNode{
ElemType data;
int bf;
struct BSTNode *lchild ,*rchild;
} BSTNode,* BSTree;
Status SearchBST(BSTree T,ElemType e)//查找
void R_Rotate(BSTree &p)//右旋
void L_Rotate(BSTree &p)//左旋
void LeftBalance(BSTree &T)//插入平衡调整
void RightBalance(BSTree &T)//插入平衡调整
Status InsertAVL(BSTree &T,ElemType e,int &taller)//插入
void DELeftBalance(BSTree &T)//删除平衡调整
void DERightBalance(BSTree &T)//删除平衡调整
Status Delete(BSTree &T,int &shorter)//删除操作
Status DeleteAVL(BSTree &T,ElemType e,int &shorter)//删除操作
void merge(BSTree &T1,BSTree &T2)//合并操作
void splitBSTree(BSTree T,ElemType e,BSTree &T1,BSTree &T2)//分裂操作
void PrintBSTree(BSTree &T,int lev)//凹入表显示
接下来附上所有源码
#include<stdio.h>#include<stdlib.h>//#define TRUE 1//#define FALSE 0//#define OK 1//#define ERROR 0#define LH +1#define EH 0#define RH -1
typedef int Status;typedef int ElemType;typedef struct BSTNode{ElemType data;int bf;struct BSTNode *lchild ,*rchild;} BSTNode,* BSTree;
/*查找算法*/Status SearchBST(BSTree T,ElemType e){if(!T){return FALSE; //查找失败}else if(e == T->data ){return TRUE; //查找成功}else if (e < T->data){return SearchBST(T->lchild,e);}else{return SearchBST(T->rchild,e);}}
//右旋void R_Rotate(BSTree &p){BSTree lc;lc = p->lchild;p->lchild = lc->rchild;lc->rchild = p;p = lc;
}//左旋void L_Rotate(BSTree &p){BSTree rc;rc = p->rchild;p->rchild = rc->lchild;rc->lchild = p;p = rc;}
void LeftBalance(BSTree &T){BSTree 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);} }
void RightBalance(BSTree &T) { BSTree rc,ld; rc=T->rchild; switch(rc->bf){ case RH: T->bf= rc->bf=EH; L_Rotate(T); break; case LH: ld=rc->lchild; switch(ld->bf){ case LH: T->bf=RH; rc->bf=EH; break; case EH: T->bf=rc->bf=EH; break; case RH: T->bf = EH; rc->bf=LH; break; } ld->bf=EH; R_Rotate(T->rchild); L_Rotate(T); } } //插入结点Status InsertAVL(BSTree &T,ElemType e,int &taller){if(!T){T= (BSTree) malloc (sizeof(BSTNode));T->data = e;T->lchild = T->rchild = NULL;T->bf = EH;taller = 1;}else{if(e == T->data){taller = 0;return ERROR;}if(e < T->data){if(!InsertAVL(T->lchild,e,taller))return ERROR;if(taller)switch(T->bf){case LH:LeftBalance(T);taller = 0;break;case EH:T->bf = LH;taller = TRUE;break;case RH:T->bf = EH;taller = FALSE;break;}}else{if (!InsertAVL(T->rchild,e,taller)){return ERROR;}if(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 1;}void DELeftBalance(BSTree &T){BSTree lc,rd; lc=T->lchild;switch(lc->bf){ case LH: T->bf = EH; //lc->bf= EH;R_Rotate(T);break; case EH: T->bf = EH; 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);} }
从起点，到尽头，也许快乐，或有时孤独，
