ds_btreedlg.cpp

来自「数据结构B树算法的演示程序 包括添加删除节点」· C++ 代码 · 共 500 行

// DS_BTreeDlg.cpp : implementation file
//

#include "stdafx.h"
#include "DS_BTree.h"
#include "DS_BTreeDlg.h"
#include "BTree.h"

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

/////////////////////////////////////////////////////////////////////////////
// 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)
	//}}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()

/////////////////////////////////////////////////////////////////////////////
// CDS_BTreeDlg dialog

CDS_BTreeDlg::CDS_BTreeDlg(CWnd* pParent /*=NULL*/)
	: CDialog(CDS_BTreeDlg::IDD, pParent)
{
	//{{AFX_DATA_INIT(CDS_BTreeDlg)
	m_DeleteData = 0;
	m_InsertData = 0;
	m_RandCount = 0;
	m_NodeCount = 0;
	m_TreeKey = 0;
	//}}AFX_DATA_INIT
	// Note that LoadIcon does not require a subsequent DestroyIcon in Win32
	m_hIcon = AfxGetApp()->LoadIcon(IDR_MAINFRAME);
}

void CDS_BTreeDlg::DoDataExchange(CDataExchange* pDX)
{
	CDialog::DoDataExchange(pDX);
	//{{AFX_DATA_MAP(CDS_BTreeDlg)
	DDX_Control(pDX, ID_CreateRandNode, m_CreateRandNode);
	DDX_Control(pDX, IDC_RAND_SPIN, m_RandSpin);
	DDX_Text(pDX, IDC_DELETE_DATA, m_DeleteData);
	DDV_MinMaxInt(pDX, m_DeleteData, 0, 999);
	DDX_Text(pDX, IDC_INSERT_DATA, m_InsertData);
	DDV_MinMaxInt(pDX, m_InsertData, 0, 999);
	DDX_Text(pDX, IDC_RAND_COUNT, m_RandCount);
	DDV_MinMaxInt(pDX, m_RandCount, 0, 100);
	DDX_Text(pDX, IDC_NODE_COUNT, m_NodeCount);
	DDX_Text(pDX, IDC_TREE_KEY, m_TreeKey);
	DDV_MinMaxInt(pDX, m_TreeKey, 3, 20);
	//}}AFX_DATA_MAP
}

BEGIN_MESSAGE_MAP(CDS_BTreeDlg, CDialog)
	//{{AFX_MSG_MAP(CDS_BTreeDlg)
	ON_WM_SYSCOMMAND()
	ON_WM_PAINT()
	ON_WM_QUERYDRAGICON()
	ON_BN_CLICKED(IDC_SET_TREE_KEY, OnSetTreeKey)
	ON_BN_CLICKED(IDC_INSERT_NODE, OnInsertNode)
	ON_BN_CLICKED(IDC_DELETE_NODE, OnDeleteNode)
	ON_BN_CLICKED(ID_CreateRandNode, OnCreateRandNode)
	ON_BN_CLICKED(IDC_ERASEALL, OnEraseall)
	ON_WM_HSCROLL()
	//}}AFX_MSG_MAP
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CDS_BTreeDlg message handlers

BOOL CDS_BTreeDlg::OnInitDialog()
{
	CDialog::OnInitDialog();

	// Add "About..." menu item to system menu.

	// IDM_ABOUTBOX must be in the system command range.
	ASSERT((IDM_ABOUTBOX & 0xFFF0) == IDM_ABOUTBOX);
	ASSERT(IDM_ABOUTBOX < 0xF000);

	CMenu* pSysMenu = GetSystemMenu(FALSE);
	if (pSysMenu != NULL)
	{
		CString strAboutMenu;
		strAboutMenu.LoadString(IDS_ABOUTBOX);
		if (!strAboutMenu.IsEmpty())
		{
			pSysMenu->AppendMenu(MF_SEPARATOR);
			pSysMenu->AppendMenu(MF_STRING, IDM_ABOUTBOX, strAboutMenu);
		}
	}

	// Set the icon for this dialog.  The framework does this automatically
	//  when the application's main window is not a dialog
	SetIcon(m_hIcon, TRUE);			// Set big icon
	SetIcon(m_hIcon, FALSE);		// Set small icon
	
	// TODO: Add extra initialization here

	srand(time(0)); //用来设置随机时间的种子,使rand得到的随机数不一样
	pos_x=0;
	m_NodeCount=0;             //结点数
	m_InsertData=rand()%1000;  // 随机插入的结点
	m_DeleteData=rand()%1000;  // 随机删除的结点
	m_RandCount=10;            //随机插入的结点数
	m_TreeKey=3;               //树的阶初始
	m_pBTree=NULL;
	m_NodeWidth=38;            //结点的宽
	m_DeepHeight=15;           //结点的高
	SetDC();
	m_RandSpin.SetRange(0,100);
	m_hScroll=(CScrollBar *)GetDlgItem(IDC_H_SCROLL_BAR);//获得一个指向标识为IDC_H_SCROLL_BAR的控件(这里是一个ScrollBar)的指针. 然后你可以控制它的一些状态
	UpdateData(false);
	
	return TRUE;  // return TRUE  unless you set the focus to a control
}

