#include<iostream>
#include<iomanip>
#include<string>
#include<fstream>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<array>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef struct treenode {
    char data;
    struct treenode* left;
    struct treenode* right;
}treenode,*treepoint;
treepoint println()
{
    char S;
    cin >> S;
    if (S != '#')
    {
        treepoint head = new treenode{ '#',nullptr,nullptr };
        head->data = S;
        head->left=println();
        head->right=println();
        return head;
    }
    else
    {
        return nullptr;
    }
}
void firstScan(treepoint head)
{
    if (head != nullptr)
    {
        cout <<setw(3)<< head->data;
        firstScan(head->left);
        firstScan(head->right);
    }
}
void secondScan(treepoint head)
{
    if (head != nullptr)
    {
        secondScan(head->left);
        cout << setw(3) << head->data;
        secondScan(head->right);
    }
}
void thirdScan(treepoint head)
{
    if (head != nullptr)
    {
        thirdScan(head->left);
        thirdScan(head->right);
        cout << setw(3) << head->data;
    }
}
void forthScan(treepoint treehead)
{
    queue<treepoint> newqueue;
    newqueue.push(treehead);
    while (!newqueue.empty())
    {
        treepoint newhead = newqueue.front();
        cout << setw(3) << newhead->data;
        newqueue.pop();
        if (newhead->left != nullptr)
        {
            newqueue.push(newhead->left);
        }
        if (newhead->right != nullptr)
        {
            newqueue.push(newhead->right);
        }
    }
}
/*--------------------------下面是 非递归算法--------------------------------*/
void firstScanNO(treepoint head)
{
    stack<treepoint> newstack;
    treepoint p = head;
    while (p != nullptr || !newstack.empty())
    {
        while (p != nullptr)
        {
            newstack.push(p);
            cout << setw(3) << p->data;
            p = p->left;
        }
        if (!newstack.empty())
        {
            p = newstack.top();
            newstack.pop();
            p = p->right;
        }
    }
}
void secondScanNo(treepoint head)
{
    treepoint p = head;
    stack<treepoint> newstack;
    while (!newstack.empty() || p != nullptr)
    {
        while (p!= nullptr)
        {
            newstack.push(p);
            p = p->left;
        }
        if (!newstack.empty())
        {
            p = newstack.top();
            newstack.pop();
            cout << setw(3) << p->data;
            p = p->right;
        }
    }
}
typedef struct treenodeplus
{
    treepoint p;
    bool VisitedFlag = false;
}treenodeplus,*treepointplus;
void thirdScanNo(treepoint head)
{
    treepoint p = head;
    stack<treepointplus> newstack;
    while (p != nullptr || !newstack.empty())
    {
        while (p != nullptr)
        {
            treepointplus newplus = new treenodeplus{ p };
            newstack.push(newplus);
            p = p->left;
        }
        if (!newstack.empty())
        {
            treepointplus plus = newstack.top();
            newstack.pop();
            if (plus->VisitedFlag == false)
            {
                plus->VisitedFlag = true; 
                newstack.push(plus); //再把plus 塞回去
                p = plus->p->right;
            }
            else
            {
                p = plus->p;
                cout <<setw(3)<<p->data;
                p = nullptr;
            }
        }
    }
}
//上面借助辅助空间的方式浪费了大量的存储空间 并且还要考虑元素的后续释放
//当然元素释放爷没写
//下面这种是我新学会的写法

void thirdScanNo2(treepoint head)
{
    treepoint p = head;
    stack<treepoint> newstack;
    treepoint pre=nullptr;
    while (p != nullptr || !newstack.empty())
    {
        while (p != nullptr)
        {
            newstack.push(p);
            p = p->left;
        }
        if (!newstack.empty())
        {
            p = newstack.top();
            if (p->right && p->right != pre)
            {
                p = p->right;
            }
            else
            {
                newstack.pop();
                cout << setw(3) << p->data;
                pre = p;
                p = nullptr;
            }
        }
    }
}

