ds_btreedlg.cpp

数据结构中B-树经典算法的可视化执行程序

	if(m_NodeCount!=0)
			m_CreateRandNode.SetWindowText("随机插入"); //若结点总数不为0，ID_CreateRandNode按钮上显示"随机生成"
	m_InsertData=rand()%1000;  //给m_InsertData赋值以1000以内的随机数
	UpdateData(false);	//将m_InsertData的值反馈到Edit Box上
}

void CDS_BTreeDlg::OnDeleteNode()  //删除指定结点
{
	if(UpdateData()==FALSE)  return;
	if(m_BTree==NULL)
		CreateBTree(m_TreeKey);
	if(m_BTree->Search(m_DeleteData)!=true){ //要删除的结点不存在
		MessageBox("该结点不存在！");
		m_DeleteData=rand()%1000;  //给m_DeleteData赋值以1000以内的随机数
		UpdateData(false);  //将m_DeleteData的值反馈到Edit Box上
		return;
	}
	m_BTree->Erase(m_DeleteData);  //B－树删除关键字
	m_NodeCount--;  //结点总数减1
	InvalidateRect(&m_VisRect);  //使矩形区域m_VisRect无效，系统发WM_PAINT消息重绘无效区域
	SetNodePos();  //设置B－树中各结点的位置
	if(m_NodeCount==0)
		m_CreateRandNode.SetWindowText("随机生成"); //若结点总数为0，ID_CreateRandNode按钮上显示"随机生成"
	m_DeleteData=rand()%1000;  //给m_DeleteData赋值以1000以内的随机数
	UpdateData(false);	//将m_DeleteData的值反馈到Edit Box上
}

void CDS_BTreeDlg::OnCreateRandNode()  //随机插入指定个数的结点
{
	if(m_BTree==NULL)
		CreateBTree(m_TreeKey);
	if((m_NodeCount+m_RandCount)>1000){  //现有结点数＋随机插入指定结点的个数>1000
		MessageBox("您要求的结点数超过最大上限1000");
		return;
	}
	if(UpdateData()==FALSE)  return;
	int i=0; 
	while(i!=m_RandCount){  //插入m_RandCount个结点
		int temp=rand()%1000;
		if(m_BTree->Search(temp)!=true){
			m_BTree->Insert(temp);
			i++;
		}
	}
	m_NodeCount+=i; //结点总数＝原结点总数＋i
	UpdateData(false);  //将m_NodeCount的值反馈到Edit Box上
	InvalidateRect(&m_VisRect);  //使矩形区域m_VisRect无效，系统发WM_PAINT消息重绘无效区域
	SetNodePos();  //设置B－树中各结点的位置
	m_CreateRandNode.SetWindowText("随机插入");	
}

void CDS_BTreeDlg::OnEraseall()  //清空当前树
{
	if(m_BTree==NULL)
		return;
	m_BTree->Clear(); //清空树
	m_BTree=NULL;
	m_NodeCount=0;
	UpdateData(false);  //将m_NodeCount的值反馈到Edit Box上
	m_CreateRandNode.SetWindowText("随机生成"); //ID_CreateRandNode按钮上显示"随机生成"
	pos_x=0;
	InvalidateRect(&m_VisRect);	 //使矩形区域m_VisRect无效，系统发WM_PAINT消息重绘无效区域
}

void CDS_BTreeDlg::DrawLine(BTreeNode *node) //画连接结点及其子结点的线条
{
	int startPos; //起始横坐标
	int endPos;  //结束时的横坐标
	BTreeNode *childNode;
	for(int i=0;i<node->GetDataCount()+1;i++){
		startPos=(node->NodeShowPos+i)*NodeWidth-pos_x;
		childNode=node->SonNode[i];
		endPos=(childNode->NodeShowPos+childNode->GetDataCount())*NodeWidth;
		endPos=endPos-childNode->GetDataCount()*(NodeWidth/2)-pos_x;
		DrawDC->MoveTo(startPos,node->GetDeep()*DeepHeight+NodeHeight+50);  ////
		DrawDC->LineTo(endPos,(node->GetDeep()+1)*DeepHeight+50);       ///////
	}
	
}

void CDS_BTreeDlg::DrawNode(BTreeNode *node)  //以方框的形式画出结点并显示结点的内容
{
	CString str;
	int x=0;
	int y=0;
	for(int i=0;i<node->GetDataCount();i++){
		str.Format("  %d",node->Data[i]);
		x=(node->NodeShowPos+i)*NodeWidth-pos_x;  //结点横坐标的位置
		//if((x+NodeWidth)<0 || x>(m_VisRect.right-m_VisRect.left))//当结点超出可视范围，不画
		//	continue;
		y=node->GetDeep()*DeepHeight+50; //结点纵坐标的位置
		
		//画表示结点的框及显示结点的内容
		DrawDC->TextOut(x,y,str);
		DrawDC->MoveTo(x,y);
		DrawDC->LineTo(x,y+NodeHeight);
		DrawDC->LineTo(x+NodeWidth,y+NodeHeight);
		DrawDC->LineTo(x+NodeWidth,y);
		DrawDC->LineTo(x,y);
	}
}

