bitreeview.cpp

数据结构——树 不详细介绍了

// bitreeView.cpp : implementation of the CBitreeView class
//

#include "stdafx.h"
#include "bitree.h"

#include "bitreeDoc.h"
#include "bitreeView.h"

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

#include "treeinput.h"

/////////////////////////////////////////////////////////////////////////////
// CBitreeView

IMPLEMENT_DYNCREATE(CBitreeView, CView)

BEGIN_MESSAGE_MAP(CBitreeView, CView)
	//{{AFX_MSG_MAP(CBitreeView)
	ON_COMMAND(IDM_BITREE_INIT, OnBitreeInit)
	ON_COMMAND(IDM_BITREE_CREATE, OnBitreeCreate)
	ON_COMMAND(IDM_BITREE_INORDER, OnBitreeInorder)
	ON_COMMAND(IDM_BITREE_POSTORDER, OnBitreePostorder)
	ON_COMMAND(IDM_BITREE_PREORDER, OnBitreePreorder)
	//}}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()

//程序暂停，单位为 秒

void pause(float ftime){
 time_t start,end;
 time(&start);
 do{
	 time(&end);
 }while((end-start)<ftime);


}

//二叉树结点结构

struct node
{ 
	int data;
	struct node *lch,*rch;
};

//定义二叉树
struct node root_tree;

//初始化二叉树
void Init_tree(struct node * ptree){
	ptree->lch = ptree->rch = NULL;
}
//先序遍历算法 
//入口包括 二叉树根结点指针， 窗口描述表指针， 根结点内容显示位置，和结点在二叉树中的层数
void PreOrder (struct node *root, CDC *pdc, int x, int y,int m) 
 { 
	 char str[40];

     // 获得窗口类指针，用于使要显示的内容在执行完相应语句后立即显示在屏幕上
	 CWnd *pWnd;
	 pWnd = pdc->GetWindow();  
	 


	 if (root!=NULL)   //递归的终止条件
	 {
		 m*=2;      //子结点的层数
		 wsprintf(str, " %d ", root->data); 
		 pdc->TextOut(x,y,str);  //显示结点数据内容

		 //画与子结点的连线
		 if(root->lch){
			 pdc->MoveTo(x,y);
			 pdc->LineTo(x-500/m,y+50);

		 }
		 
		 if(root->rch){
			 pdc->MoveTo(x,y);
			 pdc->LineTo(x+500/m,y+50);
		 }

		 //通过屏幕更新命令，让结点内容和连线立即在屏幕上显示出来

	     pWnd->Invalidate(FALSE);
		 pause(1);   //程序延迟，以便观察效果

		 PreOrder(root->lch, pdc, x-500/m, y+50,m); //递归 遍历左子树
		 PreOrder(root->rch, pdc, x+500/m, y+50,m); // 递归 遍历右子树
      }
     }

void InOrder (struct node *root, CDC *pdc, int x, int y, int m) 
{ 
	 char str[40];
	 CWnd *pWnd;
	 pWnd = pdc->GetWindow();
	 

	 
	 if (root!=NULL) 
     {
		 m*=2;
		 InOrder(root->lch, pdc, x-500/m, y+50,m); 
			wsprintf(str, " %d ", root->data);
			pdc->TextOut(x,y,str);
			if(root->lch!=NULL){
				pdc->MoveTo(x,y);
				pdc->LineTo(x-500/m,y+50);

			}
			if(root->rch!=NULL){
				pdc->MoveTo(x,y);
				pdc->LineTo(x+500/m,y+50);
			}

		 
		 pWnd->Invalidate(FALSE);
		 pause(1);
			
		 InOrder(root->rch, pdc, x+500/m, y+50,m);
      }
}

void PostOrder (struct node *root, CDC *pdc, int x, int y, int m) 
{ 
	 char str[40];

	 CWnd *pWnd;
	 pWnd = pdc->GetWindow();
	 

	 if (root!=NULL) 
     {
		 m*=2;
		 PostOrder(root->lch, pdc, x-500/m, y+50, m); 
		 PostOrder(root->rch, pdc, x+500/m, y+50, m);
		 wsprintf(str, "%d,", root->data);  
		 pdc->TextOut(x,y,str);
		 
		 if(root->lch){
			 pdc->MoveTo(x,y);
			 pdc->LineTo(x-500/m,y+50);
		 }
		 if(root->rch){
			 pdc->MoveTo(x,y);
			 pdc->LineTo(x+500/m,y+50);
		 }


		 pWnd->Invalidate(FALSE);
		 pause(1);
		 
      }
}


