#include <stdio.h>
#include <stdlib.h>
#include <stack>
#include <queue>
using namespace std;
/*節(jié)點定義*/
typedef struct BTNode{
    int tag;
    int data;
    struct BTNode *rchild;
    struct BTNode *lchild;
}BiTNode;
/*創(chuàng)建二叉樹*/
int CreatBiTree(BiTNode **T)
{
    int ch;
    scanf("%d",&ch);
    if(ch==-1){
        *T=NULL;
        return 0;
    }
    else{
        *T= new BiTNode;
        if(T==NULL){printf("分配內(nèi)存失敗");return 0;}
        (*T)->data=ch;
        (*T)->tag=1;
        printf("輸入左結(jié)點");
        CreatBiTree(&((*T)->lchild));
        printf("輸入有右結(jié)點");
        CreatBiTree(&((*T)->rchild));
    }
    return 1;
}
/*前序遍歷*/
int PreOrderBiTree(BiTNode *T)
{
    if(T==NULL)return 0;
    printf("%d",T->data);
    PreOrderBiTree(T->lchild);
    PreOrderBiTree(T->rchild);
    return 1;
}
int PreOrderBiTree1(BiTNode *T)
{//非遞歸實現(xiàn)前序遍歷
    stack<BiTNode*> S;
    do{
        while(T!=NULL)
        {
            printf("%d",T->data);
            S.push(T);
            T=T->lchild;
        }
        if(!S.empty())
        {
            BiTNode *tempP;
            tempP=S.top();
            S.pop();
            T=tempP->rchild;
        }
    }while(!S.empty()||T!=NULL);

}
/*中序遍歷*/
int MiddleOrderBiTree(BiTNode *T)
{
    if(T==NULL)return 0;
    MiddleOrderBiTree(T->lchild);
    printf("%d",T->data);
    MiddleOrderBiTree(T->rchild);
}
int MiddleOrderBiTree1(BiTNode *T)
{//非遞歸實現(xiàn)前序遍歷
    stack<BiTNode*> S;
    do{
        while(T!=NULL)
        {
            S.push(T);
            T=T->lchild;
        }
        if(!S.empty())
        {
            BiTNode *tempP;
            tempP=S.top();
            S.pop();
            printf("%d",tempP->data);
            T=tempP->rchild;
        }
    }while(!S.empty()||T!=NULL);

}
/*后序遍歷*/
int PostOrderBiTree(BiTNode *T)
{
    if(T==NULL)return 0;
    PostOrderBiTree(T->lchild);
    PostOrderBiTree(T->rchild);
    printf("%d",T->data);
}
/*后序遍歷的非遞歸實現(xiàn)*/
int PostOrderBiTree2(BiTNode *T)
{
    stack<BiTNode*> S;
    do{
        while(T!=NULL)
        {
            S.push(T);
            T=T->lchild;
        }
        if(!S.empty()&&(S.top())->tag==1)
        {
            (S.top())->tag=2;
            T=S.top()->rchild;
        }
        else if(!S.empty()&&S.top()->tag==2)
        {
            BiTNode* d= S.top();
            S.pop();
            printf("%d",d->data);
        }
    }while(!S.empty()||T!=NULL);
}
/*層次序遍歷*/
void LevelOrderBiTree(BiTNode *T)
{
    queue<BiTNode*> So;
    So.push(T);
    BiTNode* ss = So.front();
    while(ss!=NULL){
        printf("%d", ss->data);
        So.pop();
        So.push(ss->lchild);
        So.push(ss->rchild);
        ss = So.front();
    };
}

/*二叉樹深度*/
int depth(BiTNode *T)
{
    if(T==NULL)return 0;
    int l=depth(T->lchild);
    int r=depth(T->rchild);
    if(l<=r)return r+1;
    else return l+1;
}

/*二叉樹復(fù)制*/
void CopyBTree(BiTNode* t,BiTNode* str)//將t賦值給str
{
    if(t==NULL) str=NULL;
    if(t!=NULL){
        str=new BiTNode;
        str->data=t->data;
        CopyBTree(t->lchild,str->lchild);
        CopyBTree(t->rchild,str->rchild);
    }
}


int main()
{
    BiTNode *p;
    CreatBiTree(&p);
    printf("前序遍歷:\n");
    PreOrderBiTree(p);
    printf("\n中序遍歷\n");
    MiddleOrderBiTree(p);
    printf("\n后序遍歷\n");
    PostOrderBiTree(p);
    printf("\n層次序遍歷\n");LevelOrderBiTree(p);
    printf("\n樹的深度\n");
    printf("\n%d",depth(p));
    BiTNode* cp;
    CopyBTree(p,cp);
    if(cp==NULL)printf("ll");
    PostOrderBiTree(cp);
}