C++二叉排序树

一大块，都给你了，功能都有了~~

你自己看看吧~~希望能帮到你~~尽力了~~

//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER :6 (6_5) *
//*PROGRAM :平衡二叉排序树的综合操作 *
//*CONTENT :Insert,Search *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include
#include
#include
#include
#include
#define LH 1 //左子树高
#define EH 0 //左右子树等高
#define RH -1 //右子树高
enum BOOL{False,True};
typedef struct //定义记录的结构
{int keynum; //在本程序中只含有关键字一项
}Record;
typedef struct BSTNode //定义平衡二叉树节点结构
{Record data; //数据域
int bf; //平衡因子
struct BSTNode *lchild,*rchild; //左右孩子指针域
}BSTNode,*BSTree;
BSTree SearchBST(BSTree,int); //在平衡二叉排序树中查找元素
BOOL InsertAVL(BSTree &,Record,BOOL&); //在平衡二叉排序树中插入元素
void LeftBalance(BSTree &); //左平衡旋转处理
void RightBalance(BSTree &); //右平衡旋转处理
void InorderBST(BSTree); //中序遍历二叉排序树，即从小到大显示各元素
void R_Rotate(BSTree &); //右旋处理
void L_Rotate(BSTree &); //左旋处理
void main()
{BSTree T,p;
Record R;
char ch,keyword,j='y';
BOOL temp,taller;
textbackground(3); //设定屏幕颜色
textcolor(15);
clrscr();
//-------------------------程序说明-------------------------------
printf("This program will show how to operate to \na Balanced Binary Sort Tree.\n");
printf("You can display all elems,search a elem,insert a elem.\n");
//----------------------------------------------------------------
T=NULL;
while(j!='n')
{printf("1.display\n");
printf("2.search\n");
printf("3.insert\n");
printf("4.exit\n");
scanf(" %c",&ch); //输入操作选项
switch(ch)
{case '1':if(!T) printf("The BST has no elem.\n"); //此时平衡二叉排序树空
else {InorderBST(T);printf("\n");} //中序遍历二叉树，即从小到大显示所有元素
break;
case '2':printf("Input the keynumber of elem to be searched(int number):");
scanf("%d",&R.keynum); //输入要查找元素的关键字
p=SearchBST(T,R.keynum);
//p=NULL:查找不成功；p!=NULL:查找成功，p指向该记录
if(!p) printf("The record isn't existed!\n"); //没有找到
else printf("The record has been found!\n"); //成功找到
break;
case '3':printf("Input the record to be inserted(int number):");
scanf("%d",&R.keynum); //输入要插入元素的关键字
temp=InsertAVL(T,R,taller);
//temp=True:成功插入该记录;temp=False:树中已有与记录R有相同关键字的记录
if(!temp) printf("The record has been existed!\n"); //该元素已经存在
else printf("Sucess to insert!\n"); //成功插入
break;
default: j='n';
}
}
printf("The program is over!\nPress any key to shut off the window!\n");
getchar();getchar();
}
void InorderBST(BSTree T)
{//以中序方式遍历二叉排序树T，即从小到大显示二叉排序树的所有元素
if(T->lchild) InorderBST(T->lchild);
printf("%-4d",T->data.keynum);
if(T->rchild) InorderBST(T->rchild);
}

BSTree SearchBST(BSTree T,int key)
{//在根指针T所指二叉排序树中递归的查找其关键字等于key的元素，若查找成功
//则返回该元素的地址，若查找不成功，返回地址为NULL
if((!T)||key==T->data.keynum) return (T);
else if(keydata.keynum) return(SearchBST(T->lchild,key));
else return(SearchBST(T->rchild,key));
}

