b_tree.h

B树代码以及演示

// B_tree.h: interface for the B_tree class.
//
//////////////////////////////////////////////////////////////////////

#include "StdAfx.h"
#if !defined(AFX_B_TREE_H__F820AD40_B9D2_4B96_9E27_46A8965F0DDD__INCLUDED_)
#define AFX_B_TREE_H__F820AD40_B9D2_4B96_9E27_46A8965F0DDD__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

template <class Record, int order>
class B_node 
{
public:
	// data members
	int	edge;
	int x;
	int y;
	int count;													//num of data
	Record data[order-1];
	B_node<Record, order> *branch[order];

	void drawBox(CDC* pDC,int x,int y,char data,int num/*第num个*/)
	{
		TEXTMETRIC txt;
		pDC->GetTextMetrics(&txt);
		
		CString str=data;
		
		pDC->Rectangle(x,y,x+edge,y+edge);
		pDC->TextOut(x+edge/2-txt.tmAveCharWidth/2,y+edge/2-txt.tmHeight/2,str);
		pDC->MoveTo(x,y);
		pDC->LineTo(x+0.5*edge,y-0.4*edge);
		pDC->MoveTo(x+edge,y);
		pDC->LineTo(x+1.5*edge,y-0.4*edge);
		pDC->MoveTo(x+0.5*edge,y-0.4*edge);
		pDC->LineTo(x+1.5*edge,y-0.4*edge);
		if(num==count)
		{
			pDC->MoveTo(x+edge,y+edge);
			pDC->LineTo(x+1.5*edge,y+0.6*edge);
			pDC->LineTo(x+1.5*edge,y-0.4*edge);
		}
		
	}

	void drawGrayBox(CDC* pDC,int x,int y,int num)
	{
		CBrush brush ;
		brush.CreateSolidBrush(RGB(200,200,200));
		CBrush *oldbrush=pDC->SelectObject(&brush);
		pDC->Rectangle(x,y,x+edge,y+edge);		
		if(num==1)
		{
			CPoint pts1[3];
			pts1[0].x = x;
			pts1[0].y = y;
			pts1[1].x = x+0.5*edge;
			pts1[1].y = y-0.4*edge;
			pts1[2].x = x+0.5*edge;
			pts1[2].y = y;
			pDC->Polygon(pts1, 3);
	
		}	
		if(num==count+1)
		{
			CPoint pts2[4];
			pts2[0].x = x+edge;
			pts2[0].y = y;
			pts2[1].x = x+edge;
			pts2[1].y = y+edge;
			pts2[2].x = x+1.5*edge;
			pts2[2].y = y+0.6*edge;
			pts2[3].x = x+1.5*edge;
			pts2[3].y = y-0.4*edge;
			pDC->Polygon(pts2, 4);
			CPoint pts3[4];
			pts3[0].x = x+edge/2;
			pts3[0].y = y;
			pts3[1].x = x+edge;
			pts3[1].y = y;
			pts3[2].x = x+1.5*edge;
			pts3[2].y = y-0.4*edge;
			pts3[3].x = x+edge;
			pts3[3].y = y-0.4*edge;
			pDC->Polygon(pts3, 4);
		}
		pDC->SelectObject(oldbrush);	
	}
	void drawBranch(CDC* pDC,int x,int y,int num)
	{
		CBrush brush ;
		brush.CreateSolidBrush(RGB(0,0,0));
		CBrush *oldbrush=pDC->SelectObject(&brush);
		pDC->Ellipse(x-2,y-2,x+2,y+2);
		pDC->SelectObject(oldbrush);
		if(branch[0]==NULL)
		{		
			pDC->MoveTo(x,y);
			pDC->LineTo(x,y+edge);
			pDC->MoveTo(x-0.3*edge,y+edge);
			pDC->LineTo(x+0.3*edge,y+edge);
			pDC->MoveTo(x-0.2*edge,y+1.1*edge);
			pDC->LineTo(x+0.2*edge,y+1.1*edge);
			pDC->MoveTo(x-0.1*edge,y+1.2*edge);
			pDC->LineTo(x+0.1*edge,y+1.2*edge);
		}
		else
		{
			for(int i=0;i<=count;i++)
			{
				if(i==num)
				{
					pDC->MoveTo(x,y);			
					pDC->LineTo(branch[i]->x+branch[i]->count*edge/2+0.5*edge,branch[i]->y-0.4*edge);
				}
			}
		}
	}
	void traverse(B_node<Record, order> *root,int &nullBranchNum,int &leafNoteNum)
	{	
		if(root==NULL)
		{
			nullBranchNum++;
			return;
		}
		else if(root->branch[0]==NULL)
			leafNoteNum++;
		for(int i=0;i<=root->count;i++)
			traverse(root->branch[i],nullBranchNum,leafNoteNum);
	}
	void draw(CDC* pDC)
	{		
		int tempx=x;
		int tempy=y;
		for(int i=0;i<count;i++)
		{			
			drawBox(pDC,tempx,tempy,data[i],i+1);
			tempx+=edge;
		}
		tempx=x-edge/2;
		tempy=y+edge;
		for(i=0;i<count+1;i++)
		{			
			drawGrayBox(pDC,tempx,tempy,i+1);
			tempx+=edge;
		}
		tempx=x;
		tempy=y+1.5*edge;
		for(i=0;i<count+1;i++)
		{			
			drawBranch(pDC,tempx,tempy,i);
			tempx+=edge;
		}		
	}
	void setPos(int tempx,int tempy,int tempedge)
	{
		edge=tempedge;
		x=tempx;
		y=tempy;
	}
	B_node()
	{
		count=0;
		x=0;
		y=0;
		edge=50;
	}
};
template <class Record, int order>
class B_tree 
{
private:										// data members
	
public:
	int leafNoteNum;
	int nullBranchNum;
	int screenWidth;
	int height;
	int edge;
	int margin;
	B_node<Record, order> *root;
	B_tree()
	{
		height=0;
		leafNoteNum=0;
		nullBranchNum=0;
		root=NULL;
	};										// Add public methods
	//	virtual ~B_Tree();
	bool search_tree(Record &target);
	bool recursive_search_tree(B_node<Record, order>*current, Record &target);
	bool search_node(B_node<Record, order> *current,const Record &target,int &position);
	bool insert(const	Record &new_entry);
	bool push_down(B_node<Record, order> *current,
					const Record &new_entry,
					Record &median,
					B_node<Record,
					order>*&right_branch);
	void push_in(	B_node<Record, order> *current,
					const Record &entry,
					B_node<Record, order> *right_branch,
					int position);
	void split_node(B_node<Record, order> *current, // node to be split
					const Record &extra_entry, // new_entry to insert
					B_node<Record, order> *extra_branch,// subtree on right of extra_entry
					int position,// index in node where extra_entry goes
					B_node<Record, order> * &right_half, // new node
					// for right half of entries
					Record &median) ;// median entry (in neither half)
	bool remove(const Record &target);
	bool recursive_remove(B_node<Record, order> *current, 
													const Record &target);
	void remove_data(B_node<Record, order> *current, int position);
	void copy_in_predecessor(B_node<Record, order> *current,
										int position);
	void restore(B_node<Record, order> *current, int position);
	void move_left(B_node<Record, order> *current,
									   int position);
	void move_right(B_node<Record, order> *current,
										int position);
	void combine(B_node<Record, order> *current,
									 int position);

