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

struct Node
{
  int value;
  struct Node *left;
  struct Node *right;
};

struct Node *newNode(int value)
{
  struct Node *p = malloc(sizeof(*p));
  p->value = value;
  p->left = NULL;
  p->right = NULL;
  return p;
}

struct Node *addNode(struct Node *p, int value)
{
  if (p == NULL)
  {
    return newNode(value);
  }
  else
  {
    if (value < p->value)
    {
      p->left = addNode(p->left, value);
    }
    else
    {
      p->right = addNode(p->right, value);
    }

    return p;
  }
}

struct Node *deleteMinNode(struct Node *p)
{
  struct Node* r;

  if (p == NULL)
  {
    return NULL;
  }
  else
  {
    if (p->left == NULL)
    {
      r = p->right;
      free(p);
      return r;
    }
    else
    {
      p->left = deleteMinNode(p->left);
      return p;
    }
  }
}

struct Node *deleteNode(struct Node *p, int value, int *deleted)
{
  struct Node *r;
  struct Node *n;

  if (p == NULL)
  {
    *deleted = 0;
    return NULL;
  }
  else
  {
    if (value < p->value)
    {
      p->left = deleteNode(p->left, value, deleted);
      return p;
    }
    else if (p->value < value)
    {
      p->right = deleteNode(p->right, value, deleted);
      return p;
    }
    else
    {
      if (p->left == NULL)
      {
        r = p->right;
        free(p);
      }
      else if (p->right == NULL)
      {
        r = p->left;
        free(p);
      }
      else
      {
        n = p->right;

        while (n->left != NULL)
        {
          n = n->left;
        }

        p->value = n->value;
        p->right = deleteMinNode(p->right);
        r = p;
      }

      *deleted = 1;
      return r;
    }
  }
}

void writeNode(struct Node *p)
{
  if (p == NULL)
  {
    printf("_ ");
  }
  else
  {
    printf("[ %d ", p->value);
    writeNode(p->left);
    writeNode(p->right);
    printf("] ");
  }
}

void destroyNode(struct Node *p)
{
  if (p == NULL)
  {
    return;
  }
  else
  {
    destroyNode(p->left);
    destroyNode(p->right);
    free(p);
  }
}

