#ifndef _TREE_H
#define _TREE_H

struct Node;
typedef int ElementType;
typedef struct Node *PtrToNode;
typedef PtrToNode SearchTree;
typedef PtrToNode Position;

SearchTree MakeEmepty(SearchTree T);
Position Find(ElementType X,SearchTree T);
Position FindMin(SearchTree T);
Position FindMax(SearchTree T);
SearchTree Insert(ElementType X,SearchTree T);
SearchTree Delete(ElementType X,SearchTree T);

#endif

struct Node
{
    ElementType element;
    PtrToNode Left;
    PtrToNode Right;
};

#include <stdlib.h>
#include <stdio.h>
#include "tree.h"

SearchTree MakeEmpty(SearchTree T)
{
    if(T!=NULL){
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}
Position Find(ElementType X,SearchTree T)
{
    if(T==NULL){
        return NULL;
    }else if(X<T->element){
        return Find(X,T->Left);
    }else if(X>T->element){
        return Find(X,T->Right);
    }
    return T;
}
Position FindMin(SearchTree T)
{
    if(T!=NULL){
        while(T->Left!=NULL){
            T=T->Left;
        }
    }
    return T;
}
Position FindMax(SearchTree T)
{
    if(T!=NULL){
        while(T->Right!=NULL){
            T=T->Right;
        }
    }
    return T;
}
SearchTree Insert(ElementType X,SearchTree T)
{
    if(T==NULL){
        T=malloc(sizeof(struct Node));
        if(T==NULL){
            printf("out of space");
            exit(1);
        }else{
            T->Left=T->Right=NULL;
            T->element=X;
            return T;
        }
    }else if(X<T->element){
        T->Left=Insert(X,T->Left);
    }else if(X>T->element){
        T->Right=Insert(X,T->Right);
    }
    return T;
}
SearchTree Delete(ElementType X,SearchTree T)
{
    Position P;
    if(T==NULL){
        return NULL;
    }else if(X<T->element){
        Delete(X,T->Left);
    }else if(X>T->element){
        Delete(X,T->Right);
    }else if(T->Left!=NULL&&T->Right!=NULL){
        P=FindMax(T->Right);
        T->element=P->element;
        Delete(P->element,T->Right);
    }else{
        P=T;
        if(T->Left==NULL){
            T=T->Right;
        }else{
            T=T->Left;
        }
        free(P);
    }
    return T;
}