mainfrm.cpp

使用VS.NET开发的数据结构红黑树可视化图形界面演示。可以进行节点的添加及删除。

// MainFrm.cpp : CMainFrame 类的实现
//

#include "stdafx.h"
#include "RBTree.h"
#include "SDelete.h"
#include "SSelect.h"
#include "SRank.h"
#include "SInsert.h"



#include <iostream>
#include "MainFrm.h"
#include ".\mainfrm.h"
using namespace std;


#ifdef _DEBUG
#define new DEBUG_NEW
#endif

RBTree rbtree;
long insertvalue=0;
long delletevalue=0;
long select=0;
long rank=0;


// CMainFrame

IMPLEMENT_DYNCREATE(CMainFrame, CFrameWnd)

BEGIN_MESSAGE_MAP(CMainFrame, CFrameWnd)
	ON_WM_CREATE()
	ON_COMMAND(ID_INSERT, OnInsert)
	ON_COMMAND(ID_DELETE, OnDelete)
	ON_COMMAND(ID_OS_SELECT, OnOsSelect)
	ON_COMMAND(ID_OS_RANK, OnOsRank)
END_MESSAGE_MAP()



static UINT indicators[] =
{
	ID_SEPARATOR,           // 状态行指示器
	ID_INDICATOR_CAPS,
	ID_INDICATOR_NUM,
	ID_INDICATOR_SCRL,
};


// CMainFrame 构造/析构

CMainFrame::CMainFrame()
{
	// TODO: 在此添加成员初始化代码

}

CMainFrame::~CMainFrame()
{
}


int CMainFrame::OnCreate(LPCREATESTRUCT lpCreateStruct)
{
	if (CFrameWnd::OnCreate(lpCreateStruct) == -1)
		return -1;
	
	if (!m_wndToolBar.CreateEx(this, TBSTYLE_FLAT, WS_CHILD | WS_VISIBLE | CBRS_TOP
		| CBRS_GRIPPER | CBRS_TOOLTIPS | CBRS_FLYBY | CBRS_SIZE_DYNAMIC) ||
		!m_wndToolBar.LoadToolBar(IDR_MAINFRAME))
	{
		TRACE0("未能创建工具栏\n");
		return -1;      // 未能创建
	}

	if (!m_wndStatusBar.Create(this) ||
		!m_wndStatusBar.SetIndicators(indicators,
		  sizeof(indicators)/sizeof(UINT)))
	{
		TRACE0("未能创建状态栏\n");
		return -1;      // 未能创建
	}
	// TODO: 如果不需要工具栏可停靠，则删除这三行
	m_wndToolBar.EnableDocking(CBRS_ALIGN_ANY);
	EnableDocking(CBRS_ALIGN_ANY);
	DockControlBar(&m_wndToolBar);

	return 0;
}

BOOL CMainFrame::PreCreateWindow(CREATESTRUCT& cs)
{
	if( !CFrameWnd::PreCreateWindow(cs) )
		return FALSE;
	// TODO: 在此处通过修改 CREATESTRUCT cs 来修改窗口类或
	// 样式

	return TRUE;
}


// CMainFrame 诊断

#ifdef _DEBUG
void CMainFrame::AssertValid() const
{
	CFrameWnd::AssertValid();
}

void CMainFrame::Dump(CDumpContext& dc) const
{
	CFrameWnd::Dump(dc);
}

RBTree::RBTree()
{
	Nil=new(RBTreeNode);
	Nil->color=BLACK;
	Nil->leftchild=NULL;
	Nil->rightchild=NULL;
	Nil->parent=NULL;
	Nil->size=0;
	Nil->value=0;
	Nil->level=-1;
	root=Nil;
	root->parent=Nil;
	root->leftchild=Nil;
	root->rightchild=Nil;
}

