bstview.cpp

数据结构中的二叉搜索树

// BSTView.cpp : CBSTView 类的实现
//

#include "stdafx.h"
#include "BST.h"
#include "mainfrm.h"
#include "BSTDoc.h"
#include "BSTView.h"
#include ".\bstview.h"

#include "math.h"
#ifdef _DEBUG
#define new DEBUG_NEW
#endif


// CBSTView

IMPLEMENT_DYNCREATE(CBSTView, CView)

BEGIN_MESSAGE_MAP(CBSTView, CView)
	ON_COMMAND(ID_Insert, OnInsert)
	ON_COMMAND(ID_Search, OnSearch)
	ON_WM_SIZE()
	ON_COMMAND(ID_Pre, OnPre)
	ON_COMMAND(ID_Level, OnLevel)
	ON_COMMAND(ID_After, OnAfter)
	ON_COMMAND(ID_Mid, OnMid)
	ON_COMMAND(ID_Fei, OnFei)
	ON_COMMAND(ID_Exchange, OnExchange)
//	ON_WM_MOUSEMOVE()
//ON_WM_MOUSEMOVE()
END_MESSAGE_MAP()

// CBSTView 构造/析构

CBSTView::CBSTView()
: m_data(NULL)
{
	// TODO: 在此处添加构造代码
    first=1;

	m_R=10;
	m_Len=50;

	T=NULL;        //初始化根结点，使以下的Search()能一致；
	h=0;           //树的深度；
	leaf=0;        //树的叶子个数；
}

CBSTView::~CBSTView()
{
}

BOOL CBSTView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: 在此处通过修改 CREATESTRUCT cs 来修改窗口类或
	// 样式

	return CView::PreCreateWindow(cs);
}

// CBSTView 绘制

void CBSTView::OnDraw(CDC* pDC)
{
	CBSTDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	if (!pDoc)
		return;

	// TODO: 在此处为本机数据添加绘制代码
	if(first)
	{
        pDC->TextOut(m_x*2/3,m_y*5/8,"二叉排序树的可视化编程，在状态栏获取二叉排序树的信息");
	}
}


// CBSTView 诊断

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

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

CBSTDoc* CBSTView::GetDocument() const // 非调试版本是内联的
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CBSTDoc)));
	return (CBSTDoc*)m_pDocument;
}
#endif //_DEBUG


