数据结构（复习）--------关于二叉树的基本操作

// // 关于数据结构的总结与复习  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\n", T->data);    T = T->left;
        }

     if(isempty(s) != 1) {
        T = pop(s);//    printf("%c\n", 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\n", 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\n", deep);


    
    return 0;
}
// ---------------------------------------------------------------------------------------
// 层次遍历的思想
// 从根开始每次出队一个元素，都将这个元素的leftchild , rightchild入队直到无法入队将其最后全部出队