stdafx.cpp

里面装有 5 个小程序

/*
  实验题目：二叉的遍历
  开发思想：本实验分别用了递归和非递归来实现前序、中序、后序
			方式的遍历二叉树，还实现了层次遍历，并求出树高。
			在这些实现中，主要用到的是队列链和链栈。
  开发人员：葛兴高
  开发日期：2004、10、29
*/

#include "stdafx.h"
#include <iostream.h>

//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//二叉树的实现
//-------------------------------------------

//初始化二叉树为空
BuildTree::BuildTree()
{
	head=new TreeNode;
}
//-------------------------------------------
//析构函数
BuildTree::~BuildTree()
{
}
//-------------------------------------------
//建立二叉树
//这里使用一个非递归的前序遍历方法进行建树
void BuildTree::Create()
{
	//定义一个字符数组，存放建树所用的点
	char *ch;
	ch=new char[100];

	int i=0;
	int j=0;
	
	stack S;

	//新定义一个指针，并为其申请空间
	TreeNode *current;
	current=new TreeNode;
	
	do
	{
		cin>>ch[i];
		i++;
	}while(ch[i-1]!=35);

	current->data=ch[j];
	head=current;
	S.Push(head);//首先把头结点入栈
	current=head;//当前指针指向头结点
	
	while(ch[j+1]!='#')
	{
		j++;
		int flag=1;//flag标志，用来恢复向右走的功能
		TreeNode *p=new TreeNode;

		//建立左子树
		if(ch[j]=='.')
		{
			p->data=NULL;
			current->lchild=p;
			current=current->lchild;
		}
		else
		{
			p->data=ch[j];
			current->lchild=p;
			current=current->lchild;
		}
		if(current->data!=NULL)
		{
			S.Push(current);
		}
		else
		{
			//建立右子树
			while(flag==1)
			{
				current=S.Pop();
				TreeNode *q=new TreeNode;
				j++;
				if(ch[j]=='.')
				{
					q->data=NULL;
					current->rchild=q;
					current=current->rchild;
				}
				else
				{
					q->data=ch[j];
					current->rchild=q;
					current=current->rchild;
				}
				if(current->data!=NULL)
				{
					S.Push(current);
					flag=0;//每次向右走一次就必须向左走
				}
				else
				{
					if(ch[j+1]=='#')
						flag=0;
					else
						flag=1;
				}
			}
		}
	}
}
//-------------------------------------------
//从文件中读进树的结点进行建立二叉树
/*void BuildTree::CreateTree(char *file)
{
	Queue q;
	ifstream inFile;
	inFile.open(file);

	TreeNode *current;
	current=new TreeNode;

	//把从文件读入的数存放到各个二叉树的结点，
	//再把各个结点入列，以便可以把后面的数一
	//个一个存入到二叉树中
	inFile>>head->data;
	//inFile.get();
	q.EnQueue(head);//记录第一个结点
	inFile>>head->lchild->data;
	//inFile.get();
	q.EnQueue(head->lchild);//记录结点的左孩子
	inFile>>head->rchild->data;
	inFile.get();
	//q.EnQueue(head->rchild);//记录结点的右孩子
	
	
	//把文件中还没有完全输入的数继续输入
	while(inFile)
	{
		current=q.DelQueue();
		if(current->lchild->data!='#')
		{
			q.EnQueue(current->lchild);
			inFile>>current->lchild->lchild->data;
			inFile>>current->lchild->rchild->data;
			inFile.get();
		}
		else if(current->rchild->data!='#')
		{
			q.EnQueue(current->rchild);
			inFile>>current->rchild->lchild->data;
			inFile>>current->rchild->rchild->data;
			inFile.get();
		}
	}
}*/
//-------------------------------------------
//递归的前序遍历
void BuildTree::PreOrder_1(TreeNode *t,int first,int i)
{
	TreeNode *p;
	p=new TreeNode;

	if(first)
	{
		p=head;
		first=0;
	}
	else 
		p=t;
	if(p->data!= NULL)
	{
		Record[i]=p->data;
		cout<<p->data<<" ";
		i++;
		PreOrder_1(p->lchild,first,i);
		PreOrder_1(p->rchild,first,i);
	}
}
//-------------------------------------------
//非递归的前序遍历
void BuildTree::PreOrder_2(TreeNode *t)
{
	TreeNode *p=new TreeNode;
	stack s;	//引入一个堆栈对象

	int i=0;

	p=head;
	s.Push(p);
	while(!s.IsEmpty())
	{
		p=s.Pop();
		//Record[i]=p->data;
		cout<<p->data<<" ";
		i++;
		if(p->rchild->data!=NULL)
			s.Push(p->rchild);
		if(p->lchild->data!=NULL)
			s.Push(p->lchild);
	}
}
//-------------------------------------------
//递归的中序遍历
void BuildTree::InOrder_1(TreeNode *t,int first,int i)
{
	TreeNode *p=new TreeNode;
	
	if(first)
	{
		p=head;
		first=0;
	}
	else 
		p=t;
	if(p->data!=NULL)
	{
		InOrder_1(p->lchild,first,i);
		//Record[i]=p->data;
		//i++;
		//cout<<endl<<"递归中序遍历："<<endl;
		cout<<p->data<<" ";
	 	
		InOrder_1(p->rchild,first,i);
	}
}
//-------------------------------------------
//非递归的中序遍历
void BuildTree::InOrder_2(TreeNode *t)
{
	TreeNode *p=new TreeNode;
	stack s;
	int i=0;

	p=head;

	while((!s.IsEmpty())||(p->data!=NULL))
	{
		while(p->data!=NULL)
		{
			s.Push(p);
			p=p->lchild;
		}
		if(!s.IsEmpty())
		{
			p=s.Pop();
			//Record[i]=p->data;
			//cout<<endl<<"非递归中序遍历:"<<endl;
			cout<<p->data<<" ";
			//i++;
			p=p->rchild;
		}
	}
}
//-------------------------------------------
//递归的后序遍历
void BuildTree::PostOrder_1(TreeNode *t,int  first,int i)
{
	TreeNode *p;

	if(first)
	{
		p=head;
		first=0;
	}
	else p=t;
	if(p->data!=NULL)
	{
		PostOrder_1(p->lchild,first,i);
		PostOrder_1(p->rchild,first,i);
		//cout<<"递归后序遍历";//Record[i]=p->data;
		cout<<p->data<<" ";
		//i++;
	}
}
//-------------------------------------------
//非递归的后序遍历
void BuildTree::PostOrder_2(TreeNode *t)
{
	TreeNode *p;//定义p为当前指针

	//int i=0;
	int flag;
	stack s1,s2;

	p=head;
	//s1.Push(p);

	while((!s1.IsEmpty())||(p->data!=NULL))
	{
		while(p->data!=NULL)
		{
			s1.Push(p);
			s2.Push1(0);
			p=p->lchild;
		}
		if(!s1.IsEmpty())
		{
			p=s1.Pop();
			flag=s2.Pop1();
			///////////////////
			if(p->rchild->data!=NULL)
			{
				flag=1;
				p=p->rchild;
			}
			///////////////////
			if(flag==0)
				cout<<p->data<<" ";
			else
			{
				s1.Push(p);
				s2.Push1(1);
				p=p->rchild;
			}
		}
	}

}
//-------------------------------------------
//层次遍历
void BuildTree::LayerOrder(void)
{
	TreeNode *p;
	Queue q;

	//int i=0;
	if(head!=NULL)
		q.EnQueue(head);
	while(!q.IsEmpty())
	{
		p=q.DelQueue();
		//Record[i]=p->data ;
		//i++;
		cout<<p->data<<" ";
		if(p->lchild->data!=NULL)
			q.EnQueue(p->lchild);
		if(p->rchild->data!=NULL)
			q.EnQueue(p->rchild);
	}
}
//-------------------------------------------
//求出树的高
int BuildTree::GetHigh(TreeNode *t,int first)
{
	int CurrentHigh,LeftHigh,RightHigh;
	TreeNode  *current;

	if(first==1)
	{
		current=head;
		first=0;
	}
	else 
		current=t;
	if(current->data==NULL)
		CurrentHigh=0;
	else 
	{
		LeftHigh=GetHigh(current->lchild,first);
		RightHigh=GetHigh(current->rchild,first);
		if(LeftHigh>RightHigh)
			CurrentHigh=LeftHigh+1;
		else
			CurrentHigh=RightHigh+1;
	}
	return (CurrentHigh);
}
//---------------------------------------------------------
//---------------------------------------------------------
//---------------------------------------------------------
//---------------------------------------------------------
stack::~stack()
{
}
//---------------------------------------------------------
//入栈
void stack::Push(TreeNode *x)
{
	LinkNode *p;
	p=new LinkNode;

	p->data = x;
	p->next = Top;
	Top=p;
}
//----------------------------------------------------------
//出栈
TreeNode* stack::Pop ()
{
	LinkNode *p;
	p=new LinkNode;

	if(!IsEmpty())
	{
		p=Top;
		Top=Top->next ;
		return p->data;
	}
	else return 0;
}
//----------------------------------------------------------
//判断链栈是否为空
int stack::IsEmpty ()
{
	if (Top==NULL)
		return 1;
	else
		return 0;
}
//----------------------------------------------------------
void stack::Push1(int i)
{
	LinkNode1 *p;
	p=new LinkNode1;

	p->data = i;
	p->next = Top1;
	Top1=p;
}
//----------------------------------------------------------
//出栈
int stack::Pop1 ()
{
	LinkNode1 *p;
	p=new LinkNode1;

	if(!IsEmpty1())
	{
		p=Top1;
		Top1=Top1->next ;
		return p->data;
	}
	else return 0;
}
//----------------------------------------------------------
int stack::IsEmpty1 ()
{
	if (Top1==NULL)
		return 1;
	else
		return 0;
}


//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//队列的实现
//-------------------------------------------
//-------------------------------------------
Queue::~Queue(void)
{
}
//-------------------------------------------
//入列
void Queue::EnQueue(TreeNode *x)
{
	QueNode *p;
	p=new QueNode;

	p->data = x;
	rear->next=p;
	rear=p;
}
//-------------------------------------------
//出列
TreeNode* Queue::DelQueue ()
{
	QueNode *p;
	p=new QueNode;
	if(!IsEmpty())
	{
		p=front->next;
		front->next=p->next;
	}
	if(p==rear)
		rear=front;
	return p->data;
}