红黑树.cpp

红黑树——一种数据结构的可视化画法

// 红黑树.cpp : Defines the class behaviors for the application.
//

#include "stdafx.h"
#include "红黑树.h"

#include "MainFrm.h"
#include "红黑树Doc.h"
#include "红黑树View.h"

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

/////////////////////////////////////////////////////////////////////////////
// CMyApp
Node Nil;  //哨兵
 const pNode   nil=&Nil;
 rbTree gtree;


BEGIN_MESSAGE_MAP(CMyApp, CWinApp)
	//{{AFX_MSG_MAP(CMyApp)
	ON_COMMAND(ID_APP_ABOUT, OnAppAbout)
		// NOTE - the ClassWizard will add and remove mapping macros here.
		//    DO NOT EDIT what you see in these blocks of generated code!
	//}}AFX_MSG_MAP
	// Standard file based document commands
	ON_COMMAND(ID_FILE_NEW, CWinApp::OnFileNew)
	ON_COMMAND(ID_FILE_OPEN, CWinApp::OnFileOpen)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CMyApp construction

CMyApp::CMyApp()
{
	// TODO: add construction code here,
	// Place all significant initialization in InitInstance
}

/////////////////////////////////////////////////////////////////////////////
// The one and only CMyApp object

CMyApp theApp;
void  drawNode(pNode pn,int px,int py,int wg,CDC* pDC)
{
	CBrush *nb,*ob;
	nb=new CBrush;
	int x, y;
	x=px+wg;
	y=py+100;
	COLORREF c;
       if(pn->color==RED)
	   {
		   c=RGB(255,0,0);
		   nb->CreateSolidBrush(c);
	   }
	   else
	   {
		   c=RGB(0,0,0);
		   nb->CreateSolidBrush(c);
	   }
	   ob=pDC->SelectObject(nb);
	   CRect rec(x-15,y-15,x+15,y+15);
	   pDC->Ellipse(&rec);
	   pDC->SetTextColor(RGB(12,200,13));
	   //pDC->SetBkColor(c);
	   pDC->SetBkMode(TRANSPARENT);
	   
       CString str;
	   str.Format("%d",pn->key);
	   pDC->TextOut(x-5,y-9,str);
	   str.Format("size=%d",pn->size);
	   pDC->TextOut(x-20,y-35,str);
	   str.Format("rank=%d",gtree.Rank(pn));
	   pDC->TextOut(x-20,y+15,str);


	   pDC->MoveTo(CPoint(x,y-15));
	   if(pn->p!=nil)
	   pDC->LineTo(CPoint(px,py+15));
	   pDC->SelectObject(ob);
}

void drawRBtree(pNode pn,int px,int py,int wx,CDC*pDC)
{
       drawNode( pn,px,py,wx, pDC);
    	if(pn->left!=nil)
		drawRBtree(pn->left,px+wx,py+100,-wx/2,pDC);
		if(pn->right!=nil)
		drawRBtree(pn->right,px+wx,py+100,wx/2,pDC);

}
void listAll(pNode pn,CTreeCtrl *list,HTREEITEM hit=TVI_ROOT)
{
 CString str;
  if(pn->color==BLACK)
	 str.Format("%s :  %s :  %d",pn->name,"BLACK",pn->key);
  else
     str.Format("%s :  %s  :  %d",pn->name,"RED",pn->key);
 /*  if(pn->p == nil)
	hit=list->InsertItem(TVIF_TEXT |TVIF_PARAM,str,0,0,0,0,
	(LPARAM)pn,TVI_ROOT,0);
   else*/
      hit=list->InsertItem(TVIF_TEXT |TVIF_PARAM,str,0,0,0,0,
	(LPARAM)pn,hit,0);
	  

   if(pn->left!=nil)
   listAll(pn->left,list,hit);
   if(pn->right!=nil)
   listAll(pn->left,list,hit);

}
void listAll(pNode pn,CListBox *list ,int nindex=0)
{
	CString str;
  if(pn->color==BLACK)
	 str.Format("%s :  %s ;  %d",pn->name,"BLACK",pn->key);
  else
     str.Format("%s :  %s  ;  %d",pn->name,"RED",pn->key);
   list->InsertString( nindex,str);
   list->SetItemData(nindex,(DWORD)pn);
   if(pn->left!=nil)
   listAll(pn->left,list,nindex++);
   if(pn->right!=nil)
   listAll(pn->right,list,nindex++);
}

/////////////////////////////////////////////////////////////////////////////
// CMyApp initialization

BOOL CMyApp::InitInstance()
{
	AfxEnableControlContainer();

	// Standard initialization
	// If you are not using these features and wish to reduce the size
	//  of your final executable, you should remove from the following
	//  the specific initialization routines you do not need.

#ifdef _AFXDLL
	Enable3dControls();			// Call this when using MFC in a shared DLL
#else
	Enable3dControlsStatic();	// Call this when linking to MFC statically
#endif

	// Change the registry key under which our settings are stored.
	// TODO: You should modify this string to be something appropriate
	// such as the name of your company or organization.
	SetRegistryKey(_T("Local AppWizard-Generated Applications"));

	LoadStdProfileSettings();  // Load standard INI file options (including MRU)

	// Register the application's document templates.  Document templates
	//  serve as the connection between documents, frame windows and views.

	CSingleDocTemplate* pDocTemplate;
	pDocTemplate = new CSingleDocTemplate(
		IDR_MAINFRAME,
		RUNTIME_CLASS(CMyDoc),
		RUNTIME_CLASS(CMainFrame),       // main SDI frame window
		RUNTIME_CLASS(CMyView));
	AddDocTemplate(pDocTemplate);

	// Parse command line for standard shell commands, DDE, file open
	CCommandLineInfo cmdInfo;
	ParseCommandLine(cmdInfo);

	// Dispatch commands specified on the command line
	if (!ProcessShellCommand(cmdInfo))
		return FALSE;

	// The one and only window has been initialized, so show and update it.
	m_pMainWnd->ShowWindow(SW_SHOW);
	m_pMainWnd->UpdateWindow();
	 Nil.color=BLACK;
     Nil.size=0;
     Nil.p=nil;
     Nil.left=nil;
     Nil.right=nil;
    Nil.name=new char[4];
    strcpy(Nil.name,"nil");

	return TRUE;
}


/////////////////////////////////////////////////////////////////////////////
// CAboutDlg dialog used for App About

class CAboutDlg : public CDialog
{
public:
	CAboutDlg();

// Dialog Data
	//{{AFX_DATA(CAboutDlg)
	enum { IDD = IDD_ABOUTBOX };
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CAboutDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);    // DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	//{{AFX_MSG(CAboutDlg)
		// No message handlers
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
};

CAboutDlg::CAboutDlg() : CDialog(CAboutDlg::IDD)
{
	//{{AFX_DATA_INIT(CAboutDlg)
	//}}AFX_DATA_INIT
}

void CAboutDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CAboutDlg)
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CAboutDlg, CDialog)
	//{{AFX_MSG_MAP(CAboutDlg)
		// No message handlers
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

// App command to run the dialog
void CMyApp::OnAppAbout()
{
	CAboutDlg aboutDlg;
	aboutDlg.DoModal();
}

/////////////////////////////////////////////////////////////////////////////
// CMyApp message handlers