10.10 Programming Assignment: Binary Tree

This is what a binary search tree looks like:

You will use the following structure to implement a binary search tree:

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

You will write the following functions:

Node* Create(int value) 

This function will create a new node having the specified value and return it. The steps are:

call malloc to create the new node, assigning it to a Node* variable called node.

Assign the value of the int value parameter to node->value.

Assign NULL to left.

Assign NULL to right.

return node.

Node* Min(Node* tree) 

This function returns the node in the tree with the smallest value. The steps are:

Assign tree to a Node* variable called current.

while current->left is not null, set current to current->left.

return current.

Node* Insert(Node* tree, int value) 

This recursive function will insert a new node into the tree and return it. The steps are:

if tree is NULL, call your Create function with the specified value and return the resulting node.

if the specified value is less than tree->left, call Insert with tree->left and the specified value.

else if the specified value is greater than tree->right, call Insert with tree->right and the specified value.

return tree.

void Delete(Node* tree, Node* node) 

This recursive function will delete the specified node from the specified tree. The steps are:

If tree is NULL, return NULL.

if value is less than tree-> value, call Delete with tree->left and value as parameters, and assign the result to tree->left.

else if value is greater than tree->value, call Delete with tree->right and value as parameters, and assign the result to tree->right.

else {

if tree->left is null, assign tree->right to a temp variable, call free(tree), and return temp.

else if tree ->right is null, assign tree->left to a temp variable, call free(tree), and return temp.

declare a Node* min variable, and call your Min function with tree->right as the parameter, assigning the return value to min.

assign min->value to tree->value.

call Delete, passing tree->right and min->right as parameters, and assign the result to tree->right. }

return tree.

Node* Find(Node* tree, int value) 

This recursive function finds the node in the tree with the specified value. The steps are:

if tree is NULL or tree->value equals value, return tree.

if value is less than tree->value, return the result of calling Find using tree->left and value as parameters.

return the result of calling Find using tree->right and value as parameters.

void Print(Node* list) 

Prints the tree in alphabetical order. The steps are:

if list is NULL, return NULL.

call Print using tree>left as the parameter.

print tree->value, followed by a space, to stdout.

call Print using tree>right as the parameter.

8 3 10 6 14 4 7 13