btree.h

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

// BTree.h : header file


#ifndef BTREE_H
#define BTREE_H


#include "BTreeNode.h"


class BTree{
	private:
		
		BTreeNode *m_BTreeRoot; //根结点
		int m_KeyNum;
		
		
        //*************找到数据要插入的叶结点并返回其指针，若数据重复，则返回NULL*************
		BTreeNode * FindToLeaf(int obj);


		//*************找到数据所在的结点并返回其指针，若数据不存在，则返回NULL***************
		BTreeNode * Find(int obj);

		
		//*************创造一个新结点*****************
		BTreeNode *CreatNewNode(){
			return new BTreeNode();
		}

		
		//*************插入数据项,并保证树的结点结构仍然满足B－树要求****************
		void InsertData(BTreeNode *tNode,int obj);


		//*************将左结点，一个数据项，右结点组合并返回组合以后的结点的指针*****************
		BTreeNode * Combine(BTreeNode *left,int mid,BTreeNode *right);


		//*************删除在非叶子结点上的数据项***************
		void EraseNoLeaf(BTreeNode *node,int obj);

		
		//*************删除指定数据项**************
		void EraseData(BTreeNode *node,int obj);
		
		//*************删除关键字个数等于m_Min的结点中的数据*****************
		void EraseLeftMin(BTreeNode *node,int obj);
		
		//*************组合相应结点并连接其父结点*****************
		BTreeNode * CombineAndLink(BTreeNode * obj);


		
	public:

		BTree(int key=3){
			m_KeyNum=key;
			BTreeNode::m_KeyNum=this->m_KeyNum;
			m_BTreeRoot=CreatNewNode();
		}

	
		//*************返回B-树的阶****************
		const int GetKey()const{
			return m_KeyNum;
		}
		
		
		//*************返回根结点的指针****************
		BTreeNode * GetRoot()const{
			return m_BTreeRoot;
		}
		
		
		//*************创造一棵B-树****************
		void CreatTree(int *start,int num);



		//*************插入数据项****************
		void Insert(int obj);


		//*************查找数据项是否存在,若存在则返回true***************
		bool Search(int obj);


		//*************删除数据项**************
		void Erase(int obj){
			m_BTreeRoot->m_Parent=NULL;
			BTreeNode *temp=Find(obj);
			if(temp!=NULL)
				EraseData(temp,obj);
		}

		//*************判断B-树是否为空**************
		bool IsEmpty(){
			return m_BTreeRoot->GetDataCount()==0;
		}

		

		//**************清空树**************
		void Clear()
		{
			while(!m_BTreeRoot->m_Data.empty())
				m_BTreeRoot->m_Data.pop_back();
			m_BTreeRoot->m_SonNode[0]=NULL;
		}

};
//end class BTree





#endif//BTREE_H