#include "btree.h"

void InitTree(Tree * ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}

bool EmptyTree(const Tree * ptree)
{
    return !ptree->root?true:false;
}

int CountItem(const Tree * ptree)
{
    return ptree->size;
}

typedef struct pair {
    Node * parent;
    Node * child;
} Pair;


static bool ToLeft(ElemType e1, ElemType e2)
{
    return e1 < e2;
}
static bool ToRight(ElemType e1, ElemType e2)
{
    return e1 > e2;
}
static bool AddNode(Node * new, Node * root)
{
    if (ToLeft(new->e, root->e))
    {
        if (root->left == NULL)
            root->left = new;
        else
            AddNode(new,root->left);
    }
    else if (ToRight(new->e,root->e))
    {
        if (root->right == NULL)
            root->right = new;
        else
            AddNode(new,root->right);
    }
    else
        return false;
    return true;
}

static Pair SeekNode(Node * root, const ElemType e)
{
    Pair look;
    look.parent = NULL;
    look.child = root;

    if (look.child == NULL)
        return look;

    while (look.child != NULL)
    {
        if (ToLeft(e, look.child->e))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if (ToRight(e,look.child->e))
        {
            look.parent = look.child;
            look.child = look.child->right;
        }
        else
            break;
    }

    return look;
}

bool AddItem(const ElemType e, Tree * ptree)
{
    Node * new = (Node *) calloc (1,sizeof(Node));
    if (!new)
        return false;
    if(SeekNode(ptree->root,e).child)
        return false;

    new->e = e;
    
    ptree->size++;

    if (!ptree->root)
        ptree->root = new;
    else
        AddNode(new,ptree->root);

    return true;
}

static void DeleteNode(Node ** ptr)
{
    Node * tmp;

    if ((*ptr)->left == NULL)
    {
        tmp = *ptr;
        *ptr = (*ptr)->right;
        free(tmp);
    }
    else if ((*ptr)->right == NULL)
    {
        tmp = *ptr;
        *ptr = (*ptr)->left;
        free(tmp);
    }
    else
    {
        for (tmp = (*ptr)->left;tmp->right != NULL; tmp = tmp->right)
            continue;
        tmp->right = (*ptr)->right;
        tmp = *ptr;
        *ptr = (*ptr)->left;
        free(tmp);
    }
}

bool DeleteItem(const ElemType e, Tree * ptree)
{
    Pair look;

    look = SeekNode(ptree->root, e);
    if (look.child == NULL)
        return false;

    if (look.parent == NULL)
        DeleteNode(&ptree->root);
    else if (look.parent->left == look.child)
        DeleteNode(&look.parent->left);
    else
        DeleteNode(&look.parent->right);
    ptree->size--;

    return true;
}

bool ResTree(Node * root)
{
    Node * pnode = root;
    if (pnode->right)
        ResTree(pnode->right);
    if (pnode->left)
        ResTree(pnode->left);
    free(pnode);
    return true;
}

void PrintTree(const Node * root)
{
    printf("%c",root->e);
    if (root->left)
        PrintTree(root->left);
    if (root->right)
        PrintTree(root->right);
}