void CDS_BTreeDlg::OnSysCommand(UINT nID, LPARAM lParam)
{
	if ((nID & 0xFFF0) == IDM_ABOUTBOX)
	{
		CAboutDlg dlgAbout;
		dlgAbout.DoModal();
	}
	else
	{
		CDialog::OnSysCommand(nID, lParam);
	}
}

// If you add a minimize button to your dialog, you will need the code below
//  to draw the icon.  For MFC applications using the document/view model,
//  this is automatically done for you by the framework.

void CDS_BTreeDlg::OnPaint() 
{
	if (IsIconic())
	{
		CPaintDC dc(this); // device context for painting

		SendMessage(WM_ICONERASEBKGND, (WPARAM) dc.GetSafeHdc(), 0);

		// Center icon in client rectangle
		int cxIcon = GetSystemMetrics(SM_CXICON);
		int cyIcon = GetSystemMetrics(SM_CYICON);
		CRect rect;
		GetClientRect(&rect);
		int x = (rect.Width() - cxIcon + 1) / 2;
		int y = (rect.Height() - cyIcon + 1) / 2;

		// Draw the icon
		dc.DrawIcon(x, y, m_hIcon);
	}
	else
	{
		CDialog::OnPaint();

	//*****************add my code***********************************
	if(m_pBTree!=NULL)
		DrawDetail();
	m_hScroll->SetScrollRange(0,m_MaxWidth);
	m_hScroll->SetScrollPos(pos_x);
	}
}

// The system calls this to obtain the cursor to display while the user drags
//  the minimized window.
HCURSOR CDS_BTreeDlg::OnQueryDragIcon()
{
	return (HCURSOR) m_hIcon;
}


void CDS_BTreeDlg::CreateBTree(int key)
{
	if(m_pBTree!=NULL){
		if(m_pBTree->GetKey()!=m_TreeKey){//若没有改变阶数，不做处理
			OnEraseall();
			delete m_pBTree;
		}
		else
			return;
	}
	m_pBTree=new BTree(key);
	m_NodeHeight=m_pBTree->GetRoot()->GetKEY()*15;  //设置树各层之间的距离
}


void CDS_BTreeDlg::OnSetTreeKey() 
{
	if(UpdateData()==FALSE)  return;
	CreateBTree(m_TreeKey);
	UpdateData(false);
}

void CDS_BTreeDlg::OnInsertNode() 
{

	if(UpdateData()==FALSE)  return;
	if(m_pBTree==NULL)
		CreateBTree(m_TreeKey);
	if(m_pBTree->Search(m_InsertData)==true){
		MessageBox("该结点已经存在！");
		m_InsertData=rand()%1000;
		UpdateData(false);
		return;
	}
	m_pBTree->Insert(m_InsertData);
	m_NodeCount++;
	InvalidateRect(&m_VisRect);
	SetNodePos();
	if(m_NodeCount!=0)
			m_CreateRandNode.SetWindowText("随机插入");
	m_InsertData=rand()%1000;
	UpdateData(false);	
}

void CDS_BTreeDlg::OnDeleteNode() 
{
	if(UpdateData()==FALSE)  return;
	if(m_pBTree==NULL)
		CreateBTree(m_TreeKey);
	if(m_pBTree->Search(m_DeleteData)!=true){
		MessageBox("该结点不存在！");
		m_DeleteData=rand()%1000;
		UpdateData(false);
		return;
	}
	m_pBTree->Erase(m_DeleteData);
	m_NodeCount--;
	InvalidateRect(&m_VisRect);
	SetNodePos();
	if(m_NodeCount==0)
		m_CreateRandNode.SetWindowText("随机生成");
	m_DeleteData=rand()%1000;
	UpdateData(false);	
}

