b_treesview.cpp

B树代码以及演示

// B_TreesView.cpp : implementation of the CB_TreesView class
//

#include "stdafx.h"
#include "B_Trees.h"

#include "B_TreesDoc.h"
#include "B_TreesView.h"

#include "B_tree.h"

#ifdef _DEBUG
#define new DEBUG_NEW
#undef THIS_FILE
static char THIS_FILE[] = __FILE__;
#endif

/////////////////////////////////////////////////////////////////////////////
// CB_TreesView

IMPLEMENT_DYNCREATE(CB_TreesView, CView)

BEGIN_MESSAGE_MAP(CB_TreesView, CView)
//{{AFX_MSG_MAP(CB_TreesView)
ON_WM_CREATE()
ON_WM_DESTROY()
ON_BN_CLICKED(IDC_INSERT, OnInsert)
ON_BN_CLICKED(IDC_DELETE, OnDelete)
ON_BN_CLICKED(IDC_SEARCH, OnSearch)
//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CB_TreesView construction/destruction

CB_TreesView::CB_TreesView()
{
	// TODO: add construction code here
	isSearch=false;
	//	for(int ch='a';ch<'n';ch++)
	//		tree.insert(ch);
}

CB_TreesView::~CB_TreesView()
{
	
	
}

BOOL CB_TreesView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs
	
	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CB_TreesView drawing

void CB_TreesView::OnDraw(CDC* pDC)
{
	CB_TreesDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here	
	pDC->Rectangle(14,14,66,36);
	CRect clientRect;
	GetClientRect(clientRect);
	tree.screenWidth=clientRect.Width();
	if(tree.root!=NULL)
	{		
		tree.beforeDraw();
		tree.draw(pDC);
	}
	if(isSearch)
	{
		int x=0;
		int y;
		tree.getPos(tree.root,x,y,ch);
		if(x==0)
			MessageBox("未找到");
		else
		{
			CPen pen;
			pen.CreatePen(1,2,RGB(255,0,0));
			CPen* oldpen=pDC->SelectObject(&pen);
			int edge=tree.edge;
			TEXTMETRIC txt;
			pDC->GetTextMetrics(&txt);			
			CString str=ch;
			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);
			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);		
			pDC->SelectObject(oldpen);
		}
	}
}

/////////////////////////////////////////////////////////////////////////////
// CB_TreesView diagnostics

#ifdef _DEBUG
void CB_TreesView::AssertValid() const
{
	CView::AssertValid();
}

void CB_TreesView::Dump(CDumpContext& dc) const
{
	CView::Dump(dc);
}

