btview.cpp

VC编程显示二叉树：输入二叉树的先序序列

// BTView.cpp : implementation of the CBTView class
//

#include "stdafx.h"
#include "BT.h"

#include "BTDoc.h"
#include "BTView.h"

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

//#define	MAX 1024;
int dataHeight=30;
int minDistance=20;//=diameter
int diameter=20;
/////////////////////////////////////////////////////////////////////////////
// CBTView

IMPLEMENT_DYNCREATE(CBTView, CView)

BEGIN_MESSAGE_MAP(CBTView, CView)
	//{{AFX_MSG_MAP(CBTView)
		// 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 printing commands
	ON_COMMAND(ID_FILE_PRINT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_DIRECT, CView::OnFilePrint)
	ON_COMMAND(ID_FILE_PRINT_PREVIEW, CView::OnFilePrintPreview)
END_MESSAGE_MAP()

/////////////////////////////////////////////////////////////////////////////
// CBTView construction/destruction

CBTView::CBTView()
{
	// TODO: add construction code here

}

CBTView::~CBTView()
{
}

BOOL CBTView::PreCreateWindow(CREATESTRUCT& cs)
{
	// TODO: Modify the Window class or styles here by modifying
	//  the CREATESTRUCT cs

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CBTView drawing

void CBTView::OnDraw(CDC* pDC)
{
	CBTDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	int i=-1;
	// TODO: add draw code for native data here
	GetClientRect(m_r);
	CPen	Pen,*ptrPen;
	Pen.CreatePen(PS_COSMETIC,1,RGB(255,0,0));
	pDC->SetBkColor(RGB(255,255,255));
	ptrPen=pDC->SelectObject(&Pen);

	this->_preGetData("bt.dat",m_data);
	this->_preCreatBT(m_bt,m_data,i);
	//this->_preDisplayBT(m_bt, pDC, m_r);
	this->_acylicInDisplayBT(m_bt, pDC, m_r);

	int depth, width, leafs;
	CString csData="",csTemp;
	this->_depthWidthLeafs(m_bt, depth, width, leafs);
	csData=csData+"深度:"; csTemp.Format("%d",depth); csData=csData+csTemp;
	csData=csData+"   宽度:"; csTemp.Format("%d",width); csData=csData+csTemp;
	csData=csData+"   叶子数:"; csTemp.Format("%d",leafs); csData=csData+csTemp;
	pDC->SetTextColor(RGB(255,0,0));
	pDC->TextOut(m_r.left,m_r.top+depth*dataHeight,csData);

	pDC->SelectObject(ptrPen);
}

/////////////////////////////////////////////////////////////////////////////
// CBTView printing

BOOL CBTView::OnPreparePrinting(CPrintInfo* pInfo)
{
	// default preparation
	return DoPreparePrinting(pInfo);
}

void CBTView::OnBeginPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add extra initialization before printing
}

void CBTView::OnEndPrinting(CDC* /*pDC*/, CPrintInfo* /*pInfo*/)
{
	// TODO: add cleanup after printing
}

/////////////////////////////////////////////////////////////////////////////
// CBTView diagnostics

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

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

CBTDoc* CBTView::GetDocument() // non-debug version is inline
{
	ASSERT(m_pDocument->IsKindOf(RUNTIME_CLASS(CBTDoc)));
	return (CBTDoc*)m_pDocument;
}
#endif //_DEBUG

/////////////////////////////////////////////////////////////////////////////
// CBTView message handlers
void CBTView::_preGetData(CString filename,char data[])
{
	FILE	*fp;
	int		i;
	char	ch;	
	fp=fopen(filename,"r");
	if(fp==NULL)
	{
		AfxMessageBox("打开数据文件"+filename+"失败!");
		return;
	}
	i=0;
	while(!feof(fp))
	{	
		ch=fgetc(fp);
		//fscanf(fp,"%c",&ch);
		data[i++]=ch;
	}
	fclose(fp);
}

void CBTView::_preCreatBT(BTnode* &root, char data[], int &i)
{
	/*************************************************************
	*按先序序列建立二叉树:
	*data[]	:正确先序序列数组,'#'对应于空树
	*i		:树根前一字符的位置,初始为-1
	**************************************************************/
	i++;
	if(data[i]=='#')
		root=NULL;
	else
	{
		root=new BTnode;
		root->data=data[i];
		_preCreatBT(root->lchild, data, i);
		_preCreatBT(root->rchild, data, i);
	}
}

