Quote:

> Does anyone have the source code of a binary search tree

> that includes the initilization, insert and delete functions? Your help is

> much appreciated.

Ironically enough, yes I do. Hopefully someone will point out

any bugs in the code below, because it's only been tested

superficially with the included test routines.

--bin.h----------------------------------------------------------

/* bin - manipulates binary trees.

Derived from libavl for manipulation of binary trees.

Copyright (C) 1998, 1999 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.

Internet, or as Ben Pfaff, 12167 Airport Rd, DeWitt MI 48820, USA

through more mundane means. */

#if !bin_h

#define bin_h 1

struct bin_tree;

struct bin_tree *bin_create(void);

int bin_search(const struct bin_tree *tree, int item);

int bin_insert(struct bin_tree *tree, int item);

int bin_delete(struct bin_tree *tree, int item);

void bin_walk(const struct bin_tree *tree);

void bin_traverse(const struct bin_tree *tree);

void bin_destroy(struct bin_tree *tree);

int bin_count(const struct bin_tree *tree);

#endif /* bin.h */

--bin.c----------------------------------------------------------

/* bin - manipulates binary trees.

Derived from libavl for manipulation of binary trees.

Copyright (C) 1998, 1999 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.

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>

#include "bin.h"

struct bin_node {

int data;

struct bin_node *left;

struct bin_node *right;

Quote:

};

struct bin_tree {

struct bin_node *root;

int count;

Quote:

};

struct bin_tree *

bin_create(void)

{

struct bin_tree *tree = malloc(sizeof *tree);

if (tree == NULL)

return NULL;

tree->root = NULL;

tree->count = 0;

return tree;

Quote:

}

int

bin_search(const struct bin_tree *tree, int item)

{

const struct bin_node *node;

assert(tree != NULL);

node = tree->root;

for (;;) {

if (node == NULL)

return 0;

else if (item == node->data)

return 1;

else if (item > node->data)

node = node->right;

else

node = node->left;

}

Quote:

}

int

bin_insert(struct bin_tree *tree, int item)

{

struct bin_node *node, **new;

assert(tree != NULL);

new = &tree->root;

node = tree->root;

for (;;) {

if (node == NULL) {

node = *new = malloc(sizeof *node);

if (node == NULL)

return 0;

node->data = item;

node->left = node->right = NULL;

tree->count++;

return 1;

}

else if (item == node->data)

return 2;

else if (item > node->data) {

new = &node->right;

node = node->right;

}

else {

new = &node->left;

node = node->left;

}

}

Quote:

}

int

bin_delete(struct bin_tree *tree, int item)

{

struct bin_node **q, *t;

assert(tree != NULL);

q = &tree->root;

t = tree->root;

for (;;) {

if (t == NULL)

return 0;

else if (item == t->data)

break;

else if (item > t->data) {

q = &t->right;

t = t->right;

}

else {

q = &t->left;

t = t->left;

}

}

if (t->right == NULL)

*q = t->left;

else {

struct bin_node *r = t->right;

if (r->left == NULL) {

r->left = t->left;

*q = r;

}

else {

struct bin_node *s = r->left;

while (s->left != NULL) {

r = s;

s = r->left;

}

r->left = s->right;

s->left = t->left;

s->right = t->right;

*q = s;

}

}

tree->count--;

free(t);

return 1;

Quote:

}

static void

walk(const struct bin_node *node)

{

if (node == NULL)

return;

walk(node->left);

printf("%d ", node->data);

walk(node->right);

Quote:

}

void

bin_walk(const struct bin_tree *tree)

{

assert(tree != NULL);

walk(tree->root);

Quote:

}

void

bin_traverse(const struct bin_tree *tree)

{

struct bin_node *stack[32];

int count;

struct bin_node *node;

assert(tree != NULL);

count = 0;

node = tree->root;

for (;;) {

while (node != NULL) {

stack[count++] = node;

node = node->left;

}

if (count == 0)

return;

node = stack[--count];

printf("%d ", node->data);

node = node->right;

}

Quote:

}

static void

destroy(struct bin_node *node)

{

if (node == NULL)

return;

destroy(node->left);

destroy(node->right);

free(node);

Quote:

}

void

bin_destroy(struct bin_tree *tree)

{

assert(tree != NULL);

destroy(tree->root);

free(tree);

Quote:

}

int

bin_count(const struct bin_tree *tree)

{

assert(tree != NULL);

return tree->count;

Quote:

}

/* Print the structure of node NODE of an binary tree, which is LEVEL

levels from the top of the tree. Uses different delimiters to

visually distinguish levels. */