int main(int argc, char *argv[])
{
  int i;
  int deleted;
  struct Node *p = NULL;

  for (i = 1; i < argc; i++)
  {
    if (strcmp(argv[i], "--") == 0)
    {
      break;
    }
    else
    {
      p = addNode(p, atoi(argv[i]));
    }
  }

  printf("入力データ ");
  writeNode(p);
  printf("\n");

  for (i = i + 1; i < argc; i++)
  {
    printf("deleteNode(%d)\n", atoi(argv[i]));
    p = deleteNode(p, atoi(argv[i]), &deleted);

    if (deleted)
    {
      printf("==> ");
      writeNode(p);
      printf("\n");
    }
    else
    {
      printf("deleteNode: 指定キーのノードがありません\n");
    }
  }

  destroyNode(p);

  return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgoKc3RydWN0IE5vZGUKewogIGludCB2YWx1ZTsKICBzdHJ1Y3QgTm9kZSAqbGVmdDsKICBzdHJ1Y3QgTm9kZSAqcmlnaHQ7Cn07CgpzdHJ1Y3QgTm9kZSAqbmV3Tm9kZShpbnQgdmFsdWUpCnsKICBzdHJ1Y3QgTm9kZSAqcCA9IG1hbGxvYyhzaXplb2YoKnApKTsKICBwLT52YWx1ZSA9IHZhbHVlOwogIHAtPmxlZnQgPSBOVUxMOwogIHAtPnJpZ2h0ID0gTlVMTDsKICByZXR1cm4gcDsKfQoKc3RydWN0IE5vZGUgKmFkZE5vZGUoc3RydWN0IE5vZGUgKnAsIGludCB2YWx1ZSkKewogIGlmIChwID09IE5VTEwpCiAgewogICAgcmV0dXJuIG5ld05vZGUodmFsdWUpOwogIH0KICBlbHNlCiAgewogICAgaWYgKHZhbHVlIDwgcC0+dmFsdWUpCiAgICB7CiAgICAgIHAtPmxlZnQgPSBhZGROb2RlKHAtPmxlZnQsIHZhbHVlKTsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgcC0+cmlnaHQgPSBhZGROb2RlKHAtPnJpZ2h0LCB2YWx1ZSk7CiAgICB9CgogICAgcmV0dXJuIHA7CiAgfQp9CgpzdHJ1Y3QgTm9kZSAqZGVsZXRlTWluTm9kZShzdHJ1Y3QgTm9kZSAqcCkKewogIHN0cnVjdCBOb2RlKiByOwoKICBpZiAocCA9PSBOVUxMKQogIHsKICAgIHJldHVybiBOVUxMOwogIH0KICBlbHNlCiAgewogICAgaWYgKHAtPmxlZnQgPT0gTlVMTCkKICAgIHsKICAgICAgciA9IHAtPnJpZ2h0OwogICAgICBmcmVlKHApOwogICAgICByZXR1cm4gcjsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgcC0+bGVmdCA9IGRlbGV0ZU1pbk5vZGUocC0+bGVmdCk7CiAgICAgIHJldHVybiBwOwogICAgfQogIH0KfQoKc3RydWN0IE5vZGUgKmRlbGV0ZU5vZGUoc3RydWN0IE5vZGUgKnAsIGludCB2YWx1ZSwgaW50ICpkZWxldGVkKQp7CiAgc3RydWN0IE5vZGUgKnI7CiAgc3RydWN0IE5vZGUgKm47CgogIGlmIChwID09IE5VTEwpCiAgewogICAgKmRlbGV0ZWQgPSAwOwogICAgcmV0dXJuIE5VTEw7CiAgfQogIGVsc2UKICB7CiAgICBpZiAodmFsdWUgPCBwLT52YWx1ZSkKICAgIHsKICAgICAgcC0+bGVmdCA9IGRlbGV0ZU5vZGUocC0+bGVmdCwgdmFsdWUsIGRlbGV0ZWQpOwogICAgICByZXR1cm4gcDsKICAgIH0KICAgIGVsc2UgaWYgKHAtPnZhbHVlIDwgdmFsdWUpCiAgICB7CiAgICAgIHAtPnJpZ2h0ID0gZGVsZXRlTm9kZShwLT5yaWdodCwgdmFsdWUsIGRlbGV0ZWQpOwogICAgICByZXR1cm4gcDsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgaWYgKHAtPmxlZnQgPT0gTlVMTCkKICAgICAgewogICAgICAgIHIgPSBwLT5yaWdodDsKICAgICAgICBmcmVlKHApOwogICAgICB9CiAgICAgIGVsc2UgaWYgKHAtPnJpZ2h0ID09IE5VTEwpCiAgICAgIHsKICAgICAgICByID0gcC0+bGVmdDsKICAgICAgICBmcmVlKHApOwogICAgICB9CiAgICAgIGVsc2UKICAgICAgewogICAgICAgIG4gPSBwLT5yaWdodDsKCiAgICAgICAgd2hpbGUgKG4tPmxlZnQgIT0gTlVMTCkKICAgICAgICB7CiAgICAgICAgICBuID0gbi0+bGVmdDsKICAgICAgICB9CgogICAgICAgIHAtPnZhbHVlID0gbi0+dmFsdWU7CiAgICAgICAgcC0+cmlnaHQgPSBkZWxldGVNaW5Ob2RlKHAtPnJpZ2h0KTsKICAgICAgICByID0gcDsKICAgICAgfQoKICAgICAgKmRlbGV0ZWQgPSAxOwogICAgICByZXR1cm4gcjsKICAgIH0KICB9Cn0KCnZvaWQgd3JpdGVOb2RlKHN0cnVjdCBOb2RlICpwKQp7CiAgaWYgKHAgPT0gTlVMTCkKICB7CiAgICBwcmludGYoIl8gIik7CiAgfQogIGVsc2UKICB7CiAgICBwcmludGYoIlsgJWQgIiwgcC0+dmFsdWUpOwogICAgd3JpdGVOb2RlKHAtPmxlZnQpOwogICAgd3JpdGVOb2RlKHAtPnJpZ2h0KTsKICAgIHByaW50ZigiXSAiKTsKICB9Cn0KCnZvaWQgZGVzdHJveU5vZGUoc3RydWN0IE5vZGUgKnApCnsKICBpZiAocCA9PSBOVUxMKQogIHsKICAgIHJldHVybjsKICB9CiAgZWxzZQogIHsKICAgIGRlc3Ryb3lOb2RlKHAtPmxlZnQpOwogICAgZGVzdHJveU5vZGUocC0+cmlnaHQpOwogICAgZnJlZShwKTsKICB9Cn0KCmludCBtYWluKGludCBhcmdjLCBjaGFyICphcmd2W10pCnsKICBpbnQgaTsKICBpbnQgZGVsZXRlZDsKICBzdHJ1Y3QgTm9kZSAqcCA9IE5VTEw7CgogIGZvciAoaSA9IDE7IGkgPCBhcmdjOyBpKyspCiAgewogICAgaWYgKHN0cmNtcChhcmd2W2ldLCAiLS0iKSA9PSAwKQogICAgewogICAgICBicmVhazsKICAgIH0KICAgIGVsc2UKICAgIHsKICAgICAgcCA9IGFkZE5vZGUocCwgYXRvaShhcmd2W2ldKSk7CiAgICB9CiAgfQoKICBwcmludGYoIuWFpeWKm+ODh+ODvOOCvyAiKTsKICB3cml0ZU5vZGUocCk7CiAgcHJpbnRmKCJcbiIpOwoKICBmb3IgKGkgPSBpICsgMTsgaSA8IGFyZ2M7IGkrKykKICB7CiAgICBwcmludGYoImRlbGV0ZU5vZGUoJWQpXG4iLCBhdG9pKGFyZ3ZbaV0pKTsKICAgIHAgPSBkZWxldGVOb2RlKHAsIGF0b2koYXJndltpXSksICZkZWxldGVkKTsKCiAgICBpZiAoZGVsZXRlZCkKICAgIHsKICAgICAgcHJpbnRmKCI9PT4gIik7CiAgICAgIHdyaXRlTm9kZShwKTsKICAgICAgcHJpbnRmKCJcbiIpOwogICAgfQogICAgZWxzZQogICAgewogICAgICBwcmludGYoImRlbGV0ZU5vZGU6IOaMh+WumuOCreODvOOBruODjuODvOODieOBjOOBguOCiuOBvuOBm+OCk1xuIik7CiAgICB9CiAgfQoKICBkZXN0cm95Tm9kZShwKTsKCiAgcmV0dXJuIDA7Cn0=