织梦手机网站制作中国建设部门官方网站

设有一颗二叉树如下；

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

对树进行遍历的结果是，

先序为：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__;
#endifstruct 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;/
// CBtreeViewIMPLEMENT_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 commandsON_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/destructionCBtreeView::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 csreturn CView::PreCreateWindow(cs);
}/
// CBtreeView drawingvoid CBtreeView::OnDraw(CDC* pDC)
{CBtreeDoc* pDoc = GetDocument();ASSERT_VALID(pDoc);// TODO: add draw code for native data hereCString 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 printingBOOL CBtreeView::OnPreparePrinting(CPrintInfo* pInfo)
{// default preparationreturn 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 handlersvoid 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; 控制输出的变量；

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

运行如下；