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 *Parent;            //用来存储指向双亲结点的指针
		vector<int> Data;             //用一个向量（类似与动态增长的数组）来存储结点数据
		vector<BTreeNode *> SonNode;  //用来存储指向叶结点指针		
		static  int KeyNum;           //树的阶
		static int Min;               //非根结点中孩子结点的最小数目
		int NodeShowPos;              //结点的位置

		
		BTreeNode()
		{
			Parent=NULL;
			for(int i=0;i<KeyNum;i++)
				SonNode.push_back(NULL);
			NodeShowPos=0;
		}
			
		
		const int GetKEY()const{     //返回树的阶数
			return KeyNum;
		}
		
		
		int Search(int obj)const; //查找结点中指定关键字，返回查找到关键字的位置,若没有找到，返回-1		
		
		int SearchPos(BTreeNode * obj)const; //查找并返回相应子结点在当前结点中的连接位置，若不存在则返回－1
		
		int SearchSonNodePos(int obj)const; //查找对应子结点，返回查找到子结点的位置，如果结点已经存在，返回－1		
				
		int InsertSort(int obj,BTreeNode *left,BTreeNode *right); //将给定的关键字插入结点并使其有序，返回插入后的位置		
		
		bool IsFull()const{  //判断结点的关键字是否已满，满则返回true
			return KeyNum<=Data.size();
		}
		
		void Split(int mid,BTreeNode *right); //将左结点右半部分赋给右结点
		
		bool IsLeaf()const; //判断该结点是否为叶结点，是则返回true
		
		void Remove(int obj); //删除结点中指定的关键字
		
		bool LeftIsMin(int pos)const; //判断左结点是否为关键字数最小值，是则返回true
		
		bool RightIsMin(int pos)const;//判断右结点是否为关键字数最小值，是则返回true
		
		BTreeNode * MaxInLeft(int pos)const; //找到左子树中最大值，返回最大值关键字所在的结点
		
		BTreeNode * MinInRight(int pos)const; //找到右子树的最小值，返回最小值关键字所在的结点
										
		bool IsLessThanMin()const{ //判断结点关键字的数目是否小于关键字最少要求，若小于则返回true
			return Min>Data.size();
		}
		
		bool IsMin()const{ //判断结点关键字的数目是否等于Min，若等于则返回true
			return Data.size()==Min;
		}
				
		int GetDataCount(){ //返回该结点所包含的关键字个数
			return Data.size();
		}
		
		int GetDeep(){ //返回该结点在树中的深度，根结点深度为0
			int deep;
			BTreeNode *node=this;
			for(deep=0;node!=NULL;deep++){
				node=node->Parent;
			}
			return deep-1;
		}

};
//end class BTreeNode



#endif//BTREENODE_H