/*
  實(shí)驗(yàn)題目：二叉的遍歷
  開發(fā)思想：本實(shí)驗(yàn)分別用了遞歸和非遞歸來實(shí)現(xiàn)前序、中序、后序
			方式的遍歷二叉樹，還實(shí)現(xiàn)了層次遍歷，并求出樹高。
			在這些實(shí)現(xiàn)中，主要用到的是隊(duì)列鏈和鏈棧。
  開發(fā)人員：葛興高
  開發(fā)日期：2004、10、29
*/

#if !defined(AFX_STDAFX_H__7F1144C4_7286_4B6F_9810_21C0C06D6551__INCLUDED_)
#define AFX_STDAFX_H__7F1144C4_7286_4B6F_9810_21C0C06D6551__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000
#include <fstream.h>
#include <stdio.h>
#include <conio.h>

//-------------------------------------------
//-------------------------------------------
//定義樹結(jié)點(diǎn)的類型
typedef	char DataType;

//樹結(jié)點(diǎn)
struct TreeNode
{
	DataType data;
	TreeNode *lchild;
	TreeNode *rchild;
};

//樹類
class BuildTree
{
public:

	//構(gòu)造函數(shù)，初始化鏈表
	BuildTree();
	
	//析構(gòu)函數(shù)
	~BuildTree(void);
	
	//建立一棵二叉樹
	//初始化樹為空
	void Create();
	
	//前序遍歷,用遞歸算法
	//結(jié)果：輸出前序遍歷的結(jié)果
	void PreOrder_1(TreeNode *t,int first,int i);
	
	//前序遍歷，用非遞歸算法
	//結(jié)果：輸出前序遍歷的結(jié)果
	void PreOrder_2(TreeNode *t);

	//中序遍歷，用遞歸算法
	//結(jié)果：輸出中序遍歷的結(jié)果
	void InOrder_1(TreeNode *t,int first,int i);

	//中序遍歷，用非遞歸算法
	//結(jié)果：輸出中序遍歷的結(jié)果
	void InOrder_2(TreeNode *t);

	//后序遍歷，用遞歸算法
	//結(jié)果：輸出后序遍歷的結(jié)果
	void PostOrder_1(TreeNode *t,int first,int i);

	//后序遍歷，用非遞歸算法
	//結(jié)果：輸出后序遍歷的結(jié)果
	void PostOrder_2(TreeNode *t);

	//層次遍歷
	//結(jié)果：輸出層次遍歷的結(jié)果
	void LayerOrder(void);

	//求樹的高
	//返回樹的高
	int GetHigh(TreeNode *t,int first);

	//一個(gè)用來保存遍歷結(jié)果的數(shù)組
	char Record[100];

public:
	
	//定義一個(gè)根結(jié)點(diǎn),也就是鏈?zhǔn)酱鎯Φ逆滎^
	TreeNode *head;

};
//-------------------------------------------
//-------------------------------------------
//-------------------------------------------
//鏈隊(duì)的結(jié)點(diǎn)
struct  QueNode
{
	TreeNode*  data;//定義成指針類型的數(shù)據(jù)
	QueNode *next;
};

//鏈隊(duì)的類
class Queue
{
public:
	QueNode *front;
	QueNode *rear;

public:
	
	//結(jié)構(gòu)函數(shù)
	//初始化鏈隊(duì)，并為鏈?zhǔn)疥?duì)列的鏈頭分配空間
	Queue( )
	{
	 	QueNode * temp;
		temp=new QueNode;
		front=rear=temp;
	}
	
	//析構(gòu)函數(shù)
	~Queue(void);

	//入列
	//結(jié)果：把當(dāng)前指針入列
	void EnQueue(TreeNode* x);

	//出列
	//結(jié)果：返回一個(gè)指針型數(shù)據(jù)
	TreeNode* DelQueue();

	//判斷隊(duì)列是否為空
	int IsEmpty()
	{
		if(front == rear)
			return 1;
		else return 0;
	}
};

//-------------------------------------------
//-------------------------------------------
//棧類
struct LinkNode1
{
	int data;
	LinkNode1 *next;
};

struct  LinkNode	//鏈棧結(jié)點(diǎn)
{
	TreeNode* data;//存放指針
	LinkNode *next;
};

//定義一個(gè)堆棧，用來遍歷搜索的過程
class stack
{
public:

	//構(gòu)造函數(shù)，并初始化
	stack()
	{
		Top=NULL;
	}

	//析構(gòu)函數(shù)
	~stack();

	//入棧
	TreeNode* Pop();
	int Pop1();

	//出棧
	void Push(TreeNode *x);
	void Push1(int i);

	//判空
	int IsEmpty();
	int IsEmpty1();


private:
	//棧頂指針
	LinkNode *Top;
	LinkNode1 *Top1;
};


#endif // !defined(AFX_STDAFX_H__7F1144C4_7286_4B6F_9810_21C0C06D6551__INCLUDED_)