/*
  實驗題目：二叉的遍歷
  開發思想：本實驗分別用了遞歸和非遞歸來實現前序、中序、后序
			方式的遍歷二叉樹，還實現了層次遍歷，并求出樹高。
			在這些實現中，主要用到的是隊列鏈和鏈棧。
  開發人員：葛興高
  開發日期：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;
}