平衡二叉排序树的综合操作.cpp

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的左子树作左旋平衡处理