bintree.cpp

一个简单还原二叉树并在屏幕输出树形的小程序

#include "stdafx.h"
#include "Dialog.h"
#include "DialogDlg.h"
#include "BinTree.h"

CBinTreeNode::CBinTreeNode(char cVal,CBinTreeNode * pLeft, CBinTreeNode * pRight)
{
	m_cVal = cVal;
	m_pLeft = pLeft;
	m_pRight = pRight;
}

CBinTreeNode::~CBinTreeNode()
{
	{
		if(m_pLeft != 0)
		{delete m_pLeft;}
		if(m_pRight != 0)
		{delete m_pRight;}
	}
}

CBinTreeNode * CBinTreeNode::CreatTree(char * sPre, char * sMid, int nSize)
{
	if(nSize == 0)//若长度为零，返回
		return 0;
	if(nSize == 1)//若长度为一，建立结点后，返回
		return new CBinTreeNode(*sPre, NULL, NULL);
	int nMidSplit;//定义一个栅栏，区分中序中的左右子树
	for(nMidSplit = 0; nMidSplit < nSize; ++nMidSplit)
	{
		if(sPre[0] == sMid[nMidSplit])//找到中序中的根节点
			break;
	}
	if(nMidSplit == nSize)
		return 0;
	return new CBinTreeNode(*sPre, CreatTree(sPre+1, sMid, nMidSplit),//递归调用结点 
		CreatTree(sPre+nMidSplit+1, sMid+nMidSplit+1, nSize-nMidSplit-1));//构造函数，建立二叉树
}


void CBinTreeNode::BTInOrder(CBinTreeNode * root, int totalSpaces)
{
	if (NULL != root)
    {
        BTInOrder(root->m_pLeft, (totalSpaces + 40));//递归调用函数输出左子树
		CDialogDlg::DrawText(root->m_cVal,totalSpaces);//在屏幕上打印树的结点
		BTInOrder(root->m_pRight, (totalSpaces + 40));//递归调用函数输出右子树	
    }

}