#include<iostream>
#include<queue>
#include<stack>
#include < iomanip >
using namespace std;
typedef struct tree {

	char value;//结点值
	tree* lchild;//左子树指针
	tree* rchild;//右子树指针
};
void creat_tree(tree*& T)//创建二叉树
{
	char ch;
	cin>>ch;//从键盘输入一串字母,依次读取,直至换行键
	if (ch == '#')//注意：叶子节点的左子树和右子树要赋值为‘#’
		T = NULL;
	
	else {
		T = new tree;
		T->value = ch;
		creat_tree(T->lchild);
		creat_tree(T->rchild);
	}
	
}
void VLR(tree* T)//先序遍历二叉树
{
	if (T == NULL)
		return;
	else {
		cout << T->value<<'\t';
		VLR(T->lchild);
		VLR(T->rchild);
	}
}
void LVR(tree* T)//中序遍历二叉树
{
	if (T == NULL)
		return;
	else {
		LVR(T->lchild);
		cout << T->value<<'\t';
		LVR(T->rchild);
	}

}
void LRV(tree* T)	//后序遍历二叉树
{
	if (T == NULL)
		return;
	else {
		LRV(T->lchild);
		LRV(T->rchild);
		cout << T->value<<'\t';
	}

}
int caclnum(tree* T)//计算结点个数
{
	if (T == NULL)
		return 0;
	else
	{
		return 1 + caclnum(T->lchild) + caclnum(T->rchild);//计算二叉树结点个数
	}

}
void LevelOrder(tree* T)//层序遍历
{
	if (T == NULL)
		return;
	queue<tree*> s;//建立一个队列容器

	s.push(T);
	while (!s.empty())
	{
		tree* tr = s.front();
		cout << tr->value << '\t';
		s.pop();
		if (tr->lchild != NULL)//每处理一个结点，就将其左右孩子入栈
			s.push(tr->lchild);

		if (tr->rchild != NULL)
			s.push(tr->rchild);
	}
}
//中序遍历的非递归算法
void InOrderWithoutRecursion1(tree* T)
{
	//空树
	if (T == NULL)
		return;
	//树非空
	tree* p = T;
	stack<tree*> s;
	while (!s.empty() || p)
	{
		//一直遍历到左子树最下边，边遍历边保存根节点到栈中
		while (p)
		{
			s.push(p);
			p = p->lchild;
		}
		//当p为空时，说明已经到达左子树最下边，这时需要出栈了
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			cout << setw(4) << p->value;
			//进入右子树，开始新的一轮左子树遍历(这是递归的自我实现)
			p = p->rchild;
		}
	}
	cout << endl;
}

//先序遍历非递归算法
void PreOrderWithoutRecursion1(tree* T)
{
	if (T == NULL)
		return;
	tree* p = T;
	stack<tree*> s;
	while (!s.empty() || p)
	{
		//边遍历边打印，并存入栈中，以后需要借助这些根节点进入右子树
		while (p)
		{
			cout << setw(4) << p->value;
			s.push(p);
			p = p->lchild;
		}
		//当p为空时，说明根和左子树都遍历完了，该进入右子树了
		if (!s.empty())
		{
			p = s.top();
			s.pop();
			p = p->rchild;
		}
	}
	cout << endl;
}

//定义枚举类型：Tag
enum Tag { left, right };
//自定义新的类型，把二叉树节点和标记封装在一起
typedef struct TagNode
{
	tree* node;
	Tag tag;
};
//后序遍历非递归算法  
void PostOrderWithoutRecursion2(tree* T)
{
	if (T == NULL)
		return;
	stack<TagNode> s;
	TagNode tagnode;
	tree* p = T;
	while (!s.empty() || p)
	{
		while (p)
		{
			tagnode.node = p;
			//该节点的左子树被访问过
			tagnode.tag = Tag::left;
			s.push(tagnode);
			p = p->lchild;
		}
		tagnode = s.top();
		s.pop();
		//左子树被访问过，则还需进入右子树
		if (tagnode.tag == Tag::left)
		{
			//置换标记
			tagnode.tag = Tag::right;
			//再次入栈
			s.push(tagnode);
			p = tagnode.node;
			//进入右子树
			p = p->rchild;
		}
		else//右子树已被访问过，则可访问当前节点
		{
			cout << setw(4) << (tagnode.node)->value;
			//置空，再次出栈(这一步是理解的难点)
			p = NULL;
		}
	}
	cout << endl;
}
int main() {

	tree* T;
	creat_tree(T);
	VLR(T);//前序遍历
	cout << endl;
	LVR(T);//中序遍历
	cout << endl;
	LRV(T);//后序遍历
	cout << endl;
	cout << caclnum(T)<<endl;//统计结点个数
	LevelOrder(T);//层序遍历
	cout << endl;
	PreOrderWithoutRecursion1(T);
	InOrderWithoutRecursion1(T);
	PostOrderWithoutRecursion2(T);
	return 0;
}