#include <stdio.h>

//-----------------------------------------------------------------
// 構造体
//-----------------------------------------------------------------
typedef struct seg_node{
    int data,level;
    struct seg_node *left_node;  /* 左の子へのポインタ */
    struct seg_node *right_node; /* 右の子へのポインタ */
} seg_t;
typedef struct _find_node_ {
    int lorr_next,lorr_now;
    seg_t *next,*parent_next;
    seg_t *now,*parent_now;
} find_t;
enum LEFT_or_RIGHT {
    TLEFT  = 0,
    TRIGHT = 1,
};
enum FIND_DIR {
    FIND_LARGE = 0,
    FIND_SMALL = 1,
};
//-----------------------------------------------------------------
// 関数宣言
//-----------------------------------------------------------------
seg_t *data_input(seg_t *root_node);
seg_t *set_node(int data);
seg_t *make_tree(seg_t *root_node, seg_t *new_node);
void find_node(seg_t **f_node,seg_t *root_node,int data);
void del_node(seg_t **root_node);
void delfind_node(int fdir,find_t *f_node,seg_t *parent_node,
                  seg_t *root_node,int lorr,int data);
void list_tree(seg_t *root_node);
void disp_node(seg_t *p);
void delete_tree(seg_t *root_node);
//-----------------------------------------------------------------

int main(void)
{
    seg_t *p,*root_node;
    char a[20];
    int x,flg=1;
    root_node = NULL; /* 初期化 */
    while(flg){
        printf("入力：1 検索：2 削除:3 終了：9 -> ");
        scanf("%s",a);
        x = atoi(a);
        switch(x){
        case 1:
            root_node = data_input(root_node); /* データの入力 */
            break;
        case 2:
            printf("find data = ");
            scanf("%d",&x);
            p = NULL;
            find_node(&p,root_node,x);
            disp_node(p);
            break;
        case 3:
            del_node(&root_node);
            break;
        case 9:
            flg = 0;
            break;
        }
        if(flg){
            printf("**tree structure\n");
            list_tree(root_node); /* 降順表示 */
        }
    }
    delete_tree(root_node);
    return 0;
}

/* データ入力 */
seg_t *data_input(seg_t *root_node)
{
    seg_t *new_node; /* 新しいノードのポインタ */
    char a[20];
    int indata;
    printf("input data = ");
    scanf("%s", a);
    indata = atoi(a);
    /* 新しいノードへデータを入れる */
    new_node  = set_node(indata);
    /* 新しいノードを2分木に挿入 */
    root_node = make_tree(root_node, new_node);
}

/* ノード作成関数 */
seg_t *set_node(int data){
    seg_t *new_node; /* 新しいノードのポインタ */
    new_node = (seg_t *)malloc(sizeof(seg_t));
    if(new_node == NULL){
        fprintf(stderr,"cannot alloc node\n");
        exit(1);
    }
    new_node->data  = data;
    new_node->level = 0;
    new_node->left_node  = NULL;
    new_node->right_node = NULL;
    return(new_node);
}

/* ノードの2分木への挿入 */
seg_t *make_tree(seg_t *root_node, seg_t *new_node)
{
    if (root_node == NULL){
        return new_node;
    } else {
        if (root_node->data > new_node->data){
            root_node->left_node  = make_tree(root_node->left_node, new_node);
            root_node->left_node->level  = root_node->level+1;
        } else {
            root_node->right_node = make_tree(root_node->right_node, new_node);
            root_node->right_node->level = root_node->level+1;
        }
    }
    return root_node;
}

/* 数値データの検索 */
void find_node(seg_t **f_node,seg_t *root_node,int data)
{
    if(*f_node != NULL) return;
    if(root_node != NULL) {
        find_node(f_node,root_node->right_node,data);
        if(data == root_node->data){
            *f_node = root_node;
        }
        find_node(f_node,root_node->left_node,data);
    }
}

