bst.c

来自「数据结构源码合集」· C语言 代码 · 共 146 行

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

typedef struct node *link;
struct node {
     int item;
     link l, r;
};

link NODE(int item, link l, link r)
{
     link t = malloc(sizeof *t);
     t->item = item; t->l = l; t->r = r;
     return t;
}

int bst_search(link t, int item)
{
     if(!t)
		 return 0;
     if(item < t->item)
		 return bst_search(t->l, item);
     if(item > t->item)
		 return bst_search(t->r, item);

     return 1;
}

link bst_insert(link t, int item)
{
     if(!t)
		 return NODE(item, NULL, NULL);
     if(item < t->item)
		 t->l = bst_insert(t->l, item);
     else if(item > t->item)
		 t->r = bst_insert(t->r, item);

     return t;
}

link bst_delete_first(link t, int item)
{
     link p;

     if(!t)
		 return NULL;
     if(item < t->item)
		 t->l = bst_delete(t->l, item);
     else if(item > t->item)
		 t->r = bst_delete(t->r, item);
     else
	 {
		if((t->l == NULL) && (t->r == NULL))
		{
			free(t);
			t = NULL;
		}
		else if(t->l)
		{
			for(p = t->l; p->r; p = p->r)
				;
			t->item = p->item;
			t->l = bst_delete(t->l, t->item);
		}
		else if (t->r)
		{
			for (p = t->r; p->l; p = p->l)
				;
			t->item = p->item;
			t->r = bst_delete(t->r, t->item);
		}
     }
     return t;
}

/*
link bst_delete_second(link t, int item)
{
	link x, p;

	if(t == NULL)
		return 0;
	if(item < t->item)
		bst_delete_second(t->l, item);
	else if(item > t->item)
		bst_delete_second(t->r, item);
	else
	{
		if((t->l == NULL) && (t->r == NULL))
		{
			free(t);
			t = NULL;
		}
		else if(t->l)
		{
			for(x = root; x->


*/

void pprint(link t)
{
     if (t) {
	  printf("(");
	  printf("%d", t->item);
	  pprint(t->l);
	  pprint(t->r);
	  printf(")");
     } else printf("( )");
}

void in_order(link t)
{
     if (!t) return;
     in_order(t->l);
     printf("%4d", t->item);
     in_order(t->r);
}

#define RANGE 100
#define N 16

int main()
{
     int i, item;
     link T = NULL;
     srand(time(NULL));
     for (i=0; i<N; i++) T = bst_insert(T, rand()%RANGE);
     
     in_order(T); printf("\n\n");
     printf("       \\tree"); pprint(T); printf("\n\n");
     while (T) {
	  item = rand()%RANGE;
	  if (bst_search(T, item)) {
	       printf("delete %d in tree\n", item);
	       T = bst_delete(T, item);
	       in_order(T); printf("\n\n");
	       printf("       \\tree"); pprint(T); printf("\n\n");
	  }
     }
	 
	 return 0;
}