b_tree.h

B树的实现以及图形化显示

//////////////////////////////////////////////////////////////////////////
//姓名: 林文清
//学号: 0610374
//专业: 计算机科学与技术
//课程: 数据结构
//////////////////////////////////////////////////////////////////////////

enum Error_code{success,overflow,duplicate_error,not_present};  //结果返回类型
static int one_sqare=27;    //设置显示图形每个方格的边的长度
//////////////////////////////////////////////////////////////////////////
//B-Tree的结点数据结构B_node的声明
//////////////////////////////////////////////////////////////////////////
template <class Record>
class B_node{
public:
	int count;      //记录存入的关键字数
	Record* data;   //关键字指针
	B_node<Record>** branch;   //每个B-Tree节点的枝节边指针
	//构造函数
	B_node(int num){            //num为阶数
		data=new Record[num-1];
		branch=new B_node<Record>* [num];
		count=0;     //初始关键数为0
	}
	//析构函数
	~B_node(){
		delete []data;
		delete []branch;
	}
};
//////////////////////////////////////////////////////////////////////////
//B-tree类的声明
//////////////////////////////////////////////////////////////////////////
template <class Record>
class B_tree
{
	int order;    //阶数
	B_node<Record> *root;  //根节点
	bool whether_created;  //用于判断是否已经构造了B-Tree
public:
	//无参构造函数
	B_tree(){
		root=NULL;
		whether_created=false;
	}
	//含参构造函数
	B_tree(int num){
		order=num;
		whether_created=true;
		root=NULL;
	}
	Error_code set_order(int);           //设置阶数
	Error_code insert(Record);           //插入关键字
	Error_code search_tree(Record&);     //在树中查找关键字
	Error_code search_node(B_node<Record> *, const Record &, int &);         //在结点中查找关键字
	Error_code push_down(B_node<Record>*,Record,Record&,B_node<Record>* &);  //在结点中插入关键字
	Error_code recursive_search_tree(B_node<Record> *, Record &);            //递归查找关键字
	void push_in(B_node<Record> *,const Record &,B_node<Record> *,int );     //往上一个结点中插入关键字
    void split_node(B_node<Record> *,const Record &,B_node<Record> *,int,B_node<Record> * &,Record &); //分裂结点
    Error_code remove(const Record &);                               //删除关键字
	Error_code recursive_remove(B_node<Record> *, const Record &);   //递归删除结点
	void remove_data(B_node<Record> *, int);                         //直接删除关键字
	void copy_in_predecessor(B_node<Record> *,int);                  //从上一个结点摘一个结点过来
	void restore(B_node<Record> *, int);                             //重新存储结点
	void move_left(B_node<Record> *,int);                            //向左移动结点
	void move_right(B_node<Record> *,int);                           //向右移动结点
	void combine(B_node<Record> *,int);                              //合并结点
	void print_B_tree(B_node<Record>*,CDC*,CPoint,int);              //递归打印结点
	void display(CDC*,CPoint);                                       //打印结点
};
template<class Record>
Error_code B_tree<Record>::set_order(int num)
{
	if (!whether_created)
	{
		order=num;
		whether_created=true;
		return success;
	}
	return duplicate_error;
}
template<class Record>
Error_code B_tree<Record>::search_node(B_node<Record> *current, const Record &target, int &position)
{
	position = 0;
	while (position < current->count &&target > current->data[position])
		position++;
	if (position<current->count&&target==current->data[position])
		return success;
	else
		return not_present;
}
template<class Record>
Error_code B_tree<Record> ::recursive_search_tree(B_node<Record> *current, Record &target)
{
	Error_code result = not_present;
	int position;
	if (current != NULL) {
		result = search_node(current, target,position);    //在结点中查找
		if (result == not_present) //如果要插入的关键字不在B-Tree中
			result = recursive_search_tree (current->branch[position], target);
		else                        //如果要插入的关键字在B-Tree中
			target = current->data[position];
	}
	return result;
}
template<class Record>
Error_code B_tree<Record> ::search_tree(Record &target)
{
	return recursive_search_tree(root, target);
}
template<class Record>
void B_tree<Record>::push_in( B_node<Record> *current,const Record &entry,B_node<Record> *right_branch,int position)
{
	//采用类似插入排序的方式插入关键字
	for (int i = current->count; i > position; i--) {
		current->data[i] = current->data[i-1];
		current->branch[i+1] = current->branch[i];
	}
	current->data[position] = entry;
	current->branch[position+1] = right_branch;
	current->count ++;
}
template<class Record>
void B_tree<Record> :: split_node(B_node<Record> *current,const Record &extra_entry, B_node<Record> *extra_branch,int position,B_node<Record> * &right_half, Record &median)
{
	right_half = new B_node<Record>(order);
	int mid = order/2;            //从中间位置开始分裂
	if (position <= mid) {        //如果要插入的关键字的位置小于等于中间位置
		for (int i = mid; i < order - 1; i++) {
			right_half->data[i - mid] = current->data[i];
			right_half->branch[i + 1 - mid] =current->branch[i +1];
		}
		current->count = mid;
		right_half->count = order - 1 - mid;
		push_in(current, extra_entry,extra_branch, position);
	}
	else {                       //如果要插入的关键字的位置小于中间位置
		mid++;
		for (int i = mid; i < order - 1; i++) {
			right_half->data[i - mid] = current->data[i];
			right_half->branch[i + 1 - mid] =current->branch[i + 1];
		}
		current->count = mid;
		right_half->count = order - 1 - mid;
		push_in(right_half, extra_entry, extra_branch, position -mid);
	}
	median = current->data[current->count - 1];
	right_half->branch[0] = current->branch[current->count];
	current->count--;
}
template <class Record,int order>
Error_code B_tree<Record>::push_down(B_node<Record>* current,Record new_entry,Record& median,B_node<Record>* &right_branch)
{
	Error_code result;
	int position;
	if(current==NULL)   //如果指针为空
	{
		median=new_entry;
		right_branch=NULL;
		result=overflow;
	}
	else{         //指针不为空
		if(search_node(current,new_entry,position)==success)    //如果要插入的关键字在B-Tree中
			result=duplicate_error;
		else{                                                   //如果要插入的关键字不在B-Tree中
			Record extra_entry;
			B_node<Record> *extra_branch;
			result=push_down(current->branch[position],new_entry,extra_entry,extra_branch);
			if(result==overflow){   //如果溢出
				if(current->count<(order-1)){    //如果插入当前结点不会溢出
					result=success;
					push_in(current,extra_entry,extra_branch,position);   //直接插入该结点
				}
				else   //如果插入当前结点会溢出,则分裂结点
					split_node(current,extra_entry,extra_branch,position,right_branch,median);
			}
		}
	}
	return result;
}
template <class Record,int order>
Error_code B_tree<Record>::insert(Record new_entry)
{
	Record median;
	B_node<Record> *right_branch,*new_root;
	Error_code result=push_down(root,new_entry,median,right_branch);
	if(result==overflow)   //如果插入溢出到根结点,则根结点分裂
	{
		new_root=new B_node<Record>(order);
		new_root->count=1;
		new_root->data[0]=median;