[数据结构与算法]数据结构-前中后序遍历的递归与非递归算法，层次遍历算法

#include<iostream>
#include<stack>
#include<deque>
using namespace std;
typedef struct BinTree//二叉树的结构体
{
	int data;
	BinTree* Lch;//左孩子 Left Child
	BinTree* Rch;//右孩子 Right Child
	BinTree(int initData=0)// 定义构造函数，方便初始化
	{
		Lch=NULL;
		Rch=NULL;
		data=initData;
	}
}BinTree;
/*     << PreOrderTrav_Stack >>
先序遍历实现思想：<栈实现>
1.父节点入栈
2.父节点出栈后，右左结点依次入栈
*/
void PreOrderTrav_Stack(BinTree *root)//先序遍历的栈实现(非递归实现)
{
	if(root==NULL)
	{
		cout<<"二叉树为空，程序直接返回\n";
		return;
	}
	stack<BinTree*> stk;//老师说了现在可以使用标准模板库的栈和队列了
	stk.push(root);//根结点入栈
	while(!stk.empty())
	{
		BinTree* bt=stk.top();
		stk.pop();//父节点出栈
		cout<<bt->data<<",";
		if(bt->Rch)//右节点入栈
			stk.push(bt->Rch);
		if(bt->Lch)//左节点入栈
			stk.push(bt->Lch);
	}
}
void PreOrderTrav_Recur(BinTree *root)//先序遍历的递归实现
{
	if(root!=NULL)//递归顺序为rLR
	{
		cout<<root->data<<",";
		PreOrderTrav_Recur(root->Lch);
		PreOrderTrav_Recur(root->Rch);
	}
}
/*        <<  InOrderTrav_Stack 算法实现思想  >> < 栈实现 >
用whlie和t指针双重判断的原因是，可能出现左树和根结点全被弹出的情况，但右子树还没开始输出，而head指向右节点
1.利用头结点t，如果t非空，就把t节点压栈，t指向左节点
2.如果t空了，说明栈顶结点是没有左节点的，我们就把栈顶元素弹出，然后指向栈顶元素的右节点
*/
void InOrderTrav_Stack(BinTree *root)//中序遍历的非递归算法
{
	if(root==NULL)
	{
		cout<<"二叉树为空，程序直接返回\n";
		return;
	}
	stack<BinTree*> stk;
	BinTree* t=root;
	while(!stk.empty()||t!=NULL)
	{
		if(t!=NULL)//如果t不为空，就将t入栈，t指向t的左节点
		{
			stk.push(t);
			t=t->Lch;
		}
		else//如果t为空，说明当前结点没有左结点，那就弹出当前结点并将t调整到当前结点的右节点
		{
			t=stk.top();
			stk.pop();//弹出结点
			cout<<t->data<<",";
			t=t->Rch;//指向右节点
		}
	}
}
void InOrderTrav_Recur(BinTree *root)//中序遍历的递归实现
{
	if(root!=NULL)//递归顺序为 LrR
	{
		InOrderTrav_Recur(root->Lch);
		cout<<root->data<<",";
		InOrderTrav_Recur(root->Rch);
	}
}
/*        <<  PostOrderTrav_Stack 算法实现思想  >>
1.可由最好实现的先序遍历rLR逆序实现
2.我们修改“先序遍历”为rRL,然后逆序输出 就是LRr 通过先序遍历的代码略微修改就能实现后序遍历
3.只需要多加个栈来存储内容即可
*/
void PostOrderTrav_Stack(BinTree *root)//后序遍历的非递归实现
{
	if(root==NULL)
	{
		cout<<"二叉树为空，程序直接返回\n";
		return;
	}
	stack<BinTree*> stk;
	stack<int> stk_data;//存储数据，等待后面的逆序输出
	stk.push(root);
	while(!stk.empty())//按照 rRL的顺序入栈
	{
		BinTree *bt=stk.top();
		stk.pop();
		stk_data.push(bt->data);
		if(bt->Lch)
			stk.push(bt->Lch);
		if(bt->Rch)
			stk.push(bt->Rch);
	}
	while(!stk_data.empty())//逆序输出数据栈中的数据，实现rRL转LRr
	{
		int temp=stk_data.top();
		cout<<temp<<",";
		stk_data.pop();
	}
}
void PostOrderTrav_Recur(BinTree *root)//后续遍历的递归实现
{
	if(root!=NULL)//递归顺序 LRr
	{
		PostOrderTrav_Recur(root->Lch);
		PostOrderTrav_Recur(root->Rch);
		cout<<root->data<<",";
	}
}
/*   << LevelOrderTrav >>
层次遍历思想:
1.队列实现，父节点进队
2.父节点出队后两个左右结点依次入队
*/
void LevelOrderTrav(BinTree *root)//层次遍历
{
	deque<BinTree*> dq;
	dq.push_back(root);//根结点入队
	while(!dq.empty())
	{
		BinTree *temp=dq.front();
		dq.pop_front();//出队
		cout<<temp->data<<",";
		if(temp->Lch)//左结点入队
			dq.push_back(temp->Lch);
		if(temp->Rch)//右结点入队
			dq.push_back(temp->Rch);
	}
}
BinTree *BTArray[13];// 0号索引位弃用 设置为全局变量
void BinTreeGenerate(BinTree *root)//按照题目要求生成二叉树
{
	BTArray[1]=root;
	for(int i=2;i<=12;i++)
	{
		BTArray[i]=new BinTree(i);//在堆区动态开辟空间
	}
	BTArray[1]->Lch=BTArray[2];BTArray[1]->Rch=BTArray[3];
	BTArray[2]->Lch=BTArray[4];BTArray[2]->Rch=BTArray[5];
	BTArray[4]->Lch=BTArray[7];BTArray[4]->Rch=BTArray[6];
	BTArray[5]->Lch=BTArray[8];BTArray[5]->Rch=BTArray[10];
	BTArray[3]->Rch=BTArray[9];
	BTArray[9]->Lch=BTArray[11];BTArray[9]->Rch=BTArray[12];
}
void DelTree()//释放开辟的空间
{
	for(int i=2;i<=12;i++)
	{
		delete BTArray[i];
	}
}
int main()
{
	BinTree *root=new BinTree;
	root->data=1;
	BinTreeGenerate(root);
	cout<<"---------------PreOrder-------------------\n";
	cout<<"非递归方式实现先序遍历:\n";
	PreOrderTrav_Stack(root);//非递归方式实现先序遍历
	cout<<endl;
	cout<<"递归方式实现先序遍历:\n";
	PreOrderTrav_Recur(root);//递归方式实现先序遍历
	cout<<endl;
	cout<<"---------------InOrder--------------------\n";
	cout<<"非递归方式实现中序遍历:\n";
	InOrderTrav_Stack(root);//非递归方式实现中序遍历
	cout<<endl;
	cout<<"递归方式实现中序遍历:\n";
	InOrderTrav_Recur(root);//递归方式实现中序遍历
	cout<<endl;
	cout<<"---------------PostOrder------------------\n";
	cout<<"非递归方式实现后序遍历:\n";
	PostOrderTrav_Stack(root);//非递归方式实现后序遍历
	cout<<endl;
	cout<<"递归方式实现后序遍历:\n";
	PostOrderTrav_Recur(root);//递归方式实现后序遍历
	cout<<endl;
	cout<<"---------------LevelOrder-----------------\n";
	cout<<"实现层次遍历:\n";
	LevelOrderTrav(root);//非递归方式实现后序遍历
	cout<<endl;
	cout<<"-----------------------------------------\n";
	delete root;//释放根结点空间
	DelTree();//释放其他节点空间
	return 0;
}