btreenode.cpp

数据结构中B-树经典算法的可视化执行程序

// BTreeNode.cpp : implementation file

#include "stdafx.h"
#include "BTreeNode.h"


int BTreeNode::KeyNum=3;
int BTreeNode::Min=KeyNum/2;


//*****************查找结点中指定关键字，返回查找到关键字的位置,若没有找到，返回-1******************

int BTreeNode::Search(int obj)const
{
	for(int i=0;i<Data.size();i++){
		if(obj==Data[i])
			return i;
	}
	return -1;
}



//*****************查找对应子结点，返回查找到的位置，若结点已经存在，返回－1*******************

int BTreeNode::SearchSonNodePos(int obj)const
{
	for(int i=0;i<Data.size();i++){
		if(obj==Data[i]) 
			return -1;
		if(obj<Data[i])
			return i;
	}
	return Data.size();
}




//*****************将给定的关键字插入结点并使其有序，返回插入后的位置*******************

int BTreeNode::InsertSort(int obj,BTreeNode *left,BTreeNode *right)
{
	int endPos=Data.size();

	Data.push_back(obj);
	sort(Data.begin(),Data.end());
	int pos=Search(obj);

	if(pos!=endPos){//如果插入的关键字不在末尾，将相应的右半部分指针右移一位
		for(int i=SonNode.size();i>pos+1;i--)
			SonNode[i]=SonNode[i-1];
	}
	
	SonNode[pos]=left;
	SonNode[pos+1]=right;

	if(left!=NULL) left->Parent=this;//子结点和父结点的连接
	if(right!=NULL) right->Parent=this;
	return pos;
}




//******************将左结点右半部分赋给右结点************************

void BTreeNode::Split(int mid,BTreeNode *right)
{
	BTreeNode *temp;
	for(int i=mid+1,j=0; i<Data.size(); i++,j++){
		right->Data.push_back(Data[i]);

		right->SonNode[j]=temp=SonNode[i];//转移
		right->SonNode[j+1]=SonNode[i+1];

		if(temp!=NULL)
			temp->Parent=right;//分离时，右结点的子结点指向自己的父结点
	}

	temp=right->SonNode[j];//对应最后一个关键字
	if(temp!=NULL)
		temp->Parent=right;//分离时，右结点的子结点指向自己的父结点

	for(i=mid,j=Data.size();i<j;i++)//将多余结点从左结点删除
		Data.pop_back();
}



//*******************判断该结点是否为叶子结点，是则返回true*********************

bool BTreeNode::IsLeaf()const
{
	for(int i=0;i<=Data.size();i++){
		if(SonNode[i]!=NULL)
			return false;
	}
	return true;
}



//*********************删除结点中指定的关键字************************

void BTreeNode::Remove(int obj)
{
	vector<int>::iterator it=find(Data.begin(),Data.end(),obj);
	if(it!=Data.end())	
		Data.erase(it);
}



//*********************判断左结点是否为关键字数最小值，是则返回true******************

bool BTreeNode::LeftIsMin(int pos)const
{
	if(pos<0) return true;
	BTreeNode *temp=SonNode[pos];
	return Min==temp->Data.size();
}



//*********************判断右结点是否为关键字数最小值，是则返回true******************

bool BTreeNode::RightIsMin(int pos)const
{
	if(pos>Data.size()) return true;
	BTreeNode *temp=SonNode[pos];
	return Min==temp->Data.size();
}



//*********************找到左子树中最大值，返回最大值关键字所在的结点*****************

BTreeNode * BTreeNode::MaxInLeft(int pos)const
{
	BTreeNode *temp=SonNode[pos];
	BTreeNode *sonNode=temp->SonNode[temp->Data.size()];
	while(sonNode!=NULL){
		temp=sonNode;
		sonNode=temp->SonNode[temp->Data.size()];
	}
	return temp;
}



//*********************找到右子树的最小值，返回最小值关键字所在的结点*****************

BTreeNode * BTreeNode::MinInRight(int pos)const
{
	BTreeNode *temp=SonNode[pos+1];
	BTreeNode *sonNode=temp->SonNode[0];
	while(sonNode!=NULL){
		temp=sonNode;
		sonNode=temp->SonNode[0];
	}
	return temp;
}



//*********************查找并返回相应子结点在当前结点中的连接位置，若不存在则返回－1*********************

int BTreeNode::SearchPos(BTreeNode * obj)const
{
	for(int i=0;i<SonNode.size();i++){
		if(obj==SonNode[i])
			return i;
	}
	return -1;
}