fun.cpp

平衡二叉树操作的演示: 1、 操作界面给出查找、插入、删除、退出等操作选择。 2、 每种操作均要提示输入关键字。 3、 每次插入或删除一个节点后

#include "stdafx.h"
#include "fun.h"
#include "malloc.h"
#include "stdlib.h"

Status InitBSTree(BSTree &T){
	T=NULL;
	return OK;
}

Status SearchBST(BSTree T,int key,BSTree f,BSTree &p){
	if(!T){
		p=f;
		printf("\n你所查找的元素不存在。");
		return FALSE;}
	else if(key==T->data.key){
		p=T;
		printf("\n关键字为%d的元素值为%s",key,T->data.ch);
		return TRUE;
	}
	else if(key<T->data.key)
		return SearchBST(T->lchild,key,T,p);
	else return SearchBST(T->rchild,key,T,p);
}

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;
}

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=TRUE;
	}
	else{
		if(e.key==T->data.key){
			taller=FALSE;
			return 0;
		}
		if(e.key<T->data.key){
			if(!InsertAVL(T->lchild,e,taller))
				return 0;
			if(taller)
				switch(T->bf){
				case LH:
					LeftBalance(T);taller=FALSE;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 0;
			}
			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 OK;
}


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 RH:T->bf=LH;rc->bf=EH;break;
		case EH:T->bf=rc->bf=EH;break;
		case LH:T->bf=EH;rc->bf=RH;break;
		}
		ld->bf=EH;
		R_Rotate(T->rchild);
		L_Rotate(T);
	}
}



BSTree DelBST(BSTree &T,int key,BSTree f,BSTree &p,char c){
	if(!T){
		p=NULL;
		printf("\n你所要删除的元素不存在。");
		return p;}
	else if(key==T->data.key){
		p=T;
		if(!(p->lchild||p->rchild)){
		if(c=='L')
			f->lchild=NULL;
		else if(c=='R')
			f->rchild=NULL;
		else if(f==NULL)
			T=NULL;
		}
		return p;
	}
	else if(key<T->data.key)
			
		return DelBST(T->lchild,key,T,p,'L');
	else return DelBST(T->rchild,key,T,p,'R');
}

BSTree GetRNode(BSTree &T){
	BSTree q,p;
	q=T;
	p=q->rchild;
	while(p->rchild){
		q=p;
		p=p->rchild;
	}
	q=NULL;
	return p;
}

BSTree GetLNode(BSTree &T){
	
	BSTree q,p;
	q=T;
	p=q->lchild;
	while(p->lchild){
		q=p;
		p=p->lchild;
	}
	q=NULL;
	return p;
}

Status DelBNode(BSTree &T,int key){
	BSTree p,q,p1;
	q=DelBST(T,key,NULL,p,NULL);
	if(!q)return OK;
	 if(q->lchild){
		 if(q->lchild->rchild){
			p1=GetRNode(q->lchild);
			q->data=p1->data;
			free(p1);
			printf("删除成功！");
			return OK;
		 }
		else{
		q->data=q->lchild->data;
		free(q->lchild);
		q->lchild=NULL;
		printf("删除成功！");
			return OK;
		}
	}
	else if(q->rchild){
		if(T->rchild->lchild){
			p1=GetLNode(q->rchild);
			q->data=p1->data;
			free(p1);
			printf("删除成功！");
			return OK;
		}
		else{
			q->data=q->rchild->data;
			free(q->rchild);
			q->rchild=NULL;
			printf("删除成功！");
			return OK;
		}
	}
	else{
		free(q);
		printf("删除成功！");
		return OK;
	}
}

void Print_BSTree(BSTree T,int i)//按凹入表形式打印输出树的元素,i表示结点所在层次,初次调用时i=0
{int j;
for(j=1;j<=i;j++) printf("	 "); //留出i个空格以表现出层次
printf("%d.%s\n",T->data.key,T->data.ch); //打印元素,换行
if(T->lchild)
Print_BSTree(T->lchild,i+1);
if(T->rchild)
Print_BSTree(T->rchild,i+1);
}