/* ノードの削除 */
void del_node(seg_t **root_node)
{
    int a;
    find_t p;
    p.lorr_next = p.lorr_now = TLEFT;
    p.parent_next = p.parent_now = p.next = p.now = NULL;
    printf("del data = ");
    scanf("%d",&a);
    delfind_node(FIND_LARGE,&p,NULL,*root_node,TRIGHT,a);
    if(p.now == NULL && p.next == NULL) return;
    if(p.next == NULL)
        delfind_node(FIND_SMALL,&p,NULL,*root_node,TRIGHT,a);
    if(p.now == NULL && p.next == NULL) return;
    // disp test
    disp_node(p.now);
    disp_node(p.next);
    getchar();
    //------------------------------------------------------
    // 一番大きいノードを削除するときが問題となる。。
    //------------------------------------------------------
    // link change
    if(p.now != NULL && p.next != NULL){
        // 根の変更
        if(p.parent_now == NULL) *root_node = p.next;
        // ノードのリンク内容の変更
        if(p.lorr_now == TLEFT){
            if(p.now->left_node==NULL&&p.now->right_node==NULL){
                if(p.parent_now) p.parent_now->left_node = NULL;
            } else {
                if(p.next->level > p.now->level) p.next->level = p.now->level;
                if(p.parent_next){
                    if(p.lorr_next == TLEFT) p.parent_next->left_node  = NULL;
                    else                     p.parent_next->right_node = NULL;
                }
                if(p.parent_now) p.parent_now->left_node = p.next;
            }
            if(p.now->left_node)  p.next->left_node  = p.now->left_node;
            if(p.now->right_node) p.next->right_node = p.now->right_node;
        } else {
            if(p.now->left_node==NULL&&p.now->right_node==NULL){
                if(p.parent_now) p.parent_now->right_node = NULL;
            } else {
                if(p.next->level > p.now->level) p.next->level = p.now->level;
                if(p.parent_next){
                    if(p.lorr_next == TLEFT) p.parent_next->left_node  = NULL;
                    else                     p.parent_next->right_node = NULL;
                }
                if(p.parent_now) p.parent_now->right_node = p.next;
            }
            if(p.now->left_node)  p.next->left_node  = p.now->left_node;
            if(p.now->right_node) p.next->right_node = p.now->right_node;
        }
        free(p.now);
    }
}

/* 削除用の検索 */
void delfind_node(int fdir,find_t *f_node,seg_t *parent_node,seg_t *root_node,
                  int lorr,int data)
{
    if(root_node != NULL) {
        // 一つ大きいノードを検索
        if(fdir == FIND_LARGE){
            delfind_node(fdir,f_node,root_node,root_node->right_node,
                         TRIGHT,data);
            if(data == root_node->data && f_node->now == NULL){
                f_node->now        = root_node;
                f_node->parent_now = parent_node;
                f_node->lorr_now   = lorr;
            }
            if(data < root_node->data){
                f_node->next        = root_node;
                f_node->parent_next = parent_node;
                f_node->lorr_next   = lorr;
            }
            delfind_node(fdir,f_node,root_node,root_node->left_node,
                         TLEFT,data);
        }
        // 一つ小さいノードを検索
        else {
            delfind_node(fdir,f_node,root_node,root_node->left_node,
                         TLEFT,data);
            if(data == root_node->data && f_node->now == NULL){
                f_node->now        = root_node;
                f_node->parent_now = parent_node;
                f_node->lorr_now   = lorr;
            }
            if(data > root_node->data){
                f_node->next        = root_node;
                f_node->parent_next = parent_node;
                f_node->lorr_next   = lorr;
            }
            delfind_node(fdir,f_node,root_node,root_node->right_node,
                         TRIGHT,data);
        }
    }
}

/* 長さの長い順表示 */
void list_tree(seg_t *root_node)
{
    int i;
    if(root_node != NULL) {
        list_tree(root_node->right_node);
        for(i=0;i<root_node->level;i++) printf(" ");
        printf("%d\n",root_node->data);
        list_tree(root_node->left_node);
    }
}

/* ノードデータの出力 */
void disp_node(seg_t *p)
{
    if(p == NULL) return;
    printf("**node data\n");
    printf("* data[%2d],level[%2d]\n",p->data,p->level);
    // node exist->X , none->N
    printf("*  left");
    if(p->left_node  != NULL) printf("[X]");
    else                      printf("[N]");
    printf(",right");
    if(p->right_node != NULL) printf("[X]");
    else                      printf("[N]");
    printf("\n");
}

/* ノードデータの解放 */
void delete_tree(seg_t *root_node)
{
    if(root_node == NULL) return;
    delete_tree(root_node->left_node);
    delete_tree(root_node->right_node);
    free(root_node);
}