btreenode.h

图书管理系统

#ifndef BTREENODE_H
#define BTREENODE_H

////////*************包含文件*****************///////////
#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <string>
#include <queue>
using namespace std;

//B-树的节点定义
class BTreeNode
{
public:
	///*****共有数据************
	BTreeNode *m_pParent; 
	vector<int> m_vecData;//用一个向量来存储数据
	vector<BTreeNode *> m_vecSonNode; //用来存储指向叶节点指针
	//**********在此设定节点阶数***************************************************
	//enum{m_nKEYNUM=3,m_nMIN=m_nKEYNUM/2};//B-树一个节点最多存储的数据的个数，即关键字
	static  int m_nKEYNUM;
	static int m_nMIN;
	int m_nNodeShowPos;


	
	//构造函数
	BTreeNode()
	{
		m_pParent=NULL;
		int count=m_nKEYNUM+m_nMIN;
		if(m_nKEYNUM==3)//如果不加此判断，在release版本下会有问题，debug模式下无错
			count++;
		for(int i=0;i<count;i++)
			m_vecSonNode.push_back(NULL);
		m_nNodeShowPos=0;
	}

	//返回阶数key
	const int GetKEY()const
	{
		return m_nKEYNUM;
	}

	//查找
	int Search(int obj)const
	{
		for(int i=0;i<m_vecData.size();i++)
		{
			if(obj==m_vecData[i])
				return i;
		}
		return -1;
	}

	//查找对应子节点的位置
	int SearchSonNodePos(int obj)const
	{
		for(int i=0;i<m_vecData.size();i++)
		{
			if(obj==m_vecData[i]) 
				return -1;
			if(obj<m_vecData[i])
				return i;
		}
		return m_vecData.size();
	}

	//输出各个节点值
	void ShowNode(bool isChangeLine=true,string space="  ")const
	{
		for(int i=0;i<m_vecData.size();i++)
			cout<<m_vecData[i]<<space;
		if(isChangeLine)
			cout<<endl;
	}

	//插入并使序列有序
	int InsertSort(int obj,BTreeNode *left,BTreeNode *right)
	{
		int endPos=m_vecData.size();//尾部数据的位置
		m_vecData.push_back(obj);
		sort(m_vecData.begin(),m_vecData.end());
		int pos=Search(obj);

		if(pos!=endPos)
		{
			//如果插入节点不是在尾部，将相应的右半部指针右移一位
			for(int i=m_vecSonNode.size();i>pos+1;i--)
				m_vecSonNode[i]=m_vecSonNode[i-1];
		}
		m_vecSonNode[pos]=left;
		m_vecSonNode[pos+1]=right;
		
		if(left!=NULL) left->m_pParent=this;//子节点和父节点的连接
		if(right!=NULL) right->m_pParent=this;
		return pos;
	}

	//判断关键字是否已经满
	bool IsFull()const
	{
		return m_nKEYNUM<=m_vecData.size();
	}


	//将左节点右半部分赋给右节点
	void Split(int mid,BTreeNode *right)
	{
		BTreeNode *temp;
		for(int i=mid+1,j=0; i<m_vecData.size(); i++,j++)
		{
			right->m_vecData.push_back(m_vecData[i]);
			
			right->m_vecSonNode[j]=temp=m_vecSonNode[i];//转移
			right->m_vecSonNode[j+1]=m_vecSonNode[i+1];
			
			if(temp!=NULL)
				temp->m_pParent=right;//分离时，右节点的子节点指向自己的父节点
		}

		temp=right->m_vecSonNode[j];//对应最后一个数据项
		if(temp!=NULL)
			temp->m_pParent=right;//分离时，右节点的子节点指向自己的父节点
		
		for(i=mid,j=m_vecData.size();i<j;i++)//将多余节点从左节点删除
			m_vecData.pop_back();
	}

	//判断节点是否为叶节点
	bool IsLeaf()const
	{
		for(int i=0;i<=m_vecData.size();i++)
		{
			if(m_vecSonNode[i]!=NULL)
				return false;
		}
		return true;
	}

	//删除数据项
	void Remove(int obj)
	{
		vector<int>::iterator it=find(m_vecData.begin(),m_vecData.end(),obj);
		if(it!=m_vecData.end())	
			m_vecData.erase(it);
	}

	//判断左节点是否为最小数据项数目
	bool LeftIsMin(int pos)const
	{
		if(pos<0) return true;
		BTreeNode *temp=m_vecSonNode[pos];
		return m_nMIN==temp->m_vecData.size();
	}

	//判断右节点是否为最小数据项数目
	bool RightIsMin(int pos)const
	{
		if(pos>m_vecData.size()) return true;
		BTreeNode *temp=m_vecSonNode[pos];
		return m_nMIN==temp->m_vecData.size();
	}

	//找到左子树中最大值
	BTreeNode * LeftMax(int pos)const
	{
		BTreeNode *temp=m_vecSonNode[pos];//先到最左边
		BTreeNode *sonNode=temp->m_vecSonNode[temp->m_vecData.size()];//找到最右节点
		while(sonNode!=NULL)
		{
			temp=sonNode;
			sonNode=temp->m_vecSonNode[temp->m_vecData.size()];
		}
		return temp;
	}

	//找到右子树的最小值
	BTreeNode * BTreeNode::RightMin(int pos)const
	{
		BTreeNode *temp=m_vecSonNode[pos+1];//先到最右边
		BTreeNode *sonNode=temp->m_vecSonNode[0];//找到最右节点
		
		while(sonNode!=NULL)
		{
			temp=sonNode;
			sonNode=temp->m_vecSonNode[0];
		}
		return temp;
	}

	//查找相应子节点在当前节点中的连接位置
	int SearchPos(BTreeNode * obj)const
	{
		for(int i=0;i<m_vecSonNode.size();i++)
		{
			if(obj==m_vecSonNode[i])
				return i;
		}
		return -1;
	}

	//判断节点数据项数目是否<m_nMIN
	bool IsLessThanMin()const
	{
		return m_nMIN>m_vecData.size();
	}

	//判断节点数据项数目是否＝＝m_nMIN
	bool IsMin()const
	{
		return m_vecData.size()==m_nMIN;
	}

	//返回这个节点包含的数据项的个数
	int GetDataCount()
	{
		return m_vecData.size();
	}

	//返回这个节点在树中的深度，根结点为0,往子结点递增
	int GetDeep()
	{
		int deep;
		BTreeNode *node=this;
		for(deep=0;node!=NULL;deep++)
		{
			node=node->m_pParent;
		}
		return deep-1;
	}
};

int BTreeNode::m_nKEYNUM=4;//定义static变量,此处需初始化大于等于3，否则release版本运行有错
int BTreeNode::m_nMIN=m_nKEYNUM/2;

//end class BTreeNode
//////////////////////////////////////////////////////////////
#endif//BTREENODE_H