데이터 구조 (복습) --- 이 진 트 리 에 대한 기본 조작

// //               Coding
//            ，    （  ，   ）        
#include <cstdio>
#include <cstdlib>
//#define _OJ_
typedef struct tree
{
    char data;
    struct tree *left;
    struct tree *right;
} tree, *Bitree;

typedef struct Stack1
{
    int top, base;
    Bitree *elem;
} Stack1, *Stack;

Stack
Init_Stack(void)
{
    Stack s;
    s = (Stack) malloc (sizeof(Stack1));
    s->elem = (Bitree*) malloc (100 * sizeof(Bitree));
    s->top = s->base = 0;
    return s;
}

Bitree
Init_Bitree(Bitree T)
{
    char ch;
    scanf("%c", &ch);
    if(ch == '#')    T = NULL;

    else {
     T = (Bitree) malloc (sizeof(tree));
     T->data = ch;
     T->left = Init_Bitree(T->left);
     T->right = Init_Bitree(T->right);
    }
    return T;
}


void
push(Stack s, Bitree data)
{
    s->elem[s->top++] = data;
}

Bitree
pop(Stack s)
{
    return s->elem[--s->top];
}

Bitree
get_top(Stack s)
{
    return s->elem[s->top - 1];
}

int
isempty(Stack s)
{
    if(s->base == s->top)
        return 1;
    else
        return 0;
}

void
preoder_travers(Bitree T)
{
    if(T != NULL) {
        preoder_travers(T->left);
        printf("%c ", T->data);            //         
        preoder_travers(T->right);
    }
}

void
preoder_traver(Bitree T)
{
    Stack s;
    s = Init_Stack();

    while (T != NULL || isempty(s) != 1) {            //               
        while (T) {
            push(s, T);  printf("%c
", T->data);    T = T->left;
        }

     if(isempty(s) != 1) {
        T = pop(s);//    printf("%c
", T->data);
        T = T->right;
     }

  }
}

// ------------------------------------------------------------------------------------
//       
void
postoder_traver(Bitree T)
{
    Stack s;
    s = Init_Stack();
    Bitree T1, pre;
    T1 = T;    pre = NULL;    //T1    ，   pre        

    while (T1 != NULL || isempty(s) != 1) {
        while (T1) {
            push(s, T1);    T1 = T1->left;             //       
        }
    T1 = get_top(s);

    if(T1->right == NULL || T1->right == pre) {    //T1          
       printf("%c
", T1->data);
       pre = T1;    T1 = NULL;
       pop(s);                                    //    
    }
    else
        T1 = T1->right;
    }
}

int
dept_tree(Bitree T)
{
    int dept = 0, dept1 = 0, deep = 0;
    if(T) {
        dept  = dept_tree(T->left);
        dept1 = dept_tree(T->right); //               
        deep = dept > dept1 ? dept + 1 : dept1 + 1;
    }
    return deep;
}


int main(int argc, char const *argv[]) {
#ifndef _OJ_ //ONLINE JUDGE
       freopen("input.txt", "r", stdin);
       //freopen("output.txt", "w", stdout);
#endif
    

    int deep;

    Bitree T;

    T = Init_Bitree(T);                  //       

    // preoder_travers(T);               //    

    // preoder_traver(T);                //     

    // postoder_traver(T);              //       

    deep = dept_tree(T);               //      

    printf("     ：%d
", deep);


    
    return 0;
}
// ---------------------------------------------------------------------------------------
//         //             ，       leftchild , rightchild