btree.cpp

数据结构B树算法的演示程序 包括添加删除节点

// BTree.cpp : implementation file

#include "stdafx.h"
#include "BTree.h"



//*****************找到数据要插入的叶结点并返回其指针，若数据重复，则返回NULL******************

BTreeNode * BTree::FindToLeaf(int obj)
{
	BTreeNode *temp=m_BTreeRoot;
	int pos=0;
	
	while(!temp->IsLeaf()){
		pos=temp->SearchSonNodePos(obj);
		if(pos==-1) return NULL;  //判断数据是否重复
		temp=temp->m_SonNode[pos];
	}
	pos=temp->SearchSonNodePos(obj); //查找对应子结点
	if(pos==-1)return NULL;
	return temp;
}



//****************找到数据所在的结点并返回其指针，若数据不存在，则返回NULL*******************

BTreeNode * BTree::Find(int obj)
{
	BTreeNode *temp=m_BTreeRoot;
	int pos=0;
	
	while(!temp->IsLeaf()){
		if(temp->Search(obj)!=-1) return temp;
		pos=temp->SearchSonNodePos(obj);
		temp=temp->m_SonNode[pos];
	}
	
	if(temp->Search(obj)!=-1) 
		return temp;
	else  //数据不存在
		return NULL;
}




//****************插入数据项,并保证树的结点结构仍然满足B－树要求**************

void BTree::InsertData(BTreeNode *tNode,int obj)
{
	BTreeNode *left=NULL,*right=NULL;
	BTreeNode *temp=tNode;
	while(1){
		temp->InsertSort(obj,left,right);
		if(!temp->IsFull()) return ;//插入结束

		//插入以后，节点的数据项已满,进行向上传递数据项的操作
		left=temp;
		obj=left->m_Data[left->m_KeyNum/2];
		right=CreatNewNode();
		left->Split(left->m_KeyNum/2,right);

		if(temp->m_Parent==NULL){
			temp=CreatNewNode();
			m_BTreeRoot=temp;  //如果父结点不存在，创造的父结点必定是根结点
		}
		else{
			temp=temp->m_Parent;
		}
	}	
}




//****************创造一棵B-树*****************

void BTree::CreatTree(int *start,int num)
{
	BTreeNode *temp=NULL;
	for(int i=0;i<num;start++,i++){
		temp=FindToLeaf(*start);
		if(temp!=NULL)  //如果数据没有重复，插入
			InsertData(temp,*start);
	}
}



//****************插入数据项****************

void BTree::Insert(int obj)
{
	BTreeNode *temp=NULL;
	temp=FindToLeaf(obj);
	if(temp!=NULL)  //如果数据没有重复则插入
		InsertData(temp,obj);
}



//****************查找数据项是否存在,若存在则返回true*****************

bool BTree::Search(int obj)
{
	BTreeNode *temp=FindToLeaf(obj);
	if(temp==NULL)
		return true;
	else return false;
}



//*****************将左结点，一个数据项，右结点组合并返回组合以后的结点的指针*******************

BTreeNode * BTree::Combine(BTreeNode *left,int mid,BTreeNode *right)
{
	BTreeNode *temp=NULL;
	left->m_Data.push_back(mid);//先将中间结点插入
	for(int i=left->m_Data.size(),j=0;j<right->m_Data.size();i++,j++){
		left->m_Data.push_back(right->m_Data[j]);
		temp=right->m_SonNode[j];
		left->m_SonNode[i]=temp;
		if (temp!=NULL) temp->m_Parent=left;//连接父结点
	}
	temp=right->m_SonNode[j];//针对最后一个数据项的操作
	left->m_SonNode[i]=temp;
	if (temp!=NULL) temp->m_Parent=left;
	return left;
}



//*****************删除在非叶子结点上的数据项*****************

void BTree::EraseNoLeaf(BTreeNode *node,int obj)
{
	BTreeNode *temp=NULL;
	int changeData=0;
	int pos=node->Search(obj);
	temp=node->LeftMax(pos);
	if(!temp->IsMin()){  //中序前驱结点的关键字大于m_Min
			changeData=temp->m_Data[temp->m_Data.size()-1];
			node->m_Data[pos]=changeData;
			temp->Remove(changeData);
			return ;    //删除结束
	}
	temp=node->RightMin(pos);
	if(!temp->IsMin()){ //中序后继结点的关键字大于m_Min
		changeData=temp->m_Data[0];
		node->m_Data[pos]=changeData;
		temp->Remove(changeData);
		return ;       //删除结束
	}
	
	//左右子结点均为最小关键字
	temp=node->RightMin(pos);
	changeData=temp->m_Data[0];
	node->m_Data[pos]=changeData;
	EraseLeftMin(temp,changeData);
}



