elements. This project is to randomly generate a sequence of integer
numbers, insert the first 20 distinct numbers into a binary search tree,
and finally produce an in-order listing of the tree. You are provided
with the declarations and two functions for binary search trees (see the
appended). One of the functions is Insert that adds a new element to a
binary search tree. And the other is lookup which checks if a given
element is already in a binary search tree. In this project, you need to
define a print function that prints tree elements in in-order as well as
a count function that counts and returns the number of tree nodes in a
binary search tree. In addition you need to complete the main function.
You may use the built-in random number function to generate new elements
for inserting as shown below:
srand(time(NULL)); /* do it at the beginning of main function */
newElem = rand() % 100; /* generate a new element one at a time */
Then you can check for each new element if it is already there using the
lookup function and if there are enough elements in the tree using the
count function before doing insert. Finally, use the print function to
show the result.
/* declarations and function definitions for binary search trees */
#include
#include
#include
#define TRUE 1
#define FALSE 0
typedef int BOOLEAN;
typedef int ETYPE;
typedef struct NODE *TREE;
struct NODE {
ETYPE element;
TREE leftChild, rightChild;
};
TREE insert(ETYPE x, TREE T)
{
if (T == NULL) {
T = (TREE) malloc(sizeof(struct NODE));
T->element = x;
T->leftChild = NULL;
T->rightChild = NULL;
}
else if (x < T->element)
T->leftChild = insert(x, T->leftChild);
else if (x > T->element)
T->rightChild = insert(x, T->rightChild);
return T;
}
BOOLEAN lookup(ETYPE x, TREE T)
{
if (T == NULL)
return FALSE;
else if (x == T->element)
return TRUE;
else if (x < T->element)
return lookup(x, T->leftChild);
else /* x must be > T->element */
return lookup(x, T->rightChild);
}
