二叉树MFC实现

设有一颗二叉树如下；

这似乎是一颗经常用作示例的二叉树；

对树进行遍历的结果是，

先序为：3、2、2、3、8、6、5、4，
中序为：2、2、3、3、4、5、6、8，
后序为2、3、2、4、5、6、8、3；

下面VC6看一下；单文档工程；

全部的视类CPP代码；

// btreeView.cpp : implementation of the CBtreeView class
//

#include "stdafx.h"
#include "btree.h"

#include "btreeDoc.h"
#include "btreeView.h"

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

struct TreeNode {
	int val;
	struct TreeNode *left;
	struct TreeNode *right;
};

void PreOrderTree(struct TreeNode*, CDC*, int);
void InOrderTree(struct TreeNode*, CDC*, int);
void PostOrderTree(struct TreeNode*, CDC*, int);
int maxDepth(struct TreeNode* );

int col = 0;

/
// CBtreeView

IMPLEMENT_DYNCREATE(CBtreeView, CView)

BEGIN_MESSAGE_MAP(CBtreeView, CView)
	//{{AFX_MSG_MAP(CBtreeView)
		// 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()

/
// CBtreeView construction/destruction

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

}

CBtreeView::~CBtreeView()
{
}

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

	return CView::PreCreateWindow(cs);
}

/
// CBtreeView drawing

void CBtreeView::OnDraw(CDC* pDC)
{
	CBtreeDoc* pDoc = GetDocument();
	ASSERT_VALID(pDoc);
	// TODO: add draw code for native data here
	CString str1;
	struct TreeNode nodea = { 3, NULL, NULL };
	struct TreeNode nodeb = { 2, NULL, NULL };
	struct TreeNode nodec = { 2, NULL, NULL };
	struct TreeNode noded = { 3, NULL, NULL };
	struct TreeNode nodee = { 8, NULL, NULL };
	struct TreeNode nodef = { 6, NULL, NULL };
	struct TreeNode nodeg = { 5, NULL, NULL };
	struct TreeNode nodeh = { 4, NULL, NULL };

	nodea.left = &nodeb;
	nodea.right = &nodee;
	nodeb.left = &nodec;
	nodeb.right = &noded;
	nodee.left = &nodef;
	nodef.left = &nodeg;
	nodeg.left = &nodeh;

	pDC->TextOut(20,30,"先序：");
	PreOrderTree(&nodea, pDC, 50);
	col=0;
	pDC->TextOut(20,80,"中序：");
	InOrderTree(&nodea, pDC, 100);
	col=0;
	pDC->TextOut(20,130,"后序：");
	PostOrderTree(&nodea, pDC, 150);

	int dp = maxDepth(&nodea);
	str1.Format("树的深度：%d", dp);
	pDC->TextOut(20,180,str1);
}

/
// CBtreeView printing

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

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

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

/
// CBtreeView diagnostics

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

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

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

/
// CBtreeView message handlers

void PreOrderTree(struct TreeNode* root, CDC* pDC, int rows) {
	CString str1;
	if (root == NULL) {
		return;
	}
	str1.Format("%d", root->val);
	pDC->TextOut(50+col*30, rows, str1);
	col=col+1;
	PreOrderTree(root->left,pDC,rows);
	PreOrderTree(root->right,pDC,rows);
}

void InOrderTree(struct TreeNode* root, CDC* pDC, int rows) {
	CString str1;
	if (root == NULL) {
		return;
	}
	InOrderTree(root->left, pDC, rows);
	str1.Format("%d", root->val);
	pDC->TextOut(50+col*30, rows, str1);
	col=col+1;
	InOrderTree(root->right, pDC, rows);
}

void PostOrderTree(struct TreeNode* root, CDC* pDC, int rows) {
	CString str1;
	if (root == NULL) {
		return;
	}
	PostOrderTree(root->left, pDC, rows);
	PostOrderTree(root->right, pDC, rows);
	str1.Format("%d", root->val);
	pDC->TextOut(50+col*30, rows, str1);
	col=col+1;
}

int maxDepth(struct TreeNode* root) {
	if (root == NULL) {
		return 0;
	}
	else {
		int maxLeft = maxDepth(root->left), maxRight = maxDepth(root->right);
		if (maxLeft > maxRight) {
			return 1 + maxLeft;
		}
		else {
			return 1 + maxRight;
		}
	}
}

struct TreeNode {...}，这是树的节点，节点中存储一个整数；

void PreOrderTree(struct TreeNode*, CDC*, int); 先序遍历函数；
void InOrderTree(struct TreeNode*, CDC*, int);中序遍历函数；
void PostOrderTree(struct TreeNode*, CDC*, int);后序遍历函数；后2个参数是控制输出的；
int maxDepth(struct TreeNode* ); 求深度；

int col = 0; 控制输出的变量；

 一般控制台程序是按树输入节点来创建树；窗口的暂时不太好一行行输入节点，在代码中创建节点和节点关系；

运行如下；