int main()
{
    treepoint newhead1;
    newhead1 = println();
    firstScan(newhead1);
    cout << endl;
    secondScan(newhead1);
    cout << endl;
    thirdScan(newhead1);
    cout << endl;
    forthScan(newhead1);
    cout << endl;
    firstScanNO(newhead1);
    cout << endl;
    secondScanNo(newhead1);
    cout << endl;
    thirdScanNo(newhead1);
    cout << endl;
    thirdScanNo2(newhead1);
    cout << endl;
    /*
   所用二叉树为
                                       A
                           B                      C
                     #         D          E          F
                            G    H    I      J    #  #
                         # #  # # # #  K  L
                                           ## ##
                                        */
    //输入内容为 AB#DG##H##CEI##JK##L##F##
    //前序为ABDGHCEIJKLF
    //中序为BGHDAIEKJLCF
    //后序为GHDBIKLJEFCA
    //层序为ABCDEFGHIJKL
}

#include<iostream>
#include<iomanip>
#include<string>
#include<fstream>
#include<cmath>
#include<vector>
#include<stack>
#include<cstdio>
#include<array>
#include<vector>
#include<map>
#include<queue>
using namespace std;
typedef struct treenode {
    char data;
    struct treenode* left;
    struct treenode* right;
    bool rtag=false;
    bool ltag=false; //默认指向自己的左右孩子 如果被设置为1 才表示后继
}treenode,*treepoint;
typedef struct treenodePlus {
    char data;
    struct treenodePlus* left;
    struct treenodePlus* right;
    struct treenodePlus* parent;
    bool ltag = false;
    bool rtag = false; //默认指向自己的左右孩子 如果被设置为1 才表示后继
}treenodePlus,*treepointPlus;

//我争取能在两个小时内把这个东西写出来
treepoint Create_tree()
{
    treepoint newpoint;
    char data;
    cin >> data;
    if (data == '#')
    {
        return nullptr;
    }
    else
    {
        newpoint = new treenode{ data,NULL,NULL,0,0 };
        newpoint->left = Create_tree();
        newpoint->right = Create_tree();
    }
    return newpoint;
}
void diguiScan(treepoint head)
{
    if (head)
    {
        cout <<setw(3)<<head->data;
        diguiScan(head->left);
        diguiScan(head->right);
    }
}
void Create_first_core(treepoint head,treepoint& pre)
{
    if (head != nullptr)
    {
        if (head->left == nullptr) //如果这个节点左孩子为空
        {
            head->left = pre;
            head->ltag = 1;
        }
        if (pre && pre->right == nullptr)
        {
            pre->right = head;
            pre->rtag = 1;
        }
        pre = head;
        if (head->ltag == 0)
        {
            Create_first_core(head->left, pre);
        }
        if (head->rtag == 0)
        {
            Create_first_core(head->right, pre); //调用到这里的pre 已经和原来的pre不是一个内容了
        }
    }

}
treepoint Create_first_threadtree(treepoint head)
{
    treepoint newhead = new treenode{ '#',nullptr,nullptr,0,1 };
    if (head == nullptr)
    {
        newhead->left = newhead;
        newhead->right = newhead;
        return newhead;
    }
    else
    {
        newhead->left = head;
        treepoint pre = newhead;
        Create_first_core(head, pre);
        pre->right = newhead;
        pre->rtag = 1;
        newhead->right = pre;
        return newhead;
    }
}
void first_thread_treeScan(treepoint head)
{
    treepoint p = head->left;
    while (p != head)
    {
        if (p)
        {
            cout << setw(3) << p->data;
            if (p->ltag == 0)
            {
                p = p->left;
            }
            else
            {
                p = p->right;
            }
        }
    }
}

void Create_second_core(treepoint head, treepoint& pre)
{
    if (head)
    {
        Create_second_core(head->left, pre);
        if (head->left == nullptr)
        {
            head->left = pre;
            head->ltag = 1;
        }
        if (pre&& pre->right== nullptr)
        {
            pre->right = head;
            pre->rtag = 1;
        }
        pre = head;
        Create_second_core(head->right, pre);
    }
}
treepoint Create_second_threadtree(treepoint head)
{
    treepoint newhead = new treenode{ '#',nullptr,nullptr,0,1 };
    if (head == nullptr)
    {
        newhead->left = newhead;
        newhead->right = newhead;
        return newhead;
    }
    else
    {
        newhead->left = head;
        treepoint pre = head;
        Create_second_core(head, pre);
        pre->right = newhead;
        pre->rtag = 1;
        newhead->right = pre;
        return newhead;
    }
}
void second_thread_treeScan(treepoint head)
{
    treepoint p = head->left;
    while (p != head)
    {
        while (p->ltag == 0)
        {
            p = p->left;
        }//直到p到最左侧
        cout <<setw(3)<<p->data;
        //输出这个值  
        //注意这里是while 不是if hxd
        while (p->rtag == 1 && p->right != head)
        {
            p = p->right;
            cout << setw(3) << p->data;
        }
        p = p->right;
    }
}