	void beforeDraw()
	{
		B_node<Record, order> *temp=root;	
		for(;temp!=NULL;height++)
			temp=temp->branch[0];		
		root->traverse(root,nullBranchNum,leafNoteNum);	
		margin=edge=screenWidth/(leafNoteNum+nullBranchNum+1);
		if(edge>50)
		{
			edge=50;
			margin=(screenWidth-(nullBranchNum+leafNoteNum-1)*edge)/2;
		}
		int tempx=margin+edge/2;
		setBottomPos(root,tempx,edge);		
		for(int tempheight=height-1;tempheight!=0;tempheight--)
			setOtherPos(root,edge,tempheight);		
		height=0;
		leafNoteNum=0;
		nullBranchNum=0;
	}
	void setBottomPos(B_node<Record, order> *root,int &tempx,int tempedge)
	{
		if(root==NULL)	
			return;		
		else if(root->branch[0]==NULL)
		{
			root->setPos(tempx,50+(height-1)*3*edge,tempedge);										//??????????
			tempx+=(root->count+2)*edge;
		}		
		for(int i=0;i<=root->count;i++)
			setBottomPos(root->branch[i],tempx,tempedge);
	}
	void setOtherPos(B_node<Record, order> *root,/*int &tempy,*/int tempedge,int tempheight)
	{	
		B_node<Record, order> *temp=root->branch[0];
		for(int i=0;i<height-tempheight;i++)
			temp=temp->branch[0];
		if(temp==NULL)
		{			
			root->setPos((root->branch[0]->x+root->branch[root->count]->x+root->branch[root->count]->count*edge)/2
				-root->count*edge/2,50+3*(tempheight-1)*edge,tempedge);
			return;
		}
		for(i=0;i<=root->count;i++)
			setOtherPos(root->branch[i],tempedge,tempheight);		
	}
	void getPos(B_node<Record, order> *root,int& tempx,int &tempy,char target)
	{
		if(root==NULL)	
			return;
		for(int i=0;i<=root->count;i++)
		{
			if(target==root->data[i])
			{
				tempx=root->x+i*edge;
				tempy=root->y;
				return;
			}
			getPos(root->branch[i],tempx,tempy,target);
		}	
	}
	void draw(CDC* pDC)
	{
		drawTree(root,pDC);
	}
	void drawTree(B_node<Record, order> *root,CDC* pDC)
	{		
		if(root==NULL)
			return;
		root->draw(pDC);
		for(int i=0;i<=root->count;i++)
			drawTree(root->branch[i],pDC);
	}
};

#endif // !defined(AFX_B_TREE_H__F820AD40_B9D2_4B96_9E27_46A8965F0DDD__INCLUDED_)