#include <iostream>
#include <stack>
#include <queue>
using namespace std;

/* 二叉树结构的定义 */
struct BiTNode
{
    char val;
    struct BiTNode *lchild, *rchild;

    BiTNode() {
        lchild = NULL;
        rchild = NULL;
    }
};

/* 按照前序顺序建立二叉树  */
void createBiTNode(BiTNode *&root)
{
    char c;
    cin >> c;
    if (c != '#')
    {
        root = new BiTNode();
        root->val = c;
        createBiTNode(root->lchild);
        createBiTNode(root->rchild);
    }
}

/* 递归实现前序遍历 */
void preTraverse(BiTNode *root)
{
    if (root)
    {
        cout << root->val << " ";
        preTraverse(root->lchild);
        preTraverse(root->rchild);
    }
}

/*  用非递归实现前序遍历 
每遇到一个结点，先访问该结点，并把该结点的非空右子结点推入栈中，
然后遍历左子树，左子树遍历不下去时，从栈顶弹出待访问的结点，继续遍历。
*/
void preTraverse1(BiTNode *root)
{
    stack<BiTNode*> s;
    if(root)
    {
        s.push(root);
    }

    while (!s.empty())
    {
        root = s.top();
        s.pop();
        cout << root->val << " ";
        if (root->rchild)
            s.push(root->rchild);
        if (root->lchild)
            s.push(root->lchild);
     
    }
}

/* 递归实现中序遍历 */
void midTraverse(BiTNode *root)
{
    if (root)
    {
        midTraverse(root->lchild);
        cout << root->val << " ";
        midTraverse(root->rchild);
    }
}

/* 非递归实现中序遍历 
每遇到一个结点就把它压入栈中，然后去遍历其左子树；
遍历完左子树后，从栈顶弹出并访问这个结点，
然后按照其右链指示的地址再去遍历该结点的右子树。
*/
void midTraverse1(BiTNode *root)
{
    stack<BiTNode*> s;
    while (!s.empty() || root)
    {
        if (root)
        {
            s.push(root);
            root = root->lchild;
        }
        else {
            root = s.top();
            s.pop();
            cout << root->val << " ";
            root = root->rchild;
        }
    }
}

/* 递归实现后序遍历 */
void postTraverse(BiTNode *root)
{
    if (root)
    {
        postTraverse(root->lchild);
        postTraverse(root->rchild);
        cout << root->val << " ";
    }
}

struct Element{
    bool flag;
    BiTNode *root;
};

/* 非递归实现后续遍历
每遇到一个结点，先把它压入栈中，去遍历它的左子树，遍历完左子树后，
应该继续遍历该结点的右子树；
遍历完右子树后，才从栈中弹出该结点并访问它。
由于访问某个结点前不知道是否已经访问该结点的右孩子，
因此需要给栈中的每个元素加一个标志flag，
表示该结点的右子树是否被访问过。
 */
void postTraverse1(BiTNode *root)
{
    stack<Element> s;
    Element element;
    while (!s.empty() || root)
    {
        while (root)
        {
            element.root = root;
            element.flag = false;
            s.push(element);
            root = root->lchild;
        }
        
        element = s.top();
        s.pop();
        root = element.root;

        if (!element.flag)
        {
            element.flag = true;
            root = root->rchild;
            s.push(element);
        }
        else {
            cout << root->val << " ";
            root = NULL;
        }
    }
}

/* 二叉树的层次遍历 
设置一个队列，然后只要队列不为空，
将对首元素的左右孩子加入队列（如果左右孩子不为空），
然后将队列的首元素出队即可
*/
void levelTraverse(BiTNode *root)
{
    queue<BiTNode*> que;
    que.push(root);
    while(!que.empty())
    {
        BiTNode *temp;
        temp = que.front();
        if (temp->lchild != NULL)
            que.push(temp->lchild);
        if (temp->rchild != NULL)
            que.push(temp->rchild);
        cout << temp->val << " ";
        que.pop();
    }
}

int main()
{
    BiTNode *root = NULL;
    cout << "请创建二叉树：" << endl;
    createBiTNode(root);
    cout << "二叉树的前序递归遍历:" << endl;
    preTraverse(root);cout << endl;
    cout << "二叉树的前序非递归遍历:" << endl;
    preTraverse1(root);cout << endl;
    cout << "二叉树的中序递归遍历:" << endl;
    midTraverse(root);cout << endl;
    cout << "二叉树的中序非递归遍历:" << endl;
    midTraverse1(root);cout << endl;
    cout << "二叉树的后序递归遍历:" << endl;
    postTraverse(root);cout << endl;
    cout << "二叉树的后序非递归遍历:" << endl;
    postTraverse1(root);cout << endl;
    cout << "二叉树的层次遍历:" << endl;
    levelTraverse(root);
    return 0;
}