b_tree.h

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

		new_root->branch[0]=root;
		new_root->branch[1]=right_branch;
		root=new_root;
		result=success;
	}
	return result;
}
template<class Record>
Error_code B_tree<Record>::remove(const Record &target)
{
	Error_code result;
	result = recursive_remove(root, target);   //从根结点递归删除
	if (root!= NULL&&root->count == 0)  //如果根结点不空
	{
		B_node<Record> *old_root = root;
		root = root->branch[0];
		delete old_root;
	}
	return result;
}
template<class Record>
Error_code B_tree<Record> ::recursive_remove(B_node<Record> *current, const Record &target)
{ 
	Error_code result;
	int position;
	if (current == NULL)   //若该结点为空
		result = not_present;
	else {
		if (search_node(current, target, position)== success) {//若在该结点找到该关键字
			result = success;
			if (current->branch[position] != NULL) { //若该结点不为叶结点
				copy_in_predecessor(current, position);
				recursive_remove(current->branch[position],current->data[position]);
			}
			else remove_data(current, position); //若为叶结点
		}
		else   //若在该结点找不到该关键字
			result = recursive_remove(current->branch[position], target);
		if (current->branch[position] != NULL)    //若不为叶结点
			if (current->branch[position]->count <(order - 1)/2)   //若子结点的关键字数小于阶数的半数
				restore(current, position);
	}
	return result;
}
template<class Record>
void B_tree<Record>::remove_data(B_node<Record> *current, int position)
{
	for (int i = position; i < current->count - 1; i++)
		current->data[i] = current->data[i + 1];
	current->count--;
}
template<class Record>
void B_tree <Record>::copy_in_predecessor(B_node<Record> *current,int position)
{
	B_node<Record>*leaf = current->branch[position];
	while (leaf->branch[leaf->count] != NULL)
		leaf = leaf->branch[leaf->count];
	current->data[position] =leaf->data[leaf->count - 1];
}
template<class Record>
void B_tree<Record>::restore(B_node<Record> *current, int position)
{
	if (position == current->count)   //若位置和结点的关键字数一致
		if (current->branch[position - 1]->count> (order - 1)/2)   //若大于阶数半数,则向右移动
			move_right(current, position - 1);
		else   //若小于阶数半数,则合并
			combine(current, position);
		else if (position == 0)  //若位置为0
			if (current->branch[1]->count > (order - 1)/2)   //若大于阶数半数,则向左移动
				move_left(current, 1);
			else   //若小于阶数半数,则合并
				combine(current, 1);
			else //若位置在中间
				if (current->branch[position - 1]->count> (order - 1)/2)
					move_right(current, position - 1);
				else 
					if (current->branch[position + 1]->count > (order - 1)/2)
						move_left(current, position + 1);
					else 
						combine(current, position);
}
template<class Record>
void B_tree<Record>::move_left(B_node<Record> *current,int position)
{
	B_node<Record>*left_branch = current->branch[position - 1],*right_branch = current->branch[position];
	left_branch->data[left_branch->count] =current->data[position - 1];
	left_branch->branch[++left_branch->count] =right_branch->branch[0];
	current->data[position - 1] = right_branch->data[0];
	right_branch->count--;
	for (int i = 0; i < right_branch->count; i++) {
		right_branch->data[i] = right_branch->data[i + 1];
		right_branch->branch[i] =right_branch->branch[i + 1];
	}
	right_branch->branch[right_branch->count] =right_branch->branch[right_branch->count + 1];
}
template<class Record>
void B_tree<Record>::move_right(B_node<Record> *current,int position)
{
	B_node<Record>*right_branch = current->branch[position +1],*left_branch = current->branch[position];
	right_branch->branch[right_branch->count + 1] =right_branch->branch[right_branch->count];
	for (int i = right_branch->count ; i > 0; i--) {
		right_branch->data[i] =right_branch->data[i - 1];
		right_branch->branch[i] =right_branch->branch[i - 1];
	}
	right_branch->count++;
	right_branch->data[0] =current->data[position];
	right_branch->branch[0] =left_branch->branch[left_branch->count--];
	current->data[position] =left_branch->data[left_branch->count];
}
template<class Record>
void B_tree<Record>::combine(B_node<Record> *current,int position)
{ 
	int i;
	B_node<Record>*left_branch = current->branch[position - 1],*right_branch = current->branch[position];
	left_branch->data[left_branch->count] =current->data[position - 1];
	left_branch->branch[++left_branch->count] =right_branch->branch[0];
	for (i = 0; i < right_branch->count; i++) {
		left_branch->data[left_branch->count] =right_branch->data[i];
		left_branch->branch[++left_branch->count] =right_branch->branch[i + 1];
	}
	current->count--;
	for (i = position - 1; i < current->count; i++) {
		current->data[i] = current->data[i+ 1];
		current->branch[i +1] = current->branch[i +2];
	}
	delete right_branch;
}
template<class Record>
void B_tree<Record>::print_B_tree(B_node<Record>* current,CDC* pDC,CPoint point,int edge)
{
	if (current!=NULL){	//若结点不空
		CString str;      //输出关键字
		CPoint temp;      //画关键字结点图形的点
		CPoint subtemp;   //画枝节边结点图形的点
		int size=(int)(double(current->count)/2*one_sqare);  //求从关键字结点图形中间位置到结点边界的长度
		//算出关键字结点图形左上角点的位置
		temp.x=point.x-size;
		temp.y=point.y+one_sqare/2;
		for (int j=0;j<current->count;j++)
		{
			pDC->Rectangle(temp.x,point.y,temp.x+one_sqare,point.y+one_sqare);  //画出关键字结点矩形
			str.Format("%d",current->data[j]);
			pDC->SetTextColor(RGB(0,0,255));    //设置输出字的颜色
			pDC->TextOut(temp.x+1,temp.y-8,str);//输出关键字
			temp.x+=one_sqare;                  //关键字结点横坐标位置增加一个方格边长度
		}
		size=(int)(double(current->count+1)/2*one_sqare);   //算出枝节点结点图形中间位置到结点边界的长度
		//算出枝节点结点图形左上角点的位置
		temp.x=point.x-size;
		temp.y=point.y+one_sqare;
		int start_point=edge/(current->count+1);  //算出第一个子结点图形的上中间点位置与结点图形边界的长度
		//算出第一个子结点的打印位置
		subtemp.x=point.x-edge+start_point;
		subtemp.y=temp.y+3*one_sqare;
		for (int i=0;i<current->count+1;i++)
		{
			if (current->branch[i]==NULL) //若为叶结点
			{
				//画出接地线
				CPen pen(PS_SOLID,1,RGB(255,0,0));   //设置画笔为红色
				CPen *penOld=pDC->SelectObject(&pen);
				pDC->MoveTo(temp.x+one_sqare/2,temp.y+one_sqare);
				pDC->LineTo(temp.x+one_sqare/2,temp.y+one_sqare+10);
				pDC->MoveTo(temp.x+one_sqare/2-5,temp.y+one_sqare+10);
				pDC->LineTo(temp.x+one_sqare/2+5,temp.y+one_sqare+10);
				pDC->MoveTo(temp.x+one_sqare/2-4,temp.y+one_sqare+13);
				pDC->LineTo(temp.x+one_sqare/2+4,temp.y+one_sqare+13);
				pDC->MoveTo(temp.x+one_sqare/2-3,temp.y+one_sqare+16);
				pDC->LineTo(temp.x+one_sqare/2+3,temp.y+one_sqare+16);
				pDC->SelectObject(penOld);           //还原画笔颜色
			}
			else  //若不为叶结点
			{
				//画结点连接线
				pDC->MoveTo(temp.x+one_sqare/2,temp.y+one_sqare);
				pDC->LineTo(subtemp.x,subtemp.y);
			}
			pDC->SelectStockObject(GRAY_BRUSH);      //设置画刷原色为灰色
			pDC->Rectangle(temp.x,temp.y,temp.x+one_sqare,temp.y+one_sqare);   //画出枝节点结点矩形
			pDC->SelectStockObject(HOLLOW_BRUSH);    //还原画刷颜色
			print_B_tree(current->branch[i],pDC,subtemp,start_point);          //打印子结点
			subtemp.x+=start_point*2;	//算出下一个子结点的打印位置
			temp.x+=one_sqare;          //下一个枝节点横坐标位置
		}
		
	}
}
template<class Record>
void B_tree<Record>::display(CDC* pDC,CPoint point)
{
	print_B_tree(root,pDC,point,point.x);   //递归打印B-Tree
}