/////////////////////////////////////////////////////////////////////////////
// CBitreeView construction/destruction

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

}

CBitreeView::~CBitreeView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/////////////////////////////////////////////////////////////////////////////
// CBitreeView drawing

void CBitreeView::OnDraw(CDC* pDC)
{
	CBitreeDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
}

/////////////////////////////////////////////////////////////////////////////
// CBitreeView printing

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CBitreeView diagnostics

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

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

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

/////////////////////////////////////////////////////////////////////////////
// CBitreeView message handlers

void CBitreeView::OnBitreeInit() 
{
	// TODO: Add your command handler code here
	Init_tree(&root_tree);
	
}

void CBitreeView::OnBitreeCreate() 
{
	// TODO: Add your command handler code here
	
	struct node *pnodeleft, *pnoderight;
	struct node *ptree;
	ptree= &root_tree;
	TreeInput TreeInputDlg;
	TreeInputDlg.DoModal();
	
	pnodeleft = (struct node *)malloc(sizeof(struct node));
	pnodeleft->data = TreeInputDlg.m_3_1;
	pnodeleft->lch = pnodeleft->rch = NULL;

	pnoderight = (struct node *)malloc(sizeof(struct node));
    pnoderight->data = TreeInputDlg.m_3_2;
	pnoderight->lch = pnoderight->rch = NULL;
	
	struct node *pnode21 = (struct node *)malloc(sizeof(struct node));
	pnode21->data = TreeInputDlg.m_2_1;
	pnode21->lch = pnodeleft;
	pnode21->rch = pnoderight;

	pnodeleft = (struct node *)malloc(sizeof(struct node));
	pnodeleft->data = TreeInputDlg.m_3_3;
	pnodeleft->lch = pnodeleft->rch = NULL;

	pnoderight = (struct node *)malloc(sizeof(struct node));
    pnoderight->data = TreeInputDlg.m_3_4;
	pnoderight->lch = pnoderight->rch = NULL;
	
	struct node *pnode22 = (struct node *)malloc(sizeof(struct node));
	pnode22->data = TreeInputDlg.m_2_2;
	pnode22->lch = pnodeleft;
	pnode22->rch = pnoderight;

	pnodeleft = (struct node *)malloc(sizeof(struct node));
	pnodeleft->data = TreeInputDlg.m_3_5;
	pnodeleft->lch = pnodeleft->rch = NULL;

	pnoderight = (struct node *)malloc(sizeof(struct node));
    pnoderight->data = TreeInputDlg.m_3_6;
	pnoderight->lch = pnoderight->rch = NULL;
	
	struct node *pnode23 = (struct node *)malloc(sizeof(struct node));
	pnode23->data = TreeInputDlg.m_2_3;
	pnode23->lch = pnodeleft;
	pnode23->rch = pnoderight;

	pnodeleft = (struct node *)malloc(sizeof(struct node));
	pnodeleft->data = TreeInputDlg.m_3_7;
	pnodeleft->lch = pnodeleft->rch = NULL;

	pnoderight = (struct node *)malloc(sizeof(struct node));
    pnoderight->data = TreeInputDlg.m_3_8;
	pnoderight->lch = pnoderight->rch = NULL;
	
	struct node *pnode24 = (struct node *)malloc(sizeof(struct node));
	pnode24->data = TreeInputDlg.m_2_4;
	pnode24->lch = pnodeleft;
	pnode24->rch = pnoderight;

	struct node *pnode11 = (struct node *)malloc(sizeof(struct node));
	pnode11->data = TreeInputDlg.m_1_1;
	pnode11->lch = pnode21;
	pnode11->rch = pnode22;

	struct node *pnode12 = (struct node *)malloc(sizeof(struct node));
	pnode12->data = TreeInputDlg.m_1_2;
	pnode12->lch = pnode23;
	pnode12->rch = pnode24;

	root_tree.data = TreeInputDlg.m_0;
	root_tree.lch = pnode11;
	root_tree.rch = pnode12;


}


 
void CBitreeView::OnBitreeInorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();
	CWnd *pWnd;
	RECT sRect; 
	pWnd = pdc->GetWindow();  


	InOrder(&root_tree, pdc, 500,50,1);
   

}

void CBitreeView::OnBitreePostorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();
	CWnd *pWnd;
	 pWnd = pdc->GetWindow();  
	 
	PostOrder(&root_tree,pdc, 500,50,1);
}

void CBitreeView::OnBitreePreorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();
	Invalidate(TRUE);
	PreOrder(&root_tree,pdc, 500,50,1);
	
}