#include<iostream>

#include <algorithm>

#include <vector>

#include <set>

#include <map>

#include <string>

#include <string.h>

#include<stack>

#include<ctime>

#include <sstream>

#include <queue>

using namespace std;

// 树节点的结构体

struct TreeNode

{

    int val;

    TreeNode *left;

	TreeNode *right;

    TreeNode(int x) : val(x), left(NULL), right(NULL) {}

};

// 函数声明

void preorder (TreeNode * p);

void midorder (TreeNode *p);

void postorder(TreeNode *p);

void preorder_1 (TreeNode *p);

void preorder_2 (TreeNode *p);

void midorder_1(TreeNode* p);

void postorder_1(TreeNode* p);

void levelorder_1(TreeNode*p);

int main()

{

	TreeNode* a=new TreeNode (2);

	TreeNode* b= new TreeNode(3);

	TreeNode* c= new TreeNode(1);

	a->left=b;a->right=c;

	TreeNode* d= new TreeNode(6);

	TreeNode* e= new TreeNode(4);

	b->left=new TreeNode(5);b->right=d;

	d->left=new TreeNode(3);d->right=new TreeNode(0);

	c->right=e;

	e->left=new TreeNode (-1);e->right=new TreeNode(2);

	cout << "递归版: " <<endl;

	preorder(a);

	cout << endl;

	midorder(a);

	cout << endl;

	postorder(a);

	cout << endl;

	cout <<"迭代版: " <<endl;

	cout << "先序遍历1.0:";

	preorder_1(a);

	cout <<endl;

	cout << "先序遍历2.0:";

	preorder_2(a);

	cout <<endl;

	cout << "中序遍历:";

	midorder_1(a);

	cout << endl;

	cout <<"层次遍历:" ;

	levelorder_1(a);

	cout << endl;

	return 0;

}

//%%%%%%%%%%%%%%%%%%%%%%%%%%%  递归版  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%

// 树的前序遍历

void preorder (TreeNode * p)

{

	if(p == NULL) return;

	cout<< p->val << " ";

	preorder(p->left);

	preorder(p->right);

}

//树的中序遍历

void midorder (TreeNode *p)

{

	if(p == NULL) return;

	midorder(p->left);

	cout<< p->val << " ";

	midorder(p->right);

}

// 树的后序遍历

void postorder(TreeNode *p)

{

	if(p == NULL) return;

	postorder(p->left);

	postorder(p->right);

	cout<< p->val << " ";

}

// %%%%%%%%%%%%%%%%%%%%%%%% 迭代版 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

// 前序遍历1.0

void preorder_1 (TreeNode *p)

{

	stack<TreeNode *> s;

	s.push(p);

	while(!s.empty())

	{

		TreeNode* tmp=s.top();

		s.pop();

		cout << tmp->val << " ";

		if(tmp->right != NULL) s.push(tmp->right);

		if(tmp->left != NULL) s.push(tmp->left);

	}

}

// 前序遍历2.0

void visitalongleft(TreeNode* p,stack<TreeNode*> &s)

{

	while(p!=NULL)

	{

		s.push(p);

		cout << p->val << " ";

		p=p->left;

	}

}

void preorder_2 (TreeNode *p)

{

	stack<TreeNode*> s;

	while(true)

	{

		visitalongleft(p,s);

		if(s.empty()==true) break;

		TreeNode* tmp=s.top();

		s.pop();

		p=tmp->right;

	}

}

// 中序遍历迭代版

void leftalong(TreeNode* p,stack<TreeNode*> &s)

{

	while(p!=NULL) {s.push(p);p=p->left;}

}

void midorder_1(TreeNode* p)

{

	stack<TreeNode*> s;

	while(true)

	{

		leftalong(p,s);

		if(s.empty()==true) break;

		cout << s.top()->val << " ";

		p=s.top()->right;

		s.pop();

	}

}

void levelorder_1(TreeNode*p)

{

	queue<TreeNode *> q;

	if(p==NULL) return;

	q.push(p);

	while(!q.empty())

	{

		cout << q.front()->val <<" ";

		if(q.front()->left != NULL) q.push(q.front()->left);

		if(q.front()->right != NULL) q.push(q.front()->right);

		q.pop();

	}

}