void CDS_BTreeDlg::OnCreateRandNode() 
{
	if(m_pBTree==NULL)
		CreateBTree(m_TreeKey);
	if((m_NodeCount+m_RandCount)>1000){
		MessageBox("您要求的结点数超过最大上限1000");
		return;
	}
	if(UpdateData()==FALSE)  return;
	int i=0;
	TRACE("%d",m_RandCount);
	while(i!=m_RandCount){
		int temp=rand()%1000;
		if(m_pBTree->Search(temp)!=true){
			m_pBTree->Insert(temp);
			i++;
		}
	}
	m_NodeCount+=i;
	UpdateData(false);
	InvalidateRect(&m_VisRect);
	SetNodePos();
	m_CreateRandNode.SetWindowText("随机插入");	
}

void CDS_BTreeDlg::OnEraseall() 
{
	if(m_pBTree==NULL)
		return;
	m_pBTree->Clear();
	m_pBTree=NULL;
	m_NodeCount=0;
	UpdateData(false);
	m_CreateRandNode.SetWindowText("随机生成");
	pos_x=0;
	InvalidateRect(&m_VisRect);	
}


void CDS_BTreeDlg::DrawDetail()
{
	queue<BTreeNode *> drawQue;
	BTreeNode *currNode=m_pBTree->GetRoot();
	if(currNode->IsLeaf()){//只有一个节点
		DrawNode(currNode);
		return;
	}
	drawQue.push(currNode);
	while(!drawQue.empty()){
		currNode=drawQue.front();
		drawQue.pop();
		DrawNode(currNode);
		if(!currNode->IsLeaf()){
			DrawLine(currNode);
		}
		if(!currNode->IsLeaf()){
			for(int i=0;i<currNode->GetDataCount()+1;i++){
				drawQue.push(currNode->m_SonNode[i]);
			}
		}
	}
}

void CDS_BTreeDlg::GetLeafNodeQue(queue<BTreeNode*> & que)
{
	BTreeNode *currNode=m_pBTree->GetRoot();
	que.push(currNode);
	while(!currNode->IsLeaf()){
		for(int i=0;i<currNode->GetDataCount()+1;i++){
			que.push(currNode->m_SonNode[i]);
		}
		que.pop();
		currNode=que.front();
	}
}

void CDS_BTreeDlg::SetParentNodePos(queue<BTreeNode*> & que)
{
	BTreeNode *currNode=NULL;
	BTreeNode *leftChildNode=NULL;
	BTreeNode *rightChildNode=NULL;
	BTreeNode *currParentNode=NULL;
	int nodePos;
	int nodeCount=que.size();
	for (nodeCount=que.size();nodeCount!=0;nodeCount--) {
		//setPosition
		currNode=que.front();
		nodePos=currNode->GetDataCount()/2;//找到最中间的子节点的位置，位置从0开始
		leftChildNode=currNode->m_SonNode[nodePos];//取得那个子结点的指针
		//根据子结点的显示位置设置父节点的显示位置
		if(currNode->GetDataCount()%2==1 ){//让父节点指向子节点的线画在子节点中间
			rightChildNode=currNode->m_SonNode[nodePos+1];
			nodePos=leftChildNode->m_NodeShowPos+leftChildNode->GetDataCount();
			nodePos=(nodePos+rightChildNode->m_NodeShowPos-1)/2;
		}
		else{
			nodePos=leftChildNode->m_NodeShowPos+leftChildNode->GetDataCount()/2;
		}
		currNode->m_NodeShowPos=nodePos;
		que.pop();
		//Add parent Node to parentQueue
		if(currParentNode==currNode->m_Parent || currNode->m_Parent==NULL){
			continue;//防止相同节点插入队列
		}
		else{
			que.push(currNode->m_Parent);
			currParentNode=currNode->m_Parent;
		}
	}
}