int RBTree::DeleteFixColor(RBTreeNode * x)
{
	RBTreeNode * w=Nil;
	while(x!=root && x->color==BLACK)
	{
		if(x==x->parent->leftchild)
		{
			w=x->parent->rightchild;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				LeftRotate(x->parent);
				w=x->parent->rightchild;
			}//if

			if(w->leftchild->color==BLACK && w->rightchild->color==BLACK)
			{
				w->color=RED;
				x=x->parent;
			}//if
			else 
			{
				if(w->rightchild->color==BLACK)
				{
					w->leftchild->color=BLACK;
					w->color=RED;
					RightRotate(w);
					w=x->parent->rightchild;
				}//elseif

				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->rightchild->color=BLACK;
				LeftRotate(x->parent);
				x=root;
			}
		}//if
		else
		{
			w=x->parent->leftchild;
			if(w->color==RED)
			{
				w->color=BLACK;
				x->parent->color=RED;
				RightRotate(x->parent);
				w=x->parent->leftchild;
			}//if

			if(w->rightchild->color==BLACK && w->leftchild->color==BLACK)
			{
				w->color=RED;
				x=x->parent;
			}//if
			else 
			{
				if(w->leftchild->color==BLACK)
				{
					w->rightchild->color=BLACK;
					w->color=RED;
					LeftRotate(w);
					w=x->parent->leftchild;
				}//elseif

				w->color=x->parent->color;
				x->parent->color=BLACK;
				w->leftchild->color=BLACK;
				RightRotate(x->parent);
				x=root;
			}
		}
	}//while
	
	x->color=BLACK;

	return 0;
}

int RBTree::DeleteNode(RBTreeNode * z)
{
	RBTreeNode * y = Nil;
	RBTreeNode * x = Nil;
	
	if(z->leftchild==Nil||z->rightchild==Nil)
		y=z;
	else y=Successor(z);
	
	if(y->leftchild!=Nil)
		x=y->leftchild;
	else
		x=y->rightchild;

	x->parent=y->parent;

	if(y->parent==Nil)
		root=x;
	else if(y==y->parent->leftchild)
			y->parent->leftchild=x;
	else y->parent->rightchild=x;

	if(y!=z)
		z->value=y->value;
	if(y->color==BLACK)
		DeleteFixColor(x);
	
	RBTreeNode * tem = y->parent;
	while(tem!=Nil)
	{
		tem->size=tem->size-1;
		tem=tem->parent;
	}
	delete y;

	return 0;
}

int RBTree::DeleteTree(RBTreeNode * z)
{
	if(z!=Nil)
	{
		DeleteTree(z->leftchild);
		DeleteTree(z->rightchild);
		delete z;
		return 0;
	}
	else return 0;
}

int RBTree::Fixlevel(RBTreeNode * z)
{
	if(z!=Nil)
	{
		z->leftchild->level=z->level+1;
		z->rightchild->level=z->level+1;
		Fixlevel(z->leftchild);
		Fixlevel(z->rightchild);
		return 0;
	}
	else return 0;
}

RBTreeNode * RBTree::Minimum(RBTreeNode * z)
{
	while(z->leftchild!=Nil)
		z=z->leftchild;
	return z;
}

RBTreeNode * RBTree::Maximum(RBTreeNode * z)
{
	while(z->rightchild!=Nil)
		z=z->rightchild;
	return z;
}

RBTreeNode * RBTree::Successor(RBTreeNode * x)
{
	if(x->rightchild!=Nil)
		return Minimum(x->rightchild);
	RBTreeNode * y = x->parent;
	while((y!=Nil) && (x==y->rightchild))
	{
		x=y;
		y=y->parent;
	}
	return y;
}