//*****************删除指定数据项***********************

void BTree::EraseData(BTreeNode *node,int obj)
{
	if(!node->IsLeaf()){ //不是叶结点
		EraseNoLeaf(node,obj);
	}
	else{ //叶结点
		//关键字不是最小,或删除的是叶子根结点
		if(node->m_Data.size() > node->m_Min || node->m_Parent==NULL)
			node->Remove(obj);
		else
			EraseLeftMin(node,obj);
	}
}


//*********************删除关键字个数等于m_Min的结点中的数据*************************

void BTree::EraseLeftMin(BTreeNode *node,int obj)
{
	BTreeNode *temp=node;
	BTreeNode *parent=temp->m_Parent;
	int changeData=0;	
	BTreeNode *left=NULL;
	BTreeNode *right=NULL;
	int pos=parent->SearchPos(node);//查找目标结点在其父结点中位置
	//如果左兄弟关键字个数大于m_Min
	if(!parent->LeftIsMin(pos-1)){
		left=parent->m_SonNode[pos-1];
		//将父结点parent->m_Data[pos-1]传递到目标结点
		node->Remove(obj);
		node->InsertSort(parent->m_Data[pos-1],NULL,NULL);
		//将左结点最大值覆盖parent->m_Data[pos-1]
		int deletePos=left->m_Data.size()-1;
		parent->m_Data[pos-1]=left->m_Data[deletePos];
		left->m_Data.pop_back();//删除左子结点最大值
		return ;//删除结束
	}
	//如果右兄弟数据项数目大于m_Min
	if(!parent->RightIsMin(pos+1)){
		right=parent->m_SonNode[pos+1];
		//将父结点parent->m_Data[pos]传递到目标结点
		node->Remove(obj);
		node->InsertSort(parent->m_Data[pos],NULL,NULL);
		//将右结点最小值覆盖parent->m_Data[pos]
		parent->m_Data[pos]=right->m_Data[0];
		right->m_Data.erase(right->m_Data.begin());//删除右子结点最小值
		return ;//删除结束
	}
	//左右兄弟结点数据项数目均为最小值
	temp->Remove(obj);
	while(temp!=NULL){
		if(temp->IsLessThanMin()){
			temp=CombineAndLink(temp);
		}
		else return;
	}
}



//*******************组合相应结点并连接其父结点************************

BTreeNode * BTree::CombineAndLink(BTreeNode * obj){
	BTreeNode *temp;
	BTreeNode *parent=obj->m_Parent;
	
	int pos=parent->SearchPos(obj);
	//左兄弟不存在
	if(pos==0)
		pos++;
	//将obj左兄弟和其父结点中序后继数据项，以及obj本身组合
	temp=Combine(parent->m_SonNode[pos-1],parent->m_Data[pos-1],
				parent->m_SonNode[pos]);

	parent->Remove(parent->m_Data[pos-1]);//从父结点删除被temp组合的数据项
	parent->m_SonNode[pos-1]=temp;//连接组合后的子结点
	temp->m_Parent=parent;
	for(int i=pos;i<=parent->m_Data.size();i++){//移动子结点指针
		parent->m_SonNode[i]=parent->m_SonNode[i+1];
	}

	if(temp->IsFull()){//当合并以后的结点不符合规范时,将结点分离
			BTreeNode *right=CreatNewNode();
			int mid=temp->m_Data[temp->m_KeyNum/2];
			temp->Split(temp->m_KeyNum/2,right);
			parent->InsertSort(mid,temp,right);
	}
	if(parent->IsLessThanMin() && parent->m_Parent==NULL){//当parent已经是根结点
		if(parent->m_Data.size()==0){//父结点可能为空
			m_BTreeRoot=parent->m_SonNode[0];
			m_BTreeRoot->m_Parent=NULL;
			return NULL;
		}
		m_BTreeRoot=parent;
		m_BTreeRoot->m_Parent=NULL;
		return NULL;
	}
	return parent;
}