btreenode.h

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

// BTreeNode.h : header file

#ifndef BTREENODE_H
#define BTREENODE_H


#include <iostream>
#include <vector>
#include <algorithm>
#include <list>
#include <string>
#include <queue>
using namespace std;


class BTreeNode{
	public:
		
		BTreeNode *m_Parent;            //用来存储指向双亲结点的指针
		vector<int> m_Data;             //用一个向量（类似与动态增长的数组）来存储结点数据
		vector<BTreeNode *> m_SonNode;  //用来存储指向叶结点指针		
		static  int m_KeyNum;           //树的阶
		static int m_Min;               //非根结点中孩子结点的最小数目
		int m_NodeShowPos;              //结点的位置

		
		BTreeNode()
		{
			m_Parent=NULL;
			for(int i=0;i<m_KeyNum;i++)
				m_SonNode.push_back(NULL);
			m_NodeShowPos=0;
		}
		
		
		//*****************返回树的阶数**********
		const int GetKEY()const{
			return m_KeyNum;
		}

		
		//*****************查找结点中指定数据项，返回查找到数据项的位置,若没有找到，返回-1*********
		int Search(int obj)const;

		
		//*****************查找对应子结点，返回查找到子结点的位置，如果结点已经存在，返回－1*******************
		int SearchSonNodePos(int obj)const;

		
		//*****************输出结点各个数据项的值***************
		void ShowNode(bool isChangeLine=true,string space="  ")const;
		
		
		//*****************将数据项插入结点并使其有序，返回插入后的位置*******************
		int InsertSort(int obj,BTreeNode *left,BTreeNode *right);

		
		//*****************判断结点的关键字是否已满，满则返回true************************
		bool IsFull()const{
			return m_KeyNum<=m_Data.size();
		}

		
		//*****************将左结点右半部分赋给右结点*************************
		void Split(int mid,BTreeNode *right);

		
		//*****************判断该结点是否为叶子结点，是则返回true************************
		bool IsLeaf()const;

		
		//*****************删除结点中指定的数据项*********************
		void Remove(int obj);

		
		//*****************判断左结点是否为关键字最小值，是则返回true**********************
		bool LeftIsMin(int pos)const;


		//*****************判断右结点是否为关键字最小值，是则返回true**********************
		bool RightIsMin(int pos)const;

		
		//*****************找到左子树中最大值，返回最大值数据项所在的结点*********************
		BTreeNode * LeftMax(int pos)const;


		//*****************找到右子树的最小值，返回最小值数据项所在的结点*********************
		BTreeNode * BTreeNode::RightMin(int pos)const;
				

		//*****************查找并返回相应子结点在当前结点中的连接位置，若不存在则返回－1*************************
		int SearchPos(BTreeNode * obj)const;

		
		//*****************判断结点数据项的数目是否小于关键字最少要求，若小于则返回true*************************
		bool IsLessThanMin()const{
			return m_Min>m_Data.size();
		}

		
		//*****************判断结点数据项的数目是否等于m_Min，若等于则返回true**************************
		bool IsMin()const{
			return m_Data.size()==m_Min;
		}
		
		
		//*****************返回该结点所包含的数据项个数**************************
		int GetDataCount(){
			return m_Data.size();
		}

		
		//*****************返回该结点在树中的深度，根结点为0**************************
		int GetDeep(){
			int deep;
			BTreeNode *node=this;
			for(deep=0;node!=NULL;deep++){
				node=node->m_Parent;
			}
			return deep-1;
		}

};
//end class BTreeNode



#endif//BTREENODE_H