CB_TreesDoc* CB_TreesView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CB_TreesDoc)));
	return (CB_TreesDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CB_TreesView message handlers
int CB_TreesView::OnCreate(LPCREATESTRUCT lpCreateStruct) 
{
	if (CView::OnCreate(lpCreateStruct) == -1)
		return -1;
	// TODO: Add your specialized creation code here	
	btnIns.Create("Insert",BS_DEFPUSHBUTTON |WS_VISIBLE|WS_CHILD,CRect(75,15,125,35),this,IDC_INSERT);
	btnDel.Create("Delete",BS_DEFPUSHBUTTON |WS_VISIBLE|WS_CHILD,CRect(135,15,185,35),this,IDC_DELETE);
	btnSea.Create("Search",BS_DEFPUSHBUTTON |WS_VISIBLE|WS_CHILD,CRect(195,15,245,35),this,IDC_SEARCH);
	edit.Create(ES_LEFT |ES_LOWERCASE|WS_VISIBLE|WS_CHILD,CRect(15,15,65,35),this,IDC_EDIT);
	edit.SetLimitText(1);
	edit.SetWindowText("a");
	return 0;
}
void CB_TreesView::OnInsert() 
{
	// TODO: Add your control notification handler code here
	
	CString str;	
	GetDlgItemText(IDC_EDIT,str);
	if(!str.IsEmpty())
	{

		char ch=str.GetAt(0);
		if(ch>='a'&&ch<='z')
		{
			isSearch=false;
			tree.insert(ch);
			ch++;
			str.SetAt(0,ch);
			edit.SetWindowText(str);		
			Invalidate();
		}
		else
			MessageBox("超越范围");
	}
	else
		MessageBox("输入为空");
}
void CB_TreesView::OnDelete() 
{
	// TODO: Add your control notification handler code here
	CString str;	
	GetDlgItemText(IDC_EDIT,str);
	if(!str.IsEmpty())
	{
		isSearch=false;
		char ch=str.GetAt(0);
		if(!tree.remove(ch))
			MessageBox("不成功");
		edit.SetSel(0, -1);
		edit.Clear();
		Invalidate();		
	}
	else
		MessageBox("输入为空");
}
void CB_TreesView::OnSearch() 
{
	// TODO: Add your control notification handler code here
	CString str;	
	GetDlgItemText(IDC_EDIT,str);
	if(!str.IsEmpty())
	{
		isSearch=true;
		ch=str.GetAt(0);
	//	tree.getPos(tree.root,x,y,ch);
		edit.SetSel(0, -1);
		edit.Clear();		
		Invalidate();
	}
	else
		MessageBox("输入为空");
}
void CB_TreesView::OnDestroy() 
{
	CView::OnDestroy();
	
	// TODO: Add your message handler code here	
}

////////////////////////////////////////////////////////////////////////////
//implementation of the B_tree class

template <class Record, int order>
bool B_tree<Record, order> ::search_tree(Record &target)
{
	return recursive_search_tree(root, target);
}
template <class Record, int order>
bool B_tree<Record, order> ::recursive_search_tree(B_node<Record, order>*current, Record &target)
{
	bool result =false;								//not_present
	int position;
	if(current != NULL)
	{
		result = search_node(current, target, position);
		if (result == false)
		{
			result = recursive_search_tree(current->branch[position], target);
		}
		else		
			target = current->data[position];
	}
	return result;
};
template <class Record, int order>
bool B_tree<Record, order>::search_node(B_node<Record, order> *current,
										const Record &target,
										int &position)	
{
	position = 0;
	while (position < current->count &&target > current->data[position])
		position++; //Perform a sequential search//through the keys.
	if (position < current->count &&target == current->data[position])
		return true;
	else
		return false;
}

template <class Record, int order>
bool B_tree<Record, order>::insert(const Record &new_entry)
{
	Record median;
	B_node<Record, order> *right_branch,*new_root;
	bool result = push_down(root,new_entry, median, right_branch);
	if (result == false) 
	{
		// The whole tree grows in height.
		//Make a brand new_root for the whole B-tree.
		new_root = new B_node<Record, order>;
		new_root->count = 1;
		new_root->data[0] = median;
		new_root->branch[0] = root;
		new_root->branch[1] = right_branch;
		root = new_root;
		result = true;
	}
	return result;
}
template <class Record, int order>
bool B_tree<Record, order> ::push_down(B_node<Record, order> *current,
									   const Record &new_entry,
									   Record &median,
									   B_node<Record,
									   order>*&right_branch)
{
	bool result;
	int position;
	if (current == NULL) 
	{
		// Since we cannot insert in an empty tree,
		//the recursion terminates.
		median = new_entry;
		right_branch = NULL;
		result = false;								//overflow
	}
	else 
	{	// Search the current node.
		if (search_node(current, new_entry, position) ==true)
			result= true;
		//	result = 0;								//duplicate_error
		else 
		{
			Record extra_entry;
			B_node<Record, order> *extra_branch;
			result = push_down(	current->branch [position],	new_entry,extra_entry,extra_branch);
			if (result == false)
			{
				// Record extra_entry now must be added to current
				if (current->count < order - 1) 
				{
					result =true ;					//success
					push_in(current, extra_entry,
						extra_branch, position);
				}
				else 
					split_node( current, extra_entry,extra_branch, position,right_branch, median);
				// Record median and its right_ branch will go up to a higher node.
			}
		}
	}
	return result;
}
template <class Record, int order>
void B_tree<Record, order>::push_in(	B_node<Record, order> *current,
									const Record &entry,
									B_node<Record, order> *right_branch,
									int position)
{
	for (int i = current->count; i > position; i--) 
	{
		// Shift all later data to the right.
		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, int order>
void B_tree<Record, order>:: 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)
{
	right_half = new B_node<Record, order>;
	int mid = order/2; // The entries from mid on will go to right half .
	if (position <= mid) 
	{ // First case: extra_entry belongs in left half.
		for (int i = mid; i < order - 1; i++) 
		{ // Move entries to right_half .
			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
	{ // Second case: extra_entry belongs in right_half.
		mid++; // Temporarily leave the median in left half.
		for (int i = mid; i < order - 1; i++) 
		{
			// Move entries to right_half .
			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];
	// Remove median from left half.
	right_half->branch[0] = current->branch[current->count];
	current->count--;
}

template <class Record, int order>
bool B_tree<Record, order> ::remove(const Record &target)
{
	bool result;
	result = recursive_remove(root, target);
	if (root != NULL && root->count == 0)
	{ // root is now empty.
		B_node<Record, order> *old_root = root;
		root = root->branch[0];
		delete old_root;
	}
	return result;
}
template <class Record, int order>
bool B_tree<Record, order> ::recursive_remove(B_node<Record, order> *current, 
											  const Record &target)
{
	bool result;
	int position;
	if (current == NULL) result =false ;//not_present
	else {
		if (search_node(current, target, position)
			== true) {
			// The target is in the current node.
			result = true;
			if (current->branch[position] != NULL) 
			{
				// not at a leaf node
				copy_in_predecessor(current, position);
				recursive_remove(current->branch[position],
					current->data[position]);
			}
			else remove_data(current, position);
			// Remove from a leaf node.
		}
		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, int order>
void B_tree<Record, order> ::remove_data(B_node<Record, order> *current, int position)
{
	for (int i = position; i < current->count - 1; i++)
		current->data[i] = current->data[i + 1];
	current->count--;
}

template <class Record, int order>
void B_tree < Record, order > ::copy_in_predecessor(B_node<Record, order> *current,
													int position)
{
	B_node<Record, order>
		*leaf = current->branch[position];
	// First go left from the current entry.
	while (leaf->branch[leaf->count] != NULL)
		leaf = leaf->branch[leaf->count];
	// Move as far rightward as possible.
	current->data[position] =
		leaf->data[leaf->count - 1];
}
template <class Record, int order>
void B_tree<Record, order> ::restore(B_node<Record, order> *current, int position)
{
	if (position == current->count) // case: rightmost branch
		if (current->branch[position - 1]->count
			> (order - 1)/2)
			move_right(current, position - 1);
		else
			combine(current, position);
		else if (position == 0) // case: leftmost branch
			if (current->branch[1]->count > (order - 1)/2)
				move_left(current, 1);
			else
				combine(current, 1);
			else // remaining cases: intermediate branches
				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, int order>
void B_tree<Record, order> ::move_left(B_node<Record, order> *current,
									   int position)
{
	B_node<Record, order>
		*left_branch = current->branch[position - 1],
		*right_branch = current->branch[position];
	left_branch->data[left_branch->count] =
		current->data[position - 1]; // Take entry from the parent.
	left_branch->branch[++left_branch->count] =
		right_branch->branch[0];
	current->data[position - 1] = right_branch->data[0];
	// Add the right-hand entry to the parent.
	right_branch->count--;
	for (int i = 0; i < right_branch->count; i++) {
		// Move right-hand entries to fill the hole.
		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, int order>
void B_tree<Record, order> ::move_right(B_node<Record, order> *current,
										int position)
{
	B_node<Record, order>
		*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--) {
		// Make room for new entry.
		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];
	// Take entry from parent.
	right_branch->branch[0] =
		left_branch->branch[
		left_branch->count--];
	current->data[position] =
		left_branch->data[
		left_branch->count];
}
template <class Record, int order>
void B_tree<Record, order> ::combine(B_node<Record, order> *current,
									 int position)
{ 
	int i;
	B_node<Record, order>
		*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;
}