#define MAX_TREE_NUMBER 200

typedef struct item
{
    char petname[20];
    char petkind[20];
}Item;

typedef struct node
{
    Item item;
    struct node *left;
    struct node *right;
}Node;

typedef struct tree
{
    Node *root;
    int size;
}Tree;

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

void initializeTree(Tree *ptree)
{
    ptree->root = NULL;
    ptree->size = 0;
}
bool TreeIsEmpey(const Tree *ptree)
{
    return ptree->size == 0;
}
bool TreeIsFull(const Tree *ptree)
{
    return ptree->size == MAX_TREE_NUMBER;
}
int TreeItemCount(const Tree *ptree)
{
    return ptree->size;
}
static Node *MakeNode(const Item *pi)
{
    Node *new_node;
    new_node = (Node *)malloc(sizeof(Node));
    if(new_node != NULL)
    {
        new_node->item = *pi;
        new_node->left = NULL;
        new_node->right = NULL;
    }
    return new_node;
}
static bool ToLeft(const Item *i1, const Item *i2)
{
    int comp1;
    if((comp1 = strcmp(i1->petname, i2->petname))< 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) < 0)
        return true;
    else
        return false;
}
static bool ToRight(const Item *i1, const Item *i2)
{
    int comp1;
    if((comp1 = strcmp(i1->petname, i2->petname))> 0)
        return true;
    else if (comp1 == 0 && strcmp(i1->petkind, i2->petkind) > 0)
        return true;
    else
        return false;
}
static Pair SeekItem(const Item *pi, const Tree *ptree)
{
    Pair look;
    look.parent = NULL;
    look.child = ptree->root;
    
    if(look.child == NULL)
        return look;
    
    while (look.child != NULL) {
        
        if (ToLeft(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child = look.child->left;
        }
        else if(ToRight(pi, &(look.child->item)))
        {
            look.parent = look.child;
            look.child  = look.child->right;
        }
        else
            break;
    }
    return look;
}
static void AddNode(Node *new_node, Node *root)
{
    if(ToLeft(&new_node->item, &root->item))
    {
        if(root->left == NULL)
            root->left = new_node;
        else
            AddNode(new_node, root->left);
    }
    
   else if(ToRight(&new_node->item, &root->item))
    {
        if(root->right == NULL)
            root->right = new_node;
        else
            AddNode(new_node, root->right);
    }
   else
   {
       fprintf(stderr, "location error in AddNode()\n");
       exit(1);
   }
}
bool AddItem(const Item *pi, Tree *ptree)
{
    Node *new_node;
    if(TreeIsFull(ptree))
    {
        fprintf(stderr, "Tree is full\n");
        return false;
    }
    if(SeekItem(pi, ptree).child != NULL)
    {
        fprintf(stderr, "Attempted to add duolucate item\n");
        return false;
    }
    new_node = MakeNode(pi);
    if(new_node == NULL)
    {
        fprintf(stderr, "Cound't create node\n");
        return false;
    }
    ptree->size++;
    if(ptree->root == NULL)
        ptree->root = new_node;
    else
        AddNode(new_node, ptree->root);
    
    return true;
}
bool InTree(const Tree *ptree, const  Item *pi)
{
    return (SeekItem(pi, ptree).child == NULL) ? true : false;
}
static void DeleteNode(Node **ptr)
{
    Node *temp;
    
    if((*ptr)->left == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->right;
        free(temp);
    }
    else if((*ptr)->right == NULL)
    {
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
    else
    {
        for(temp = (*ptr)->left; temp->right != NULL;temp = temp->right)
            continue;
        temp->right = (*ptr)->right;
        temp = *ptr;
        *ptr = (*ptr)->left;
        free(temp);
    }
}
bool DeleteItem(const Item *pi, Tree *ptree)
{
    Pair look;
    look = SeekItem(pi, ptree);
    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;
}
static void InOrder(const Node *root, void (*pfun)(Item item))
{
    if(root != NULL)
    {
        InOrder(root->left, pfun);
        (*pfun)(root->item);
        InOrder(root->right, pfun);
    }
}
void Traverse(const Tree *ptree, void (*pfun)(Item item))
{
    if(ptree != NULL)
        InOrder(ptree->root, pfun);
}
static void DeleteAllNodes(Node *root)
{
    Node *pright;
    if(root != NULL)
    {
        pright = root->right;
        DeleteAllNodes(root->left);
        free(root);
        DeleteAllNodes(pright);
    }
}
void DeleteAll(Tree *ptree)
{
    if(ptree != NULL)
        DeleteAllNodes(ptree->root);
    ptree->root = NULL;
    ptree->size = 0;
}