void CBTView::_preDisplayBT(BTnode* root, CDC* pDC,CRect &r)
{
	//计算树根位置
	int xLeft=r.left-diameter/2;   int xRight=r.right-diameter/2;
	int y=r.top+diameter/2;
	//显示
	__preDisplayBT(root,pDC,r,xLeft, xRight, y);
}



void CBTView::__preDisplayBT(BTnode* root, CDC* pDC,CRect &r,\
						int xLeft, int xRight, int y)
{
	int x=xLeft+(xRight-xLeft)/2;
	if (root==NULL) return;
	if ( (y>r.bottom)||((xRight-xLeft)<minDistance) )
	{
		AfxMessageBox("Not enough displaying area!");
		return;
	}

	pDC->Ellipse(x-diameter/2,y-diameter/2, x+diameter/2,y+diameter/2);
	pDC->TextOut(x-5, y-8, root->data);
	if(root->lchild!=NULL)
	{
		pDC->MoveTo(x, y);
		pDC->LineTo( (xLeft+x)/2, y+dataHeight);
		__preDisplayBT(root->lchild, pDC, r, xLeft, x,y+dataHeight);
	}
	if(root->rchild!=NULL)
	{
		pDC->MoveTo(x, y);
		pDC->LineTo( (x+xRight)/2, y+dataHeight);
		__preDisplayBT(root->rchild, pDC, r, x, xRight, y+dataHeight);
	}

}

void CBTView::_acylicInDisplayBT(BTnode* root, CDC* pDC,CRect &r)
{
	BTGnode	stack[1024];
	int		top=0;
	int		xLeft=r.left+diameter/2;
	int		xRight=r.right-diameter/2;
	int		xMid=xLeft+(xRight-xLeft)/2;
	int		y=r.top+diameter/2;

	do{
		while(root!=NULL)
		{
			if ((top!=0)&&(stack[top].pBTnode->lchild==root))
			{
				pDC->MoveTo(stack[top].xLeft+\
							(stack[top].xRight-stack[top].xLeft)/2,\
							stack[top].y);
				pDC->LineTo(xMid,y);
			}
			top++;
			stack[top].pBTnode=root;
			stack[top].xLeft=xLeft;
			stack[top].xRight=xRight;
			stack[top].y=y;
			root=root->lchild;
			xLeft=xLeft;	xRight=xMid;	
			xMid=xLeft+(xRight-xLeft)/2; y=y+dataHeight; 
		}
		if (top!=0)
		{
			root=stack[top].pBTnode;
			xLeft=stack[top].xLeft;
			xRight=stack[top].xRight;
			xMid=xLeft+(xRight-xLeft)/2;
			y=stack[top].y;
			pDC->Ellipse(xMid-diameter/2,y-diameter/2, xMid+diameter/2,y+diameter/2);
			//////pDC->TextOut(root->data,xMid,y);
			pDC->TextOut(xMid-5,y-8,root->data);
			top--;
			root=root->rchild;
			if(root!=NULL)
			{
				pDC->MoveTo(xMid,y);
				xLeft=xMid;		xRight=xRight;
				xMid=xLeft+(xRight-xLeft)/2;
				y=y+dataHeight;
				pDC->LineTo(xMid,y);
			}
		}
	} while (!((top==0)&&(root==NULL)));

}


void CBTView::_depthWidthLeafs(BTnode* root, int &depth,int &width,\
								int &leafs)
{
	BTnode *que[1024];  //0-->...
	int		hp,tp,lc;
	depth=width=leafs=0;
	if(root==NULL) return;

	hp=0;	tp=1;	lc=1;	que[0]=root; width=1;
	do{

		root=que[hp];
		hp=(hp+1)%1024;
		if ( (root->lchild==NULL)&&(root->rchild==NULL) )	leafs++;
		if (root->lchild!=NULL)
		{
			if( ((tp+1)%1024)==hp)
			{AfxMessageBox("Queue is full!");return;}
			que[tp]=root->lchild;
			tp=(tp+1)%1024;
		}
		if (root->rchild!=NULL)
		{
			if( ((tp+1)%1024)==hp)
			{AfxMessageBox("Queue is full!");return;}
			que[tp]=root->rchild;
			tp=(tp+1)%1024;
		}
		if(hp==lc)
		{
			depth++;	
			if( ((tp-hp+1024)%1024)>width ) width=(tp-hp+1024)%1024;
			lc=tp;
		}

	} while(hp!=tp);

}