hongheiview.cpp

红黑树算法

// hongheiView.cpp : implementation of the CHongheiView class
//

#include "stdafx.h"
#include "honghei.h"

#include "hongheiDoc.h"
#include "hongheiView.h"

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

/////////////////////////////////////////////////////////////////////////////
// CHongheiView

IMPLEMENT_DYNCREATE(CHongheiView, CView)

BEGIN_MESSAGE_MAP(CHongheiView, CView)
//{{AFX_MSG_MAP(CHongheiView)
	ON_COMMAND(ID_INSERT, OnInsert)
	ON_COMMAND(ID_DELETE, OnDelete)
	ON_COMMAND(ID_SEARCH, OnSearch)
	ON_COMMAND(ID_REDRAW, OnRedraw)
	//}}AFX_MSG_MAP
// Standard printing commands
ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CHongheiView construction/destruction

CHongheiView::CHongheiView()
{
	// TODO: add construction code here
	this->find_res=tree.nil;
	this->finding=false;
}

CHongheiView::~CHongheiView()
{
}

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

/////////////////////////////////////////////////////////////////////////////
// CHongheiView drawing

void CHongheiView::OnDraw(CDC* pDC)
{
	CHongheiDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	CRect rect;
	this->GetClientRect(rect);
	CPoint point(rect.right/2,0);
	if(this->tree.root!=this->tree.nil)
		this->draw_tree(pDC,this->tree.root,point,point);
}

/////////////////////////////////////////////////////////////////////////////
// CHongheiView printing

BOOL CHongheiView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CHongheiView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CHongheiView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CHongheiView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CHongheiView message handlers

void CHongheiView::draw_tree(CDC *pDC,CTree::PRBTree parent,CPoint my_point,CPoint parent_point)
{
	CRect rect(my_point.x-10,my_point.y,my_point.x+10,my_point.y+20);


	if(this->finding&&this->find_res==parent)
	{
		CRect find_rect;
		find_rect.left=rect.left-5;
		find_rect.right=rect.right+5;
		find_rect.top=rect.top-5;
		find_rect.bottom=rect.bottom+5;
		
		
		CBrush brush,*pOldBrush;
		brush.CreateSolidBrush(RGB(0,0,255));
		pOldBrush=pDC->SelectObject(&brush);
		pDC->Rectangle(find_rect);
		pDC->SelectObject(pOldBrush);
		brush.DeleteObject();
	}
	
	CBrush brush,*pOldBrush;

	if(parent->color==0)//黑色
		brush.CreateSolidBrush(RGB(0,0,0));
	else
		brush.CreateSolidBrush(RGB(255,0,0));
	pOldBrush=pDC->SelectObject(&brush);
	pDC->Ellipse(rect);
	pDC->SelectObject(pOldBrush);
	brush.DeleteObject();
	


	CString str;
	str.Format("%d",parent->key);
	pDC->TextOut(my_point.x+15,my_point.y,str);
	if(parent==this->tree.root)//根节点
	{
		if(parent->left!=tree.nil)
		{
			CRect rect;
			this->GetClientRect(&rect);
			CPoint left_point((my_point.x/2),my_point.y+100);
			pDC->MoveTo(my_point.x,my_point.y+20);
			pDC->LineTo(left_point.x,left_point.y);
			this->draw_tree(pDC,parent->left,left_point,my_point);
		}
		if(parent->right!=tree.nil)
		{
			CRect rect;
			this->GetClientRect(&rect);
			CPoint right_point((my_point.x*3)/2,my_point.y+100);
			pDC->MoveTo(my_point.x,my_point.y+20);
			pDC->LineTo(right_point.x,right_point.y);
			this->draw_tree(pDC,parent->right,right_point,my_point);
		}	
	}
	else 
	{
		int x_cha=(parent_point.x-my_point.x)/2;//x的变化
		if(parent_point.x<my_point.x)
			x_cha=0-x_cha;
		if(parent->left!=tree.nil)
		{
			CRect rect;
			this->GetClientRect(&rect);
			CPoint left_point(my_point.x-x_cha,my_point.y+100);
			pDC->MoveTo(my_point.x,my_point.y+20);
			pDC->LineTo(left_point.x,left_point.y);
			this->draw_tree(pDC,parent->left,left_point,my_point);
		}
		if(parent->right!=tree.nil)
		{
			CRect rect;
			this->GetClientRect(&rect);
			CPoint right_point(my_point.x+x_cha,my_point.y+100);
			pDC->MoveTo(my_point.x,my_point.y+20);
			pDC->LineTo(right_point.x,right_point.y);
			this->draw_tree(pDC,parent->right,right_point,my_point);
		}
	}	
}

void CHongheiView::OnInsert() 
{
	// TODO: Add your command handler code here
	CInsertDlg dlg;
	if(dlg.DoModal())
	{	
		this->find_res=this->tree.Find_Node(this->tree.root,dlg.m_key);
		if(find_res!=tree.nil)
		{
			this->finding=false;
			AfxMessageBox("该节点已存在！");
		}
		else
		{
			tree.RB_InsertNode(this->tree.root,dlg.m_key);
			this->OnRedraw();
		}
	}
}

void CHongheiView::OnDelete() 
{
	// TODO: Add your command handler code here
	CDeleteDlg dlg;
	if(dlg.DoModal()==IDOK)
	{	
		this->find_res=this->tree.Find_Node(this->tree.root,dlg.m_key);
		if(find_res==tree.nil)
		{
			this->finding=false;
			AfxMessageBox("不存在该节点！");
		}
		else
		{
			this->tree.RB_DeleteNode(this->tree.root,dlg.m_key);
		this->OnRedraw();
		}
		

	}
}

void CHongheiView::OnSearch() 
{
	// TODO: Add your command handler code here
	CSearchDlg dlg;
	if(dlg.DoModal()==IDOK)
	{
		this->find_res=this->tree.Find_Node(this->tree.root,dlg.m_key);
		if(find_res==tree.nil)
		{
			this->finding=false;
			AfxMessageBox("不存在该节点！");
		}
		else
		{
			this->finding=true;
			this->Invalidate();
		}
	}
}

void CHongheiView::OnRedraw() 
{
	// TODO: Add your command handler code here
	this->finding=false;
	this->Invalidate();
}