int RBTree::InsertFixColor(RBTreeNode * z)
{
	RBTreeNode * y=Nil;

	while(z->parent->color==RED)
	{
		if(z->parent==z->parent->parent->leftchild)
		{
			y=z->parent->parent->rightchild;
			
			if(y->color==RED)
			{
				z->parent->color=BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
			}
			else
			{
				if(z==z->parent->rightchild)
				{
					z=z->parent;
					LeftRotate(z);
				}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				RightRotate(z->parent->parent);
			}
		}//if
		else
		{
			y=z->parent->parent->leftchild;
			
			if(y->color==RED)
			{
				z->parent->color=BLACK;
				y->color=BLACK;
				z->parent->parent->color=RED;
				z=z->parent->parent;
			}
			else
			{
				if(z==z->parent->leftchild)
				{
					z=z->parent;
					RightRotate(z);
				}
				z->parent->color=BLACK;
				z->parent->parent->color=RED;
				LeftRotate(z->parent->parent);
			}
		}
	}//while
	
	root->color=BLACK;
	
	
	return 0;
}

int RBTree::InsertNode(RBTreeNode * z)
{
	RBTreeNode * y = Nil;
	RBTreeNode * x = root;
	while(x!=Nil)
	{
		y=x;
		if(z->value<x->value)
			x=x->leftchild;
		else x=x->rightchild;
	}//while
	
	z->parent=y;
	
	if(y==Nil)
		root=z;
	else
	{
		if(z->value<y->value)
			y->leftchild=z;
		else y->rightchild=z;
	}//else
	
	z->leftchild=Nil;
	z->rightchild=Nil;
	z->color=RED;
	
	RBTreeNode * tmp = z->parent;
	while(tmp!=Nil)
	{
		tmp->size=tmp->size+1;
		tmp=tmp->parent;
	}
	
	InsertFixColor(z);
	
	return 0;
}

int RBTree::LeftRotate(RBTreeNode * x)
{
	RBTreeNode * y=Nil;
	y=x->rightchild;
	x->rightchild=y->leftchild;
	y->leftchild->parent=x;
	y->parent=x->parent;
	
	if(x->parent==Nil)
	{
		root=y;
	}//if
	else 
	{
		if(x==x->parent->leftchild)
			x->parent->leftchild=y;
		else
			x->parent->rightchild=y;
	}
	y->leftchild=x;
	x->parent=y;

	x->size=x->leftchild->size+x->rightchild->size+1;
	y->size=y->leftchild->size+y->rightchild->size+1;
	Fixlevel();

	return 0;
}

int RBTree::RightRotate(RBTreeNode * x)
{
	RBTreeNode * y=Nil;
	y=x->leftchild;
	x->leftchild=y->rightchild;
	y->rightchild->parent=x;
	y->parent=x->parent;
	
	if(x->parent==Nil)
	{
		root=y;
	}//if
	else 
	{
		if(x==x->parent->leftchild)
			x->parent->leftchild=y;
		else
			x->parent->rightchild=y;
	}
	y->rightchild=x;
	x->parent=y;

	x->size=x->leftchild->size+x->rightchild->size+1;
	y->size=y->leftchild->size+y->rightchild->size+1;
	Fixlevel();

	return 0;
}

int RBTree::BuildTree()
{
	long num;
	cout<<"Please input the number of treenodes:"<<endl;
	cin>>num;
	for (int i=1;i<=num;i++)
	{
		long key;
		cout<<"Please input the "<<i<<"th node's value"<<endl;
		cin>>key;
		RBTreeNode * tmp = new(RBTreeNode);
		tmp->value=key;
		tmp->leftchild=Nil;
		tmp->rightchild=Nil;
		tmp->parent=Nil;
		InsertNode(tmp);
	}
	Fixlevel();
	return 0;

}

int RBTree::PrintTree(RBTreeNode * x)
{
	if(x!=Nil)
	{
		for(int i=0;i<(x->level-1)*4;i++)
		{
			cout<<" ";
		}
		cout<<"└─";
		cout<<"color:"<<x->color<<" value"<<x->value<<" level"<<x->level<<" size"<<x->size<<endl;

		
	
		PrintTree(x->leftchild);
		PrintTree(x->rightchild);
		return 0;
		
	}
	else return 0;
}

