#include <stdio.h>
#include <string.h>
#include <malloc.h>

typedef struct tree_node
{
    int value;
    struct tree_node *left;
    struct tree_node *right;
    struct tree_node *parent;
} node_t;

static int value = 0;

struct tree_node * __tree_create(int n)
{
    struct tree_node *tnode = NULL;

    if (n-- < 0)
    {
        return NULL;
    }

    tnode = (struct tree_node *)malloc(sizeof(struct tree_node));
    if (NULL == tnode)
    {
        return NULL;
    }
    tnode->value = value++;
    printf("%4d\n", tnode->value);
    tnode->left = __tree_create(n);
    tnode->right = __tree_create(n);

    return tnode;
}

void tree_dump(struct tree_node *t)
{
    if (NULL == t)
    {
        return;
    }
    tree_dump(t->left);
    tree_dump(t->right);
    printf("%4d\n", t->value);
}

void tree_free(struct tree_node *t)
{
    if (NULL == t)
    {
        return;
    }
    tree_free(t->left);
    tree_free(t->right);
    printf("free tnode %4d\n", t->value);
    memset(t, 0, sizeof(struct tree_node));
    free(t);
}

int tree_depth(struct tree_node *t)
{
    int a = 0;
    int b = 0;

    if (NULL == t)
    {
        return 0;
    }

    a = tree_depth(t->left);
    b = tree_depth(t->right);

    return (a > b ? a : b) + 1;

}

void __tree_dump_by_layer(struct tree_node *t, int level)
{
    if (NULL == t || level < 0)
    {
        return;
    }

    if (0 == level)
    {
        printf("%4d  ", t->value);
        return;
    }
    __tree_dump_by_layer(t->left, level-1);
    __tree_dump_by_layer(t->right, level-1);
}

int tree_node_number(int level)
{
    int i = 0;
    int ret = 1;

    if (level <= 0)
    {
        return 1;
    }
    for (i = 0; i < level; i++)
    {
        ret = ret * 2;
    }
    return ret;
}


void printkong(int depth, int level)
{
}

void tree_dump_by_layer(struct tree_node *t, int depth)
{
    int i = 0;
    printf("\n");
    printf("\n");
    for (i = 0; i <= depth; i++)
    {
        printkong(depth, i);
        __tree_dump_by_layer(t, i);
        printf("\n");
    }
    printf("\n");
}

struct tree_node *tree_get_null_node(struct tree_node *t)
{
    if (NULL == t)
    {
        return;
    }
    tree_dump(t->left);
    tree_dump(t->right);
    printf("%4d\n", t->value);
}

struct tree_node *tree_insert(struct tree_node *t,int x)
{
    struct tree_node *tnode = NULL;
    struct tree_node *nnode = NULL;
    if (NULL == tnode)
    {
        return NULL;
    }

    nnode = tree_get_null_node(tree_node);
    if (NULL == nnode)
    {
        printf("this not be happen\n");
        return NULL;
    }

    tnode =malloc(sizeof(struct tree_node));
    if (NULL == tnode)
    {
        printf("get mem failed\n");
        return NULL;
    }

    tnode->value = x;
    tnode->left = NULL;
    tnode->right = NULL;

    if (NULL == nnode->left)
    {
        nnode->left = tnode;
    }
    else if (NULL == nnode->right)
    {
        nnode->left = tnode;
    }
    return nnode;
}


int main(void)
{
    struct tree_node *tree = NULL;

    tree = __tree_create(3);
    if (NULL == tree)
    {
        perror("tree create failed");
        return 0;
    }

    tree_dump(tree);
    tree_dump_by_layer(tree, 3);
    printf("tree depth is %d\n", tree_depth(tree));
    tree_free(tree);

    return 0;
}