tbin.c

稀疏矩阵、链表、图、队列、二叉树、多叉树、排序、遗传算法等的实现

/* tbin - manipulates threaded binary trees.
   Derived from libavl for manipulation of binary trees.
   Copyright (C) 1998-2000 Free Software Foundation, Inc.

   This program is free software; you can redistribute it and/or
   modify it under the terms of the GNU General Public License as
   published by the Free Software Foundation; either version 2 of the
   License, or (at your option) any later version.

   This program is distributed in the hope that it will be useful, but
   WITHOUT ANY WARRANTY; without even the implied warranty of
   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
   General Public License for more details.

   You should have received a copy of the GNU General Public License
   along with this program; if not, write to the Free Software
   Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA
   02111-1307, USA.

   The author may be contacted at <[e-mail]> on the Internet,
   or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA through
   more mundane means. */

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

/* A threaded binary tree node. */
struct tbin_node {
  int data;
  struct tbin_node *left;
  struct tbin_node *right;
  unsigned l_thread:1;
  unsigned r_thread:1;
};

/* A binary tree. */
struct tbin_tree {
  struct tbin_node *root;
  int count;
};

/* Creates and returns a new threaded binary tree.  Returns a null
   pointer if a memory allocation error occurs. */
struct tbin_tree *tbin_create(void)
{
  struct tbin_tree *tree = malloc(sizeof *tree);
  if (tree == NULL)
    return NULL;
  tree->root = NULL;
  tree->count = 0;
  return tree;
}

/* Searches TREE for matching ITEM.  Returns 1 if found, 0
   otherwise. */
int tbin_search(const struct tbin_tree *tree, int item)
{
  const struct tbin_node *node;

  assert(tree != NULL);

  node = tree->root;
  if (node == NULL)
    return 0;

  for (;;) {
    if (item == node->data)
      return 1;
    else if (item > node->data) {
      if (node->r_thread == 0)
	node = node->right;
      else
	return 0;
    }
    else {
      if (node->l_thread == 0)
	node = node->left;
      else
	return 0;
    }
  }
}

/* Allocates a new node in TREE.  Sets the node's data to ITEM and
   initializes the other fields appropriately. */
static struct tbin_node *new_node(struct tbin_tree *tree,
				  int item)
{
  struct tbin_node *node = malloc(sizeof *node);
  if (node == NULL)
    return NULL;

  node->data = item;
  tree->count++;
  return node;
}

/* Inserts ITEM into TREE.  Returns 1 if the item was inserted, 2 if
   an identical item already existed in TREE, or 0 if a memory
   allocation error occurred. */
int tbin_insert(struct tbin_tree *tree, int item)
{
  struct tbin_node *z, *y;

  assert(tree != NULL);

  z = tree->root;
  if (z == NULL) {
    y = tree->root = new_node(tree, item);
    if (y == NULL)
      return 0;

    y->left = y->right = NULL;
    y->l_thread = y->r_thread = 1;
    return 1;
  }

  for (;;) {
    if (item == z->data)
      return 2;
    else if (item > z->data) {
      if (z->r_thread == 1) {
	y = new_node(tree, item);
	if (y == NULL)
	  return 0;

	y->right = z->right;
	y->r_thread = 1;
	z->right = y;
	z->r_thread = 0;
	y->left = z;
	y->l_thread = 1;

	return 1;
      }

      z = z->right;
    }
    else {
      if (z->l_thread == 1) {
	y = new_node(tree, item);
	if (y == NULL)
	  return 0;

	y->left = z->left;
	y->l_thread = 1;
	z->left = y;
	z->l_thread = 0;
	y->right = z;
	y->r_thread = 1;

	return 1;
      }

      z = z->left;
    }
  }
}

/* Deletes any item matching ITEM from TREE.  Returns 1 if such an
   item was deleted, 0 if none was found. */
int tbin_delete(struct tbin_tree *tree, int item)
{
  struct tbin_node **q, *s, *t;

  assert(tree != NULL);

  t = tree->root;
  if (t == NULL)
    return 0;
  s = NULL;

  for (;;) {
    if (item == t->data)
      break;
    else if (item > t->data) {
      if (t->r_thread == 1)
	return 0;
      s = t;
      t = t->right;
    }
    else {
      if (t->l_thread == 1)
	return 0;
      s = t;
      t = t->left;
    }
  }

  if (s == NULL)
    q = &tree->root;
  else if (item > s->data)
    q = &s->right;
  else
    q = &s->left;

  if (t->l_thread == 0 && t->r_thread == 1) {
    struct tbin_node *r = t->left;
    while (r->r_thread == 0)
      r = r->right;
    if (r->right == t)
      r->right = t->right;

    *q = t->left;
  }
  else if (t->r_thread == 1) {
    if (s == NULL)
      *q = NULL;
    else if (item > s->data) {
      s->r_thread = 1;
      *q = t->right;
    }
    else {
      s->l_thread = 1;
      *q = t->left;
    }
  }
  else {
    struct tbin_node *r = t->right;
    if (r->l_thread == 1) {
      r->left = t->left;
      r->l_thread = t->l_thread;
      if (r->l_thread == 0) {
	struct tbin_node *p = r->left;
	while (p->r_thread == 0)
	  p = p->right;
	p->right = r;
      }
      *q = r;
    }
    else {
      struct tbin_node *p = r->left;
      while (p->l_thread == 0) {
	r = p;
	p = r->left;
      }

      t->data = p->data;
      if (p->r_thread == 1) {
	r->l_thread = 1;
	r->left = t;
      }
      else {
	s = r->left = p->right;
	while (s->l_thread == 0)
	  s = s->left;
	s->left = t;
      }
      t = p;
    }
  }

  free(t);
  tree->count--;
  return 1;
}

/* Helper function for tbin_walk().  Recursively prints data from each
   node in tree rooted at NODE in in-order. */
static void walk(const struct tbin_node *node)
{
  if (node->l_thread == 0)
    walk(node->left);
  printf("%d ", node->data);
  if (node->r_thread == 0)
    walk(node->right);
}

/* Prints all the data items in TREE in in-order. */
void tbin_walk(const struct tbin_tree *tree)
{
  assert(tree != NULL);
  if (tree->root != NULL)
    walk(tree->root);
}

/* Returns the next node in in-order in the tree after X, or NULL if X
   is the greatest node in the tree. */
static struct tbin_node *successor(struct tbin_node *x)
{
  struct tbin_node *y;

  assert(x != NULL);

  y = x->right;
  if (x->r_thread == 0)
    while (y->l_thread == 0)
      y = y->left;
  return y;
}

/* Return the node with the least value in the tree rooted at X. */
static struct tbin_node *minimum(struct tbin_node *x)
{
  while (x->l_thread == 0)
    x = x->left;
  return x;
}

/* Returns the previous node in in-order in the tree after X, or NULL if X
   is the greatest node in the tree. */
static struct tbin_node *predecessor(struct tbin_node *x)
{
  struct tbin_node *y;

  assert(x != NULL);

  y = x->left;
  if (x->l_thread == 0)
    while (y->r_thread == 0)
      y = y->right;
  return y;
}

/* Return the node with the greatest value in the tree rooted at X. */
static struct tbin_node *maximum(struct tbin_node *x)
{
  while (x->r_thread == 0)
    x = x->right;
  return x;
}

/* Prints all the data items in TREE in in-order, using an iterative