main.cpp

马踏棋盘和平衡树算法的演示,数据结构的课程设计,两个

#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
#include<iostream.h>



#define LH +1//左高
#define EH  0//等高
#define RH -1//右高

//函数结果状态代码
#define TRUE  1
#define FALSE 0
#define OK    1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW   -2
//Status是函数的类型,其值是函数结果状态代码
typedef int Status;
typedef char KeyType;

typedef struct {
	KeyType key;//关键字域
}ElemType;


//二叉排序树的类型定义:
typedef struct BSTNode{
	ElemType data;
	int      bf;
	// 平衡因子
	struct BSTNode *lchild,*rchild;
}BSTNode,*BSTree;


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) ;
// 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，
  // 则插入一个数据元素为e的新结点
Status EQ(KeyType a,KeyType b);
Status LT(KeyType a,KeyType b);
Status LQ(KeyType a,KeyType b);
Status PrintAVL(BSTree T,int i);
//打印平衡二叉树
void SearchAVL(BSTree T,KeyType e);
//对平衡二叉树进行查找操作
Status DeleteAVL(BSTree T,BSTree &CT,KeyType key);
//对平衡二叉树进行删除操作
Status SplitAVL(BSTree T,BSTree &LT,BSTree &GT,KeyType key);
//拆分平衡二叉树
Status MergeAVL(BSTree &T,BSTree TT);
//合并平衡二叉树
void menu();
//菜单

void main()
{
	BSTree T,CT,GT,LT;
	T=NULL;
	//初始化
	int taller=0,shorter=1;
	KeyType key; 
	menu();
	int i;
	scanf("%d",&i);
	while(i!=6)
	{
		switch(i)
		{
		case 1:	
			ElemType e;
			system("cls");
			printf("\n原平衡二叉树:\n");
			PrintAVL(T,0);
			printf("\n请输入要插入的关键字:\n");
			scanf(" %c",&key);
			e.key=key;
			InsertAVL(T,e,taller);
			//插入操作
			printf("\n插入后平衡二叉树:\n");
			PrintAVL(T,0);
			break;
		case 2:
			system("cls");
			printf("\n请输入要查找的关键字:");
			scanf(" %c",&key);
			printf("\n原平衡二叉树:\n");
			PrintAVL(T,0);
			system("pause");
			SearchAVL(T,key);
			break;
		case 3:
			CT=NULL;
			printf("\n原平衡二叉树:\n");
			PrintAVL(T,0);
			printf("\n请输入要删除的关键字:");
			scanf(" %c",&key);
			DeleteAVL(T,CT,key);
			T=CT;
			printf("\n删除后平衡二叉树:\n");
			PrintAVL(T,0);
			break;
		case 4:
			GT=LT=NULL;	
			printf("\n原平衡二叉树:\n");
			PrintAVL(T,0);
			printf("\n请输入拆分的关键字:");
			scanf(" %c",&key);
			SplitAVL(T,LT,GT,key);
			printf("\n小于或等于该关键字的平衡二叉树\n");
			PrintAVL(GT,0);
			printf("大于该关键字的平衡二叉树\n");
			PrintAVL(LT,0);
			break;
		case 5:
			BSTree t,tt;
			t=tt=NULL;
			printf("\n平衡二叉树LT:\n");
		    PrintAVL(LT,0);
			printf("\n平衡二叉树GT:\n");
			PrintAVL(GT,0);
			printf("\n合并平衡二叉树GT和LT:\n");
			MergeAVL(LT,GT);
			PrintAVL(LT,0);
			break;
		}
		system("pause");
		system("cls");
		menu();
		scanf(" %d",&i);
	}
}



void menu()
//主菜单
{
	printf("                            平衡二叉树操作演示                          ");
	printf("\n          *********************************************************** ");
	printf("\n          |                    1.插入 		                    |   "); 	
	printf("\n          |                    2.查找                               | ");
	printf("\n          |                    3.删除                               | ");
	printf("\n          |                    4.拆分                               | "); 
	printf("\n          |                    5.合并                               | ");
	printf("\n          |                    6.退出                               | ");  
	printf("\n          | 制作人:陈平锋 学号:2003040140204 计算机科学与技术(02)班 | ");
	printf("\n          ***********************************************************\n");
	printf("\n请输入操作序号：");
}


Status LQ(KeyType a,KeyType b)
{
	if(a<=b) return TRUE;
	else return FALSE;
}

Status LT(KeyType a,KeyType b)
{
	if(a<b) return TRUE;
	else return FALSE;
}

Status EQ(KeyType a,KeyType b)
{
	if(a==b) return TRUE;
	else return FALSE;
}

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


void L_Rotate(BSTree &p) {  // 算法 9.10
  // 对以p↑为根的二叉排序树作左旋处理，处理之后p指向新的树根结点，
  // 即旋转处理之前的右子树的根结点
  BSTree rc;
  rc = p->rchild;            
  // rc指向*p的右子树根结点
  p->rchild = rc->lchild;    
  // rc的左子树挂接为*p的右子树
  rc->lchild = p;  p = rc;   
  // p指向新的根结点
} // L_Rotate
                             