void CDS_BTreeDlg::SetNodePos()
{
	queue<BTreeNode *> leafNodeQue;
	queue<BTreeNode *> parentNodeQue;
	GetLeafNodeQue(leafNodeQue);
	BTreeNode *currNode;
	BTreeNode *currParentNode=NULL;
	int nodePos=1;
	while(!leafNodeQue.empty()){
		//setPosition
		currNode=leafNodeQue.front();
		currNode->m_NodeShowPos=nodePos;
		nodePos=nodePos+currNode->GetDataCount()+1;
		leafNodeQue.pop();
		//Add parent Node to parentQueue
		if(currParentNode==currNode->m_Parent || currNode->m_Parent==NULL){
			continue;//防止相同节点插入队列
		}
		else{
			parentNodeQue.push(currNode->m_Parent);
			currParentNode=currNode->m_Parent;
		}
	}
	m_MaxWidth=nodePos*m_NodeWidth;
	while(!parentNodeQue.empty()){
		SetParentNodePos(parentNodeQue);
	}
}

void CDS_BTreeDlg::DrawLine(BTreeNode *node)
{
	int startPos;
	int endPos;
	BTreeNode *childNode;
	for(int i=0;i<node->GetDataCount()+1;i++){
		startPos=(node->m_NodeShowPos+i)*m_NodeWidth-pos_x;
		childNode=node->m_SonNode[i];
		endPos=(childNode->m_NodeShowPos+childNode->GetDataCount())*m_NodeWidth;
		endPos=endPos-childNode->GetDataCount()*(m_NodeWidth/2)-pos_x;
		m_DrawDC->MoveTo(startPos,node->GetDeep()*m_NodeHeight+m_DeepHeight+50);  ////
		m_DrawDC->LineTo(endPos,(node->GetDeep()+1)*m_NodeHeight+50);       ///////
	}
	
}

void CDS_BTreeDlg::DrawNode(BTreeNode *node)
{
	CString str;
	int x=0;
	int y=0;
	int rightTop=0;
	int rightBottom=0;
	for(int i=0;i<node->GetDataCount();i++){
		str.Format("  %d",node->m_Data[i]);
		x=(node->m_NodeShowPos+i)*m_NodeWidth-pos_x;
		if((x+m_NodeWidth)<0 || x>(m_VisRect.right-m_VisRect.left))//当节点超出可视范围，不画
			continue;
		y=node->GetDeep()*m_NodeHeight+50; ////
		m_DrawDC->TextOut(x,y,str);
		m_DrawDC->MoveTo(x,y);
		m_DrawDC->LineTo(x,y+m_DeepHeight);
		m_DrawDC->LineTo(x+m_NodeWidth,y+m_DeepHeight);
		m_DrawDC->LineTo(x+m_NodeWidth,y);
		m_DrawDC->LineTo(x,y);
	}
}

void CDS_BTreeDlg::SetDC()
{
	m_Board=(CStatic*)GetDlgItem(IDC_BOARD);
	m_Board->GetClientRect(&m_VisRect);
	m_VisRect.right+=15;
	m_VisRect.bottom+=15;
	m_DrawDC=new CClientDC(m_Board);
	m_DrawDC->SetBkMode(TRANSPARENT);           //设置场景中的文字背景
	m_DrawDC->SetTextColor(RGB(56,56,206));     //设置场景中的文字颜色
	m_Pen.CreatePen(PS_SOLID,2,RGB(21,250,4));  //设置场景中的线条的粗细和颜色
	m_DrawDC->SelectObject(m_Pen);
}

void CDS_BTreeDlg::OnHScroll(UINT nSBCode, UINT nPos, CScrollBar* pScrollBar) 
{
	CString str;
	switch(nSBCode) {
	case SB_LINELEFT:
	case SB_PAGELEFT:
		if(pos_x>0)  //控制滚动，使超出可视范围部分不画
			pos_x-=m_MaxWidth/10;
		else 
			return;
		break;
	case SB_LINERIGHT:
	case SB_PAGERIGHT:
		if(pos_x<m_MaxWidth-m_VisRect.right)
			pos_x+=m_MaxWidth/10;
		else
			return;
		break;
	case SB_THUMBTRACK:
		if(nPos<m_MaxWidth-m_VisRect.right+50)
			pos_x=nPos;
		TRACE("%d\n",nPos);
		break;
	default:
		return;
	}
	CDialog::OnHScroll(nSBCode, nPos, pScrollBar);
	InvalidateRect(&m_VisRect);
}