int RBTree::PrintTree()
{
	PrintTree(root);
	return 0;
}

RBTreeNode * RBTree::FindNode(long key)
{
	RBTreeNode * tmp=root;
	if(root!=Nil)
	{
		while(tmp!=Nil && tmp->value!=key)
		{
			if(tmp->value<key)
				tmp=tmp->rightchild;
			if(tmp->value>key)
				tmp=tmp->leftchild;
		}
		return tmp;
	}
	else return Nil;
}

int RBTree::DeleteNode(long key)
{
	RBTreeNode * tmp = FindNode(key);
	if(tmp!=Nil)
	{	
		DeleteNode(tmp);
		
		return 0;
	}
	else 
	{
		AfxMessageBox("不存在这样的节点");
		return 0;
	}
}

int RBTree::DeleteNode()
{
	cout<<"Please input the value to be deleted!"<<endl;
	long key;
	cin>>key;
	DeleteNode(key);
	Fixlevel();
	return 0;
}



RBTreeNode * RBTree::OS_Select(RBTreeNode * x,long i)
{
	if(x!=Nil)
	{
		long r=x->leftchild->size+1;
		if(i==r)
			return x;
		else
		{
			if (i<r)
				return OS_Select(x->leftchild,i);
			else
				return OS_Select(x->rightchild,i-r);
		}
	}
	else return Nil;
}



long RBTree::OS_Rank(RBTreeNode * x)
{
	long r=x->leftchild->size+1;
	RBTreeNode * y=x;
	while(y!=root)
	{
		if(y==y->parent->rightchild)
			r=r+y->parent->leftchild->size+1;
		y=y->parent;
	}//while
	return r;
}

int RBTree::InsertNode(long num)
{
		RBTreeNode * tmp = new(RBTreeNode);
		tmp->value=num;
		tmp->leftchild=Nil;
		tmp->rightchild=Nil;
		tmp->parent=Nil;
		InsertNode(tmp);
		return 0;
}

int RBTree::FixPosition(RBTreeNode * node,long width)
{
	Fixlevel();
	if(node!=Nil)
	{
		int devide=1;
		for(int i=1;i<=(node->level+1);i++)
		{
			devide=devide*2;
		}
		devide++;
		
		
		node->leftchild->x=(long)((node->x)+(width/devide)/1.5);
		node->leftchild->y=(long)((node->leftchild->level)*64);
		node->rightchild->x=(long)((node->x)-(width/devide)/1.5);
		node->rightchild->y=(long)((node->rightchild->level)*64);
		

		

		FixPosition(node->leftchild,width);
		
		FixPosition(node->rightchild,width);
		return 0;
	}
	else return 0;
}

int RBTree::FixPosition(long left,long right)
{
	root->x=(long)((left+right)/2);
	root->y=0;
	FixPosition(root,right-left);

	return 0;
}

int RBTree::Show(RBTreeNode * z)
{

	

		return 0;
	
}

RBTreeNode::RBTreeNode()
{
	color=RED;
	leftchild=NULL;
	level=1;
	parent=NULL;
	rightchild=NULL;
	size=1;
	value=0;
	x=0;
	y=0;

}

RBTreeNode::~RBTreeNode()
{

}
#endif //_DEBUG


// CMainFrame 消息处理程序


void CMainFrame::OnInsert()
{
	// TODO: 在此添加命令处理程序代码
	CSInsert dlg;
	
	
	dlg.DoModal();
	
}

void CMainFrame::OnDelete()
{
	// TODO: 在此添加命令处理程序代码
	CSDelete dlg;
	dlg.DoModal();
}

void CMainFrame::OnOsSelect()
{
	// TODO: 在此添加命令处理程序代码
	CSSelect dlg;
	dlg.DoModal();
}

void CMainFrame::OnOsRank()
{
	// TODO: 在此添加命令处理程序代码
	CSRank dlg;
	dlg.DoModal();
}