void SearchAVL(BSTree T,KeyType e)
{
	if(T)
	{
		if(EQ(e,T->data.key))
			// 树中已存在和e有相同关键字的结点
		{
			printf("\n平衡二叉树存在该关键字!\n\n\n");
			return ;
		}
	
		if(LT(e,T->data.key))
			// 应继续在*T的左子树中进行搜索
			SearchAVL(T->lchild,e);
		else
			// 应继续在T↑的右子树中进行搜索
			SearchAVL(T->rchild,e);
	}
	else
		printf("\n平衡二叉树不存在该关键字!\n\n\n");
}


Status InsertAVL(BSTree &T, ElemType e, int &taller) { // 算法9.11
  // 若在平衡的二叉排序树T中不存在和e有相同关键字的结点，
  // 则插入一个数据元素为e的新结点，并返回1，否则返回0。
  // 若因插入而使二叉排序树失去平衡，则作平衡旋转处理，
  // 布尔变量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 (EQ(e.key, T->data.key))   
		// 树中已存在和e有相同关键字的结点
      { taller = FALSE; printf("\n该关键字已经存在!"); return 0; } 
	// 则不再插入
    if (LT(e.key, T->data.key)) {   
		// 应继续在*T的左子树中进行搜索
      if (InsertAVL(T->lchild, e, taller)==0) return 0;  
	  // 未插入
      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;   
        } // switch (T->bf)
    } // if
    else {    
		// 应继续在T↑的右子树中进行搜索
      if (InsertAVL(T->rchild, e, taller)==0) return 0;
      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;
        } // switch (T->bf)
    } // else
  } // else 
  return 1;
} //InsertAVL


void LeftBalance(BSTree &T) {  // 算法 9.12
  // 对以指针T所指结点为根的二叉树作左平衡旋转处理。
  // 本算法结束时，指针T指向新的根结点
  BSTree lc,rd;
  lc = T->lchild;    
  // lc指向*T的左子树根结点
  switch (lc->bf) {  
	  // 检查*T的左子树的平衡度，并作相应平衡处理
    case LH:   
		// 新结点插入在*T的左孩子的左子树上，要作单右旋处理
        T->bf = lc->bf = EH; 
        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;
        } // switch (rd->bf)
        rd->bf = EH;              
        L_Rotate(T->lchild);  
		// 对*T的左子树作左旋平衡处理
        R_Rotate(T);          
		// 对*T作右旋平衡处理
  } // switch (lc->bf) 
} // LeftBalance


void RightBalance(BSTree &T)
// 对以指针T所指结点为根的二叉树作右平衡旋转处理。
  // 本算法结束时，指针T指向新的根结点
{
	BSTree lc,ld;
	lc=T->rchild;
	// lc指向*T的右子树根结点
	switch(lc->bf){
		// 检查*T的右子树的平衡度，并作相应平衡处理
		case RH:
			T->bf = lc->bf = EH; 
			L_Rotate(T);   
			 break; 
		case LH:
			// 新结点插入在*T的右孩子的左子树上，要作双旋处理
			ld=lc->lchild;
			//ld指向*T的右孩子的左子树根
			switch(ld->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;
			}//swithc(ld->bf)
			ld->bf=EH;
			R_Rotate(T->rchild);
			// 对*T的右子树作右旋平衡处理
			L_Rotate(T);		
			// 对*T作左旋平衡处理
	}//switch(lc->bf)
}//RightBalance

Status DeleteAVL(BSTree T,BSTree &CT,KeyType key)
//删除关键字key
{
	int taller;
	if(T)
	{
		if(T->data .key !=key)
			//将不和key相等的关键字插入到平衡二叉树CT中去
			InsertAVL(CT,T->data,taller);
		DeleteAVL(T->lchild ,CT,key);
		DeleteAVL(T->rchild ,CT,key);
	}
	return OK;
}

Status PrintAVL(BSTree T,int i)
{
	if(!T)
		printf("\n该平衡二叉树为空树!\n");
	else
	{
	if(T->rchild) 
		PrintAVL(T->rchild,i+1);
	for(int j=1;j<=i;j++) 
		printf("       "); 
	//打印i个空格以表示出层次
	printf("%c(%d)\n",T->data.key,T->bf); //打印T元素,换行
	if(T->lchild) 
	   PrintAVL(T->lchild,i+1);
	}
	return OK;
}// PrintAVL

Status SplitAVL(BSTree T,BSTree &LT,BSTree &GT,KeyType key)
//将平衡二叉树T拆分为平衡二叉LT和树平衡二叉树GT
{
	int taller;
	if(T)
		//如果平衡二叉树不空
	{	
		if(key<T->data.key)
			 InsertAVL(LT,T->data,taller);
		//将大于关键字的元素插入到LT中去
		else
			 InsertAVL(GT,T->data,taller);
		//将小于关键字的元素插入到LT中去
		SplitAVL(T->lchild,LT,GT,key);
		//分割左子树
		SplitAVL(T->rchild,LT,GT,key);
		//分割右子树

	}
	return OK;
}
Status MergeAVL(BSTree &T,BSTree TT)
//将平衡二叉树T和TT合并为一棵平衡二叉树
{
	int taller;
	if(TT)
		//如果平衡二叉树不空
	{
		InsertAVL(T,TT->data,taller);
		//将平衡二叉树TT的元素依次插入到平衡二叉树T中去
		MergeAVL(T,TT->lchild);
		MergeAVL(T,TT->rchild);

	}
	return OK;
}