BOOL InsertAVL(BSTree &T,Record e,BOOL &taller)
{//若在平衡二叉排序树T中中不存在和e有相同关键字的结点，则插入一个数据元素
//为e的新结点，并返回True，否则返回False。若因插入而使平衡二叉排序树失去
//平衡，则做平衡旋转处理，布尔变量taller反映T长高与否
if(!T) //插入新结点，树“长高”，置taller为True
{T=(BSTree)malloc(sizeof(BSTNode));
T->data=e;
T->lchild=T->rchild=NULL;
T->bf=EH;
taller=True;
}
else
{if(e.keynum==T->data.keynum) //树中已有与e有相同关键字的结点
{taller=False; return False;} //不再插入
if(e.keynumdata.keynum) //应继续在*T的左子树中进行搜索
{if(!InsertAVL(T->lchild,e,taller)) return False; //未插入
if(taller) //已插入到*T的左子树中且左子树“长高”
switch(T->bf) //检查*T的平衡度
{case LH:LeftBalance(T); //原本左子树比右子树高，需要做左平衡处理
taller=False;
break;
case EH:T->bf=LH; //原本左右子树等高，现因左子树增高而使树增高
taller=True;
break;
case RH:T->bf=EH; //原本右子树比左子树高，现左右子树等高
taller=False;
break;
}
}
else //应继续在*T的右子树中进行搜索
{if(!InsertAVL(T->rchild,e,taller)) return False;//未插入
if(taller) //已插入到*T的右子树中且右子树“长高”
switch(T->bf) //检查*T的平衡度
{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 LeftBalance(BSTree &T)
{//对以指针T所指结点为根的二叉树做左平衡旋转处理，本算法结束时，
//指针T指向新的根结点
BSTree lc,rd;
lc=T->lchild; //lc指向*T的左子树根结点
switch(lc->bf) //检查*T的左子树的平衡度，并作相应平衡处理
{case LH:T->bf=lc->bf=EH; //新结点插入在*T的左孩子的左子树上，要作单右旋处理
R_Rotate(T);
break;
case RH: //新结点插入在*T的左孩子的右子树上，要作双旋处理
rd=lc->rchild; //rd指向*T的左孩子的右子树根
switch(rd->bf) //修改*T及其左孩子的平衡因子
{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); //对*T的左子树作左旋平衡处理?
R_Rotate(T); //对*T作右旋平衡处理
}
}
void RightBalance(BSTree &T)
{//对以指针T所指结点为根的二叉树做右平衡旋转处理，本算法结束时，
//指针T指向新的根结点
BSTree rc,ld;
rc=T->rchild; //rc指向*T的右子树根结点
switch(rc->bf) //检查*T的右子树的平衡度，并作相应平衡处理
{case LH: //新结点插入在*T的右孩子的左子树上，要作双旋处理
ld=rc->lchild; //ld指向*T的右孩子的左子树根
switch(ld->bf) //修改*T及其右孩子的平衡因子
{case LH:T->bf=EH;rc->bf=RH;break;
case EH:T->bf=rc->bf=EH;break;
case RH:T->bf=LH;rc->bf=EH;break;
}
ld->bf=EH;
R_Rotate(T->rchild); //对*T的右子树作右旋平衡处理?
L_Rotate(T); //对*T作左旋平衡处理
break;
case RH:T->bf=rc->bf=EH; //新结点插入在*T的右孩子的右子树上，要作单左旋处理
L_Rotate(T);
}
}

void L_Rotate(BSTree &p)
{//对以*p为根的二叉排序树作左旋处理，处理之后p指向新的根结点，即旋转处理
//之前的右子树的根结点
BSTree rc;
rc=p->rchild; //rc指向p右子树根结点
p->rchild=rc->lchild; //rc的左子树挂接为p的右子树
rc->lchild=p; //p指向新的根结点
p=rc;
}
void R_Rotate(BSTree &p)
{//对以*p为根的二叉排序树作右旋处理，处理之后p指向新的根结点，即旋转处理
//之前的左子树的根结点
BSTree lc;
lc=p->lchild; //lc指向p左子树根结点
p->lchild=lc->rchild; //lc的右子树挂接为p的左子树
lc->rchild=p; //p指向新的根结点
p=lc;
}