treepointPlus Create_PlusTree(treepointPlus pointparent)
{
    treepointPlus newhead;
    char data;
    cin >> data;
    if (data == '#')
    {
        return nullptr;
    }
    else
    {
        newhead = new treenodePlus{ data,nullptr,nullptr,nullptr,0,0 };
        newhead->parent = pointparent; //用来标记 父节点 妙啊妙啊
        newhead->left = Create_PlusTree(newhead);
        newhead->right = Create_PlusTree(newhead);
    }
    return newhead;
} //生成特殊类型二叉树
void Create_third_core(treepointPlus head, treepointPlus& pre)
{
    if (head)
    {
        Create_third_core(head->left, pre);
        Create_third_core(head->right, pre);
        if (head->left == nullptr)
        {
            head->left = pre;
            head->ltag = 1;
        }
        if (pre&&pre->right == nullptr)
        {
            pre->right = head;
            pre->rtag = 1;
        }
        pre = head;
    }
}
treepointPlus Create_third_threadtree(treepointPlus head)
{
    treepointPlus newhead = new treenodePlus{ '#',nullptr,nullptr,nullptr,0,1 };
    if (head == nullptr)
    {
        newhead->left = newhead->right = newhead;
        return newhead;
    }
    else
    {
        newhead->left = head;
        newhead->right = head;
        head->parent = newhead;
        treepointPlus pre = newhead;
        Create_third_core(head, pre);
        //这个指的是如果根节点没有右子树 因为最后一个pre必然是根节点
        //如果根节点有右子树 下面的步骤不会执行
        if (pre->right == nullptr)
        {
            pre->right = newhead;
            pre->rtag = 1;
        }
        return newhead;
    }
}
void third_thread_treeScan(treepointPlus head)
{
    treepointPlus p = head->left;
    treepointPlus pmemory = p;
    treepointPlus pre = nullptr;
    while (p != head)
    {
        while (p->ltag == 0 && p->left != pre) //防止再次进入左子树
        {
            p = p->left;
        }//直接到最左侧节点

        while (p->rtag == 1&&p!=head)//这个东西没有右子树 那我们直接访问它 并且访问它的后继
        {//防止一路访问到根节点的父节点（标志节点） 如果访问到我们就推出即可
            cout << setw(3) << p->data;
            pre = p;
            p = p->right;
        }
        //直到某一个节点 有右子树 （这是必然的 表示这个节点的整个右子树已经访问完毕 否则不会弹回到父节点）
        while (p->right == pre && p != head)  //表示这个非叶子节点不是根节点 此处输出
        {
            cout << setw(3) << p->data;
            pre = p;
            p = p->parent;
        }
        if (p->rtag == 0) //每次转到更高一级的根节点 pre的作用已经消失 不必修改pre的值
        {
            p = p->right;
        }
    }
}
int main()
{
    treepointPlus tree =Create_PlusTree(nullptr);
    //treepoint newtreefirst = Create_first_threadtree(tree);
    //first_thread_treeScan(newtreefirst);
    //treepoint newtreesecond = Create_second_threadtree(tree);
    //second_thread_treeScan(newtreesecond);
    treepointPlus newtreesecond = Create_third_threadtree(tree);
    third_thread_treeScan(newtreesecond);
    /*AB#DG##H###
   所用二叉树为
                                       A
                           B                      C
                     #         D          E          F
                            G    H    I      J    #  #
                         # #  # # # #  K  L
                                           ## ##
                                        */
    //输入内容为 AB#DG##H##CEI##JK##L##F##
    //前序为ABDGHCEIJKLF
    //中序为BGHDAIEKJLCF
    //后序为GHDBIKLJEFCA
    //层序为ABCDEFGHIJKL

    //ABCD###E#F#G##H#IO###
    //后续  D  C  G  F  E  B  O  I  H  A

    //AB#DG##H###
    // G  H  D  B  A
    //A#B#CD##E#F##
    //D  F  E  C  B  A


    /*
    
    */
}