void

print_structure(struct bin_node *node, int level)

{

assert(level <= 100);

if (node == NULL) {

printf(" nil");

return;

}

printf(" %c%d", "([{`/"[level % 5], node->data);

if (node->left || node->right) {

print_structure(node->left, level + 1);

if (node->right)

print_structure(node->right, level + 1);

}

printf("%c", ")]}'\\"[level % 5]);

Quote:

}

/* Examine NODE in a binary tree. *COUNT is increased by the number

of nodes in the tree, including the current one. If the node is

the root of the tree, PARENT should be INT_MIN, otherwise it should

be the parent node value. If this node is a left child of its

parent node, DIR should be -1. Otherwise, if it is not the root,

it is a right child and DIR must be +1. Sets *OKAY to 0 if an

error is found. */

void

recurse_tree(struct bin_node *node, int *count, int parent,

int dir, int *okay)

{

if (node == NULL)

return;

assert(count != NULL);

(*count)++;

recurse_tree(node->left, count, node->data, -1, okay);

recurse_tree(node->right, count, node->data, +1, okay);

if (parent != INT_MIN) {

assert(dir == -1 || dir == +1);

if (dir == -1 && node->data > parent) {

printf(" Node %d is smaller than its left child %d.\n",

parent, node->data);

*okay = 0;

}

else if (dir == +1 && node->data < parent) {

printf(" Node %d is larger than its right child %d.\n",

parent, node->data);

*okay = 0;

}

}

Quote:

}

/* Checks that TREE's structure is kosher and verifies that the values

in ARRAY are actually in the tree. There must be as many elements

in ARRAY as there are nodes in the tree. Exits the program if an

error was encountered. */

void

verify_tree(struct bin_tree *tree, int array[])

{

int count = 0;

int okay = 1;

recurse_tree(tree->root, &count, INT_MIN, 0, &okay);

if (count != tree->count) {

printf(" Tree has %d nodes, but tree count is %d.\n",

count, tree->count);

okay = 0;

}

if (okay) {

int i;

for (i = 0; i < tree->count; i++)

if (!bin_search(tree, array[i])) {

printf("Tree does not contain expected value %d.\n",

array[i]);

okay = 0;

}

}

if (!okay) {

printf("Error(s) encountered, aborting execution.\n");

exit(EXIT_FAILURE);

}

Quote:

}

/* Arrange the N elements of ARRAY in random order. */

void

shuffle(int *array, int n)

{

int i;

for (i = 0; i < n; i++) {

int j = i + rand() % (n - i);

int t = array[j];

array[j] = array[i];

array[i] = t;

}

Quote:

}

/* Size of tree used for testing. */

#define TREE_SIZE 16

/* Simple stress test procedure for the binary tree routines. Does

the following:

* Generate a random number seed. By default this is generated from

the current time. You can also pass an integer seed value on the

command line if you want to test the same case. The seed value is

displayed.

* Create a tree and insert the integers from 0 up to TREE_SIZE - 1

into it, in random order. Verifies and displays the tree structure

after each insertion.

* Removes each integer from the tree, in a different random order.

Verifies and displays the tree structure after each deletion.

* Destroys the tree.

This is pretty good test code if you write some of your own binary

tree routines. If you do so you will probably want to modify the

code below so that it increments the random seed and goes on to new

test cases automatically. */

int

main(int argc, char **argv)

{

int array[TREE_SIZE];

struct bin_tree *tree;

int i;

{

int seed;

if (argc == 2)

seed = atoi(argv[1]);

else

seed = time(0) * 257 % 32768;

...

**read more »**