经典数据结构算法c++源码

//* * * * * * * * * * * * * * * * * * * * * * * * //*CHAPTER :6 (6_5) * //*PROGRAM :平衡二叉排序树的综合操作 * //*CONTENT :Insert,Search * //* * * * * * * * * * * * * * * * * * * * * * * * #include <dos.h> #include <conio.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #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(key<T->data.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.keynum<T->data.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; }