bitree.cpp

汉诺塔算法演示程序

#include "StdAfx.h"
#include ".\bitree.h"
#include "CreatTree.h"

namespace{
	const int  = 50;         //定义二叉树节点数最大值为50
	pointer Q[MAXSIZE + 1];
}

CBiTree::CBiTree(void):root(NULL),m_inputTree(_T("Input Tree"))
{
}

CBiTree::~CBiTree(void)
{
}

void CBiTree::initial(CView *pView,CDC* pDC){
	//创建二叉树
	CCreatTree inputTree;
	inputTree.m_tree = m_inputTree;
	INT_PTR result = inputTree.DoModal();
	if(result = IDOK){
		m_inputTree = inputTree.m_tree;
	}

}
//.........................................二叉树.....................................................//
/////////////////////////////////////////////////////////


//程序暂停，单位为 秒

void CBiTree::pause(float ftime){
	time_t start,end;
	time(&start);
	do{
		time(&end);
	}while((end-start)<ftime);
}
////
//先根遍历
//入口包括 二叉树根结点指针， 窗口描述表指针， 根结点内容显示位置，和结点在二叉树中的层数
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, " %c ", 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, " %c ", 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, "%c", 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);		//程序延迟，以便观察效果

	}
}

//创建二叉树
bitree level_creat(CString ss)  //按层次序列建立二叉树，返回根指针
{
	int i=0,j=0;
	int front,rear;
	pointer s;

	root=NULL;                //置空二叉树
	front=rear=0;		//置空队列
	if(ss.GetLength()==0){		//若输入字符为空，则弹出对话框加以提示
		Wrong abcd;
		abcd.DoModal();
	}
	else{
		while(ss[i]!='*')			//输入字符，若不是结束符则循环
		{
			if((ss[i]>='A'&&ss[i]<='Z')||ss[i]=='@')   //若是合法字符，则继续
			{

				if(ss[i]>='A'&&ss[i]<='Z'){			//非虚节点，建立新节点
					s=new node;
					s->data=ss[i];
					s->lch=s->rch=NULL;
				}
				else if(ss[i]=='@') s=NULL;
			}
			else                 //非法字符，则弹出对话框加以提示，且结束循环
			{
				Again abc;
				abc.DoModal();
				break;
			}
			rear++;Q[rear]=s;		//不管节点是否为虚，均要入队

			if(rear==1){root=s;front=1;}	//第一个点是根，需修改头指针
			else if(s&&Q[rear/2])			//孩子和双亲都不是虚节点
			{ front=rear/2;					//两次循环后，修改头指针
			if(rear%2==0) Q[front]->lch=s;		//rear是偶数，新节点是左孩子
			else
				Q[front]->rch=s;}				//rear是奇数，新节点是右孩子
			i++;		//继续下一个循环


		}
	}
	return root;
}

//生成层次遍历的二叉树
void CBlieveView::OnNew() 
{
	// TODO: Add your command handler code here
	Blieve_String Build;		//弹出对话框，提示输入字符
	Build.DoModal();
	level_creat(Build.m_str);	//调用level_creat创建二叉树

}
//在屏幕上画出中根遍历的二叉树
void CBlieveView::OnInorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();	//函数入口

	Invalidate(TRUE);			//刷新屏幕

	InOrder(root, pdc, 500,50,1);		//调用InOrder，中根遍历二叉树
}
//屏幕上画出后根遍历的二叉树
void CBlieveView::OnPostorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();		//函数入口

	Invalidate(TRUE);

	PostOrder(root,pdc, 500,50,1);	//调用PostOrder，中根遍历二叉树
}
//屏幕上画出先根遍历的二叉树
void CBlieveView::OnPreorder() 
{
	// TODO: Add your command handler code here
	CDC *pdc = GetDC();		//函数入口
	Invalidate(TRUE);		//刷新屏幕

	PreOrder(root,pdc, 500,50,1);  //调用PreOrder，先根遍历二叉树
}
//调用level_creat重新创建二叉树，再调用PreOrder将其用先根遍历的方式再屏幕中打印出来
void CBlieveView::OnInit()	
{
	// TODO: Add your command handler code here
	Blieve_String Build;		//弹出对话框，提示输入字符	
	Build.DoModal();
	level_creat(Build.m_str);		//调用level_creat创建二叉树
	CDC *pdc = GetDC();			//函数入口

	Invalidate(TRUE);		//刷新屏幕

	PreOrder(root,pdc, 500,50,1);		 //调用PreOrder，先根遍历二叉树
}