btreenode.cpp

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

// BTreeNode.cpp : implementation file

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


int BTreeNode::m_KeyNum=3;
int BTreeNode::m_Min=m_KeyNum/2;


//*****************查找结点中指定数据项，返回查找到数据项的位置,若没有找到，返回-1******************

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



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

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



//*****************输出结点各个数据项的值*****************

void BTreeNode::ShowNode(bool isChangeLine,string space)const
{
	for(int i=0;i<m_Data.size();i++)
		cout<<m_Data[i]<<space;
	if(isChangeLine) cout<<endl;
}



//*****************将数据项插入结点并使其有序，返回插入后的位置*******************

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

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

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

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




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

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

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

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

	temp=right->m_SonNode[j];//对应最后一个数据项
	if(temp!=NULL)
		temp->m_Parent=right;//分离时，右结点的子结点指向自己的父结点

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



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

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



//*********************删除结点中指定的数据项************************

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



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

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



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

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



//*********************找到左子树中最大值，返回最大值数据项所在的结点*****************

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



//*********************找到右子树的最小值，返回最小值数据项所在的结点*****************

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



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

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