void CDS_BTreeDlg::DrawDetail()  //画出各结点
{
	queue<BTreeNode *> drawQue;
	BTreeNode *currNode=m_BTree->GetRoot();  //currNode为指向根结点的指针
	if(currNode->IsLeaf()){ //currNode为叶结点
		DrawNode(currNode); //在屏幕上画出结点
		return;
	}
	drawQue.push(currNode); //将currNode插入队列drawQue
	while(!drawQue.empty()){ //队列drawQue不为空
		currNode=drawQue.front();  //将队头元素赋给currNode
		drawQue.pop(); //删除队头元素
		DrawNode(currNode); //在屏幕上画出结点
		if(!currNode->IsLeaf()){
			DrawLine(currNode);  //画连接结点currNode及其子结点的线条
		}
		if(!currNode->IsLeaf()){
			for(int i=0;i<currNode->GetDataCount()+1;i++){
				drawQue.push(currNode->SonNode[i]);  //将currNode的子结点插入队列
			}
		}
	}
}

void CDS_BTreeDlg::SetLeafNodeQue(queue<BTreeNode*> & que)  //设置叶结点的队列
{
	BTreeNode *currNode=m_BTree->GetRoot(); //currNode为指向根结点的指针
	que.push(currNode); //将currNode插入队列que
	while(!currNode->IsLeaf()){
		for(int i=0;i<currNode->GetDataCount()+1;i++){
			que.push(currNode->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->SonNode[nodePos];//取得那个子结点的指针
		//根据子结点的显示位置设置父结点的显示位置
		if(currNode->GetDataCount()%2==1 ){//让父结点指向子结点的线画在子结点中间
			rightChildNode=currNode->SonNode[nodePos+1];
			nodePos=leftChildNode->NodeShowPos+leftChildNode->GetDataCount();
			nodePos=(nodePos+rightChildNode->NodeShowPos-1)/2;
		}
		else{
			nodePos=leftChildNode->NodeShowPos+leftChildNode->GetDataCount()/2;
		}
		currNode->NodeShowPos=nodePos;
		que.pop();
		//Add parent Node to parentQueue
		if(currParentNode==currNode->Parent || currNode->Parent==NULL){
			continue;//防止相同节点插入队列
		}
		else{
			que.push(currNode->Parent);
			currParentNode=currNode->Parent;
		}
	}
}

void CDS_BTreeDlg::SetNodePos() //设置B－树中各结点的位置
{
	queue<BTreeNode *> leafNodeQue;
	queue<BTreeNode *> parentNodeQue;
	SetLeafNodeQue(leafNodeQue);
	BTreeNode *currNode;
	BTreeNode *currParentNode=NULL;
	int nodePos=1;
	while(!leafNodeQue.empty()){
		//setPosition
		currNode=leafNodeQue.front();
		currNode->NodeShowPos=nodePos;
		nodePos=nodePos+currNode->GetDataCount()+1;
		leafNodeQue.pop();
		//Add parent Node to parentQueue
		if(currParentNode==currNode->Parent || currNode->Parent==NULL){
			continue;//防止相同节点插入队列
		}
		else{
			parentNodeQue.push(currNode->Parent);
			currParentNode=currNode->Parent;
		}
	}
	MaxWidth=nodePos*NodeWidth;
	while(!parentNodeQue.empty()){
		SetParentNodePos(parentNodeQue);
	}
}

void CDS_BTreeDlg::SetDC() //设置画图的DC
{
	Board=(CStatic*)GetDlgItem(IDC_BOARD); //获得一个指向标识为IDC_BOARD的控件(这里是一个CStatic)的指针. 然后你可以控制它的一些状态
	Board->GetClientRect(&m_VisRect);
	m_VisRect.right+=15;
	m_VisRect.bottom+=15;
	DrawDC=new CClientDC(Board);
	DrawDC->SetBkMode(TRANSPARENT);           //设置场景中的文字背景
	DrawDC->SetTextColor(RGB(0,255,255));     //设置场景中的文字颜色
	m_Pen.CreatePen(PS_SOLID,2,RGB(237,108,20));  //设置场景中的线条的粗细和颜色
	DrawDC->SelectObject(m_Pen);
}

void CDS_BTreeDlg::OnHScroll(UINT nSBCode, UINT nPos, CScrollBar* pScrollBar) //滚动条属性设置
{
	switch(nSBCode) {  //滚动条的通知消息码
	case SB_LINELEFT:  //向左滚动一列
	case SB_PAGELEFT:  //向左滚动一页
		if(pos_x>0)  //控制滚动，使超出可视范围部分不画
			pos_x-=MaxWidth/20;
		else 
			return;
		break;
	case SB_LINERIGHT: //向右滚动一列
	case SB_PAGERIGHT: //向右滚动一页
		if(pos_x<MaxWidth-m_VisRect.right)
			pos_x+=MaxWidth/20;
		else
			return;
		break;
	case SB_THUMBTRACK:  //滚动框被拖动
		if(nPos<MaxWidth-m_VisRect.right)
			pos_x=nPos;
		break;
	default:
		return;
	}
	CDialog::OnHScroll(nSBCode, nPos, pScrollBar);
	InvalidateRect(&m_VisRect);
}

void CDS_BTreeDlg::OnAbout() 
{
    CAboutDlg about;
	about.DoModal();	
}

void CDS_BTreeDlg::Onhelp() 
{
	// TODO: Add your control notification handler code here
	ShellExecute(NULL,"open","help.chm",NULL,NULL,SW_SHOW );
}