#include<cstdio>
#include<cstdlib>
#include<queue>
#define max_size 10
#define useless_data -1
#define node_child 1
#define node_link 0


const char child[] = "child";
const char pointer[] = "pointer";

typedef struct TreeNode{
    int data;
    TreeNode* left_child;
    bool left_child_property;
    TreeNode* right_child;
    bool right_child_property;
    TreeNode(){
        data = useless_data;
        left_child = 0;
        right_child = 0;
        left_child_property = node_child;
        right_child_property= node_child;
    }

    bool clean(){
        if(this->left_child) {
            if(this->left_child->clean()){
                this->left_child = 0;
            }
        }
        if(this->right_child){
            if(this->right_child->clean()){
                this->right_child = 0;
            }
        }
        if(this->data==useless_data){
            delete this;
            return true;
        }
        return false;
    }

    void destory_all(){
        if(this->left_child&&this->left_child_property==node_child) this->left_child->destory_all();
        if(this->right_child&&this->right_child_property==node_child) this->right_child->destory_all();
        delete this;
    }

    void destory(){
        if(this->left_child&&this->left_child_property==node_child) this->left_child->destory_all();
        if(this->right_child&&this->right_child_property==node_child) this->right_child->destory_all();
    }

    void output_inOrder(){
        if(this->left_child_property==node_child&&this->left_child) this->left_child->output_inOrder();

        printf("%d ",this->data);

        if(this->right_child_property==node_child&&this->right_child) this->right_child->output_inOrder();
    }

    /**
    *将当前结点的left_child(指向prev)和前驱结点的right_child(指向this)线索化，要求传入当前结点的前驱
    *线索化后变为left_link和right_link
    **/
    void visit_and_build_thread(TreeNode*& prev){
        if(this->left_child==0&&this->left_child_property==node_child){
            this->left_child = prev;
            this->left_child_property = node_link;
        }
        if(prev&&prev->right_child==0&&prev->right_child_property==node_child){
            prev->right_child = this;
            prev->right_child_property = node_link;
        }
        //线索化完毕，将前驱移至当前结点的位置
        prev = this;
    }

    /**
    * 用前序遍历将二叉树线索化，需要传入前驱结点
    **/
    void build_thread_preorder(){
        //如果直接传入 (TreeNode*)0, 引用会找不到地址，因此先声明变量
        TreeNode* prev = 0;
        build_thread_preorder(prev);
        //函数执行完毕后，prev会指向遍历的最后一个结点(此时prev->right_child如果为0，需要修改结点类型)
        if(prev->right_child == 0){
            prev->right_child_property = node_link;
        }
    }
    void build_thread_preorder(TreeNode*& prev){

       visit_and_build_thread(prev);

       //如果把前驱结点当成左子树访问会导致死循环
       if(this->left_child&&this->left_child_property==node_child){
            this->left_child->build_thread_preorder(prev);
       }

       if(this->right_child){
            this->right_child->build_thread_preorder(prev);
       }
    }


    /**
    * 用中序遍历将二叉树线索化，需要传入前驱结点
    **/
    void build_thread_inorder(){
        //如果直接传入 (TreeNode*)0, 引用会找不到地址，因此先声明变量
        TreeNode* prev = 0;
        build_thread_inorder(prev);
        //函数执行完毕后，prev会指向遍历的最后一个结点(此时prev->right_child必定为0，需要修改结点类型)
        if(prev->right_child == 0){
            prev->right_child_property = node_link;
        }
    }
    void build_thread_inorder(TreeNode*& prev){
       if(this->left_child){
            this->left_child->build_thread_inorder(prev);
       }

       visit_and_build_thread(prev);

       if(this->right_child){
            this->right_child->build_thread_inorder(prev);
       }
    }


    /**
    * 用后序遍历将二叉树线索化，需要传入前驱结点
    **/
    void build_thread_postorder(){
        //如果直接传入 (TreeNode*)0, 引用会找不到地址，因此先声明变量
        TreeNode* prev = 0;
        build_thread_postorder(prev);
        //函数执行完毕后，prev会指向遍历的最后一个结点(此时prev->right_child如果为0，需要修改结点类型)
        if(prev->right_child == 0){
            prev->right_child_property = node_link;
        }
    }
    void build_thread_postorder(TreeNode*& prev){
       if(this->left_child){
            this->left_child->build_thread_postorder(prev);
       }

       if(this->right_child){
            this->right_child->build_thread_postorder(prev);
       }

       visit_and_build_thread(prev);
    }

    void output_node(int level){
        printf( "address:(0x%x) with data:%d ,at level:%d; left_%s = 0x%x , right_%s = 0x%x;\n",
               (int)this,this->data,level,
               (this->left_child_property==node_child?child:pointer),(int)this->left_child,
               (this->right_child_property==node_child?child:pointer),(int)this->right_child );
    }

    void output_inOrder_detailed(int level = 1){
        if(this