二分探索木

gistfile1.c

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

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

Node *create_node(int value) {
  Node *node = (Node *)malloc(sizeof(Node));
  node->value = value;
  node->left = node->right = NULL;
  return node;
}

void delete_node(Node *node) {
  free(node);
}

void delete_tree(Node *node) {
  if (!node)
    return;
  delete_tree(node->left);
  delete_tree(node->right);
  delete_node(node);
}

Node *search(Node *node, int value) {
  if (node->value == value)
    return node;
  else if (node->value > value)
    return node->left ? search(node->left, value) : NULL;
  else {
    assert(node->value < value);
    return node->right ? search(node->right, value) : NULL;
  }
}

void insert(Node *node, int value) {
  if (node->value == value)
    return;
  else if (node->value > value) {
    if (node->left) {
      insert(node->left, value);
    } else {
      Node *new_node = create_node(value);
      node->left = new_node;
    }
  } else if (node->value < value) {
    if (node->right) {
      insert(node->right, value);
    } else {
      Node *new_node = create_node(value);
      node->right = new_node;
    }
  }
}

void delete(Node *node, Node *parent, int value) {
  if (node->value == value) {
    if (!node->left && !node->right) {
      (parent->left == node) ? (parent->left = NULL) : (parent->right = NULL);
      delete_node(node);
      return;
    }
    if (!node->left) {
      assert(node->right);
      (parent->left == node) ? (parent->left = node->right) : (parent->right = node->right);
      delete_node(node);
      return;
    }
    if (!node->right) {
      assert(node->left);
      (parent->left == node) ? (parent->left = node->left) : (parent->right = node->left);
      delete_node(node);
      return;
    }
    Node *replace_node = node->left;
    Node *replace_node_parent = node;
    while (replace_node->right) {
      replace_node_parent = replace_node;
      replace_node = replace_node->right;
    }
    node->value = replace_node->value;
    (replace_node_parent->left == replace_node ) ? (replace_node_parent->left = replace_node->left) : (replace_node_parent->right = replace_node->left);
    delete_node(replace_node);
  } else if (node->value > value)
    return node->left ? delete(node->left, node, value) : NULL;
  else {
    assert(node->value < value);
    return node->right ? delete(node->right, node, value) : NULL;
  }
}

/* test */
void display(Node *node) {
  if (node->left) {
    display(node->left);
  }
  printf("%d ", node->value);
  if (node->right) {
    display(node->right);
  }
}

int main(void) {
  int data;
  Node *root = create_node(10);
  while (scanf("%d", &data) != EOF) {
    insert(root, data);
  }
  display(root);
  printf("\n");

  delete(root, NULL, 10);
  display(root);
  printf("\n");

  delete_tree(root);

  return 0;
}