// CBSTView 消息处理程序
void CBSTView::Draw(Node *p,int IsHelp) //此函数为帮助在窗口中输出每个树结点；
{
	CString str;
	if(p)
	{
		str.Format("%d",p->data);
		//cout<<p->data<<' ';
		CClientDC dc(this);
		OnPrepareDC(&dc);

		CPen bluepen(PS_SOLID,3,RGB(0,0,255));
		CPen redpen(PS_SOLID,3,RGB(255,0,0));
		CPen greenpen(PS_SOLID,3,RGB(0,255,0));
		CRect rect(p->point.x-m_R,p->point.y-m_R,p->point.x+m_R,p->point.y+m_R);

		if(!IsHelp)
			dc.SelectObject(redpen);
		else
			dc.SelectObject(greenpen);
		dc.Ellipse(&rect);
		dc.DrawText(str,&rect,DT_CENTER|DT_VCENTER|DT_SINGLELINE);

		Sleep(1000);

		dc.SelectObject(bluepen);
		dc.Ellipse(&rect);
		dc.DrawText(str,&rect,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
	}
}

/***********************************************************************************/
/***********************************************************************************/

//以下代码为操作菜单上各子菜单的事件处理函数；
void CBSTView::OnInsert()  //此函数为创建菜单的处理函数；
{
	// TODO: 在此添加命令处理程序代码
	m_data=new long;
	CString str;
	CString strh;
	CString strleaf;

	if(Dlg1.DoModal()==IDOK)  //首先弹出DIALOG窗口输入数据；
	{
		*m_data=Dlg1.m_data;	
		str.Format("%d",*m_data);
		int Isin=Search(T,*m_data);//判断该数是否已存在；
		if(!Isin)
			Search(T,*m_data,1);       //创建该结点

		//确定各点的位置;
		if(last->Islchild==-1)
		{
			last->point=CPoint(m_x,m_R);
			if(first)
			{
				first=0;
				Invalidate();
				UpdateWindow();
			}
		}
		else if(last->Islchild==1)
		{
			last->point=CPoint(last->px-m_x/pow(2,last->h-1),m_R+m_Len*(last->h-1));
		}
		else if(last->Islchild==0)
		{
			last->point=CPoint(last->px+m_x/pow(2,last->h-1),m_R+m_Len*(last->h-1));
		}

        //当该数据不存在时在窗口中画出该结点； 
		if(!Isin)
		{
			CRect rect(last->point.x-m_R,last->point.y-m_R,last->point.x+m_R,last->point.y+m_R);
			CPen bluepen(PS_SOLID,3,RGB(0,0,255));
			//画圆；
			CClientDC dc(this);
			OnPrepareDC(&dc);
			dc.SelectObject(&bluepen);
			dc.Ellipse(&rect);
			dc.DrawText(str,&rect,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
			
			//画线；
			double k1,k2;
			k1=m_x/pow(2,last->h-1)/sqrt(pow(m_x/pow(2,last->h-1),2)+m_Len*m_Len);
			k2=m_Len/sqrt(pow(m_x/pow(2,last->h-1),2)+m_Len*m_Len);

			if(last->Islchild==1)
			{
				dc.MoveTo(last->point.x+m_R*k1,last->point.y-m_R*k2);
				dc.LineTo(last->px-m_R*k1,m_R+m_Len*(last->h-2)+m_R*k2);
			}
			else if(last->Islchild==0)
			{
				dc.MoveTo(last->point.x-m_R*k1,last->point.y-m_R*k2);
				dc.LineTo(last->px+m_R*k1,m_R+m_Len*(last->h-2)+m_R*k2);
			}

            //在状态栏上显示二叉排序树的信息；
			Getleaf();
			CMainFrame* pFrame=(CMainFrame *) AfxGetApp()->m_pMainWnd;
			CStatusBar* pStatus=&pFrame->m_wndStatusBar;
			strh.Format("二叉树的深度为%d",h);
			strleaf.Format("二叉排序树的叶子个数为%d",leaf);
           
			pStatus->SetPaneText(0,"二叉排序树的信息");
			pStatus->SetPaneText(1,strh);
			pStatus->SetPaneText(2,strleaf);
			leaf=0;
		}
		else //当其已存在时弹出提示窗口；
			AfxMessageBox("该数据已存在，请输入另一值");
	}
}

void CBSTView::OnSearch()//此函数为查找的处理函数；
{
	// TODO: 在此添加命令处理程序代码
	m_data=new long;

	if(Dlg2.DoModal()==IDOK)//首先弹出对话框，输入要查找的数据；
	{
		*m_data=Dlg2.m_data;
		//进行查找，分成功与不成功向用用户提示信息；
		if(!Search(T,*m_data))
			MessageBox("查找不成功","失败",MB_OKCANCEL|MB_ICONINFORMATION);
		else
			MessageBox("查找成功","成功",MB_OKCANCEL|MB_ICONINFORMATION);
	}
}

void CBSTView::OnPre()//此函数为前序遍历的处理函数；
{
	//调用前序遍历的函数；
	PreTraverse(T);
	//提示信息；
	AfxMessageBox("前序遍历已完成");
}

void CBSTView::OnLevel()//此函数为层次遍历的处理函数；
{
	//实现中序遍历；
	for(int i=1;i<=h;i++)
		PreTraverse(T,1,i); //调用前序遍历的辅助功能，从第一层到最后一层进向遍历，自创的算法；
	AfxMessageBox("层次遍历已完成"); //提示信息；
}

void CBSTView::OnMid() //此函数为中序遍历的处理函数；
{
	//调用中序遍历函数；
	InTraverse(T);
	//提示信息；
	AfxMessageBox("中序遍历已完成");
}

void CBSTView::OnAfter() //此函数为后序遍历的处理函数；
{
	//调用后序遍历函数；
	AfterTraverse(T);
	//提示信息；
	AfxMessageBox("后序遍历已完成");
}

void CBSTView::OnFei() //非递归中序遍历的处理函数；
{
	//在状态栏给出提示；
	CMainFrame* pM=(CMainFrame*) AfxGetApp()->GetMainWnd();
	CStatusBar* pS=&pM->m_wndStatusBar;
	pS->SetPaneText(0,"用绿色表示非递归过程，红色表示找到遍历点");
	
	//调用非递归中序遍历函数；
	UnInTraverse();
	//提示信息；
	AfxMessageBox("非递归中序遍历已完成");
}

void CBSTView::OnExchange() //交换子树的处理函数；
{
	//把窗口的视图清除；
	Invalidate();  
	UpdateWindow();
	//调用后序遍历的辅助功能，即交换子树功能；
	PreTraverse(T,2);
	//调用前序遍历的辅助功能，即重画各点；
	PreTraverse(T,-1);
    
	MessageBox("交换完毕!按确定后返回原状态","提示",MB_OK|MB_ICONINFORMATION);

	Sleep(1000);

	//把窗口的视图清除；
	Invalidate();  
	UpdateWindow();

	//将子树调回来，并以原状态交重画各点；
	PreTraverse(T,2);
	PreTraverse(T,-1);
}

void CBSTView::OnSize(UINT nType, int cx, int cy)
{
	CView::OnSize(nType, cx, cy);
    
	m_x=cx/2;
	m_y=cy/2;
}

/**********************************************************************************/
/**********************************************************************************/
//以下代码为二叉排序树各种功能实现的主要代码，供上面的处理函数使用；
//其中不少函数能实现多个功能，即原功能+辅助功能，黓认为原功能；
int CBSTView::Search(Node* &q, long data, int IsHelp)//
{
	static int IsFind;
	static int px=0;
	static int temph=0;	            //当协助生成时，作为结点的深度，每当查找完一个结点，就回复0； 
	static int Islchild=-1;

	if(q)                    //当结点存在时，根据功能找所示结点；
	{
		if(q->data==data)    //当所要查找的值与所在结点相等即结束；
		{
			last=q;
			IsFind=1;

			if(!IsHelp)
			{
				Draw(q);				
			}
			return IsFind;
		}
		else if(data<q->data)  //找右边，即比data大的；
		{
			if(IsHelp) {temph++; Islchild=1; px=q->point.x; Search(q->lch,data,1);}
			else {IsFind=0; Search(q->lch,data);}
		}
		else                   //找左边，即比data小的    
		{
			if(IsHelp) {temph++; Islchild=0; px=q->point.x; Search(q->rch,data,1);}
			else {IsFind=0; Search(q->rch,data);}
		}
	}
	else                           //当结点不存在时，根据其功能实现1链接功能 或 2返回0表示查找不成功；
	{
		if(IsHelp)
		{                      //找到合适位置后生成一个结点，并与q连接上；
			Node *p;

			p=new Node;
			p->data=data;
			p->h=temph+1;
			p->Islchild=Islchild;
			p->px=px;
			p->lch=NULL;
			p->rch=NULL;       //初始化p；
			last=p;

			h=h>p->h?h:p->h;      //此句为求树的深度,即比较当前结点所在层次是否为最大；
			q=p;                  //链接上q;
			temph=0;              //深度回复0,为以后的结点作准备；
			px=0;
			return p->h;
		}
		else return IsFind;
	}
	return IsFind;
}


void  CBSTView::PreTraverse(Node *p,int IsHelp,int i)    //实现前序遍历,在原来功能上+协助层次遍历的功能+在窗口输出各结点的功能；
{
	CString str;
	if(p) 
	{
		if(!IsHelp)                               //当不是协助功能时，按前序遍历算法进行；
		{
			Draw(p);

			PreTraverse(p->lch);
			PreTraverse(p->rch);
		}
		else if(IsHelp==1)      //当是层次遍历功能时
		{
			if(p->h==i)         //当到达第i层时输出；
			{
				Draw(p);

				return;
			}  //遇到第i层时，就输出，且要返回，因为其子树深度肯定比i大，不需再搜下去；
			else
			{
				PreTraverse(p->lch,1,i);           //当没到第i层，继续搜其左右子树；
				PreTraverse(p->rch,1,i);
			}
		}
		else if(IsHelp==-1)   //实现交换子树之后的画图功能；
		{
			str.Format("%d",p->data);
			CRect rect(p->point.x-m_R,p->point.y-m_R,p->point.x+m_R,p->point.y+m_R);
			CPen bluepen(PS_SOLID,3,RGB(0,0,255));
			//画圆；
			CClientDC dc(this);
			OnPrepareDC(&dc);
			dc.SelectObject(&bluepen);
			dc.Ellipse(&rect);
			dc.DrawText(str,&rect,DT_CENTER|DT_VCENTER|DT_SINGLELINE);
			//画线；
			double k1,k2;
			k1=m_x/pow(2,p->h-1)/sqrt(pow(m_x/pow(2,p->h-1),2)+m_Len*m_Len);
			k2=m_Len/sqrt(pow(m_x/pow(2,p->h-1),2)+m_Len*m_Len);

			if(p->Islchild==1)
			{
				dc.MoveTo(p->point.x+m_R*k1,p->point.y-m_R*k2);
				dc.LineTo(p->px-m_R*k1,m_R+m_Len*(p->h-2)+m_R*k2);
			}
			else if(p->Islchild==0)
			{
				dc.MoveTo(p->point.x-m_R*k1,p->point.y-m_R*k2);
				dc.LineTo(p->px+m_R*k1,m_R+m_Len*(p->h-2)+m_R*k2);
			}
			//当没到第i层，继续搜其左右子树
			PreTraverse(p->lch,-1); 
			PreTraverse(p->rch,-1);
		}
		else if(IsHelp==2)         //以下语句是在遍历过程中交换个根的左右子树；
		{
			if(p->lch && p->rch)
			{
				Node* temp;
				temp=p->lch;
				p->lch=p->rch;
				p->rch=temp;

				p->lch->px=p->point.x;
				p->lch->point.x=p->lch->px-m_x/pow(2,p->lch->h-1);
				p->lch->Islchild=1;

				p->rch->px=p->point.x;
				p->rch->point.x=p->rch->px+m_x/pow(2,p->rch->h-1);
				p->rch->Islchild=0;
			}
			else if(p->lch && !p->rch)
			{
				p->rch=p->lch;
				p->lch=NULL;

				p->rch->px=p->point.x;
				p->rch->point.x=p->rch->px+m_x/pow(2,p->rch->h-1);
				p->rch->Islchild=0;
			}
			else if(p->rch && !p->lch)
			{
				p->lch=p->rch;
				p->rch=NULL;

				p->lch->px=p->point.x;
				p->lch->point.x=p->lch->px-m_x/pow(2,p->lch->h-1);
				p->lch->Islchild=1;
			}
			PreTraverse(p->lch,2);
			PreTraverse(p->rch,2);
		}
	}
}

void  CBSTView::InTraverse(Node *p,int IsHelp)//实现中序遍历，在原来功能上加上协助求叶子结点功能,黓认功能为原始功能；
{
	CString str;
	if(p)
	{
		if(!IsHelp)                  //默认功能；
		{
			InTraverse(p->lch);     //访问左子树；
			                      
			Draw(p);               //画出结点；

			InTraverse(p->rch);    //访问右子树；
		}
		else
		{                                 //以下语句是在遍历过程中求得叶子个数；
			if(!p->lch && !p->rch) {leaf++; return;}
			InTraverse(p->lch,1);
			InTraverse(p->rch,1);
		}
	}
}

void  CBSTView::AfterTraverse(Node *p)  //实现后序遍历;
{
	if(p)
	{
		AfterTraverse(p->lch);   //递归左子树；
		AfterTraverse(p->rch);   //递归右子树；
		Draw(p);                 //画出结点；
	}
}

void CBSTView::UnInTraverse()     //实现非递归中序遍历；
{
	stack b;
	Node *p=T;
	while(p || !b.IsEmpty())
	{
		if(p) 
		{
			Draw(p,1);            //在窗口中用绿色表示非递归的路径；
			b.PushStack(p);
			p=p->lch;             //向左走到尽头；
		}
		else                         
		{
			p=b.PopStack();       //当走到左的尽头，出栈p即为根结点；
            Draw(p);              //画出结点；
			p=p->rch;             //向右走；
		}
	}
}

void CBSTView::Getleaf()
{
	InTraverse(T,1);          //利用中序遍历求叶子结点个数；
}