btree.h

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

// BTree.h : header file


#ifndef BTREE_H
#define BTREE_H


#include "BTreeNode.h"


class BTree{
	private:		
		BTreeNode *BTreeRoot; //根结点
		int KeyNum;		
       
		BTreeNode * FindToLeaf(int obj); //找到给定的关键字要插入的叶结点并返回其指针，若数据重复，则返回NULL
		
		BTreeNode * Find(int obj);//找到给定的关键字所在的结点并返回其指针，若关键字不存在，则返回NULL
		
		BTreeNode *CreatNewNode(){ //创造一个新结点
			return new BTreeNode();
		}
		
		void InsertData(BTreeNode *tNode,int obj); //给结点插入关键字,并保证树的结点结构仍然满足B－树定义
		
		BTreeNode * Combine(BTreeNode *left,int mid,BTreeNode *right); //将左结点，一个关键字，右结点组合并返回组合以后的结点的指针
		
		void EraseNoLeaf(BTreeNode *node,int obj); //删除在非叶子结点上的关键字
		
		void EraseData(BTreeNode *node,int obj); //删除指定关键字
				
		void EraseIsMin(BTreeNode *node,int obj);//删除关键字个数等于Min的结点中的数据
				
		BTreeNode * CombineAndLink(BTreeNode * obj);//组合相应结点并连接其父结点
		
	public:
		BTree(int key=3){
			KeyNum=key;
			BTreeNode::KeyNum=this->KeyNum;
			BTreeRoot=CreatNewNode();
		}
		
		const int GetKey()const{ //返回B-树的阶
			return KeyNum;
		}
				
		BTreeNode * GetRoot()const{ //返回根结点的指针
			return BTreeRoot;
		}
				
		void CreatTree(int *start,int num); //创造一棵B-树
		
		void Insert(int obj); //B－树插入关键字
		
		bool Search(int obj); //查找关键字是否存在,若存在则返回true
		
		void Erase(int obj){ //删除B－树中指定的关键字
			BTreeRoot->Parent=NULL;
			BTreeNode *temp=Find(obj);
			if(temp!=NULL)
				EraseData(temp,obj);
		}
		
		bool IsEmpty(){ //判断B-树是否为空
			return BTreeRoot->GetDataCount()==0;
		}
		
		void Clear() { //清空树
			while(!BTreeRoot->Data.empty())
				BTreeRoot->Data.pop_back();
			BTreeRoot->SonNode[0]=NULL;
		}

};
//end class BTree





#endif//BTREE_H