/******************************************************************************

    二分木からの削除

******************************************************************************/

#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <string.h>

struct tnode {
    char *word;                     /* 単語 */
    struct tnode *left;             /* 左の子へのポインタ */
    struct tnode *right;            /* 右の子へのポインタ */
};

typedef struct tnode Tnode;

#define BUFSIZE 1024    /* バッファの大きさ */

char *freadword(FILE *in);
Tnode *Tnode_search(Tnode **pp, char *s);
void Tnode_delete(Tnode **pp, Tnode *q);
Tnode *Tnode_extractmax(Tnode **pp);
Tnode *Tnode_construct(char *s);
void Tnode_destruct(Tnode *p);
void Tnode_printtree(Tnode* tp, int depth);
void Tnode_print(Tnode *p);

int main() {
    char buf[BUFSIZE+1];
    Tnode *root = NULL;
    Tnode *p;

    while (printf("? "), fgets(buf, BUFSIZE, stdin) != NULL) {
        p = Tnode_search(&root, buf);   /* 木から探す */
        if (p) {                        /* 見つかれば…… */
            Tnode_delete(&root, p);     /* 削除 */
        }
        Tnode_printtree(root, 0);       /* 木の印字 */
    }
    return 0;
}


/* 木 p 以下に s を探して返す。なければ加え、NULL を返す */
Tnode *Tnode_search(Tnode **pp, char *s) {
    int result;

    if (*pp == NULL) {
        *pp = Tnode_construct(s); return NULL;
    } else {
        result = strcmp(s, (*pp)->word);
        if (result < 0) {                       /* 小さければ左の部分木へ */
            return Tnode_search(&((*pp)->left), s);
        } else if (result > 0) {                /* 大きければ右の部分木へ */
            return Tnode_search(&((*pp)->right), s);
        } else {                                /* 一致すればアドレスを返す */
            return *pp;
        }
    }
}


/* *pp 以下から q を削除。*pp を新しい木に置き換えることも */
void Tnode_delete(Tnode **pp, Tnode *q) {
    int result;

    result = strcmp((*pp)->word, q->word);
    if (result > 0) {
        Tnode_delete(&((*pp)->left), q);
    } else if (result < 0) {
        Tnode_delete(&((*pp)->right), q);
    } else {    /* 見つかったとき */
        if (q->right == NULL) {
            Tnode_destruct(q); *pp = q->left; return;
        }
        if (q->left == NULL) {
            Tnode_destruct(q); *pp = q->right; return;
        }
        q = Tnode_extractmax(&(q->left));
        q->left = (*pp)->left, q->right = (*pp)->right;
        Tnode_destruct(*pp); *pp = q;
    }
}


/* *pp 以下で最大のものを木から取り除いてそれを返す */
Tnode *Tnode_extractmax(Tnode **pp) {
    Tnode *q, *q2;

    if ((*pp)->right == NULL) {
        q = *pp; *pp = q->left; return q;   /* このときのみ *pp が変わる */
    }
    for (q = *pp; q->right->right != NULL; q = q->right) {
        ;
    }
    q2 = q->right; q->right = NULL; return q2;
}


/* s から Tnode を構成 */
Tnode *Tnode_construct(char *s) {
    Tnode *p;

    if ((p = malloc(sizeof(Tnode))) == NULL) {
        return NULL;
    }
    if ((p->word = malloc(strlen(s)+1)) == NULL) {
        free(p); return NULL;
    }
    strcpy(p->word, s);
    p->left = p->right = NULL;
    return p;
}


/* p の指す Tnode を破壊 */
void Tnode_destruct(Tnode *p) {
    free(p->word); free(p);
}


/* 木 p を印字。深さつき */
void Tnode_printtree(Tnode *p, int depth) {
    int i;

    if (p == NULL) {
        return;
    }
    Tnode_printtree(p->left, depth + 1);
    for (i=0; i<depth; i++) {
        printf("  ");
    }
    Tnode_print(p);
    Tnode_printtree(p->right, depth + 1);
}


/* p の指す Tnode を印字 */
void Tnode_print(Tnode *p) {
    printf("%s", p->word);
}