How would I create this program using C?

For this assignment you will build an unbalanced binary search tree from an input file of unknown

size. The input file will consist of (x,y) pairs in the following format:

input.txt

22 10

4 9

10 30

59 42

19 28

8 57

32 64

5 23

6 9

9 8

...

You will build the binary search tree based on the x values of the list. You will also allow users to delete

nodes from your tree. These deletions will also be based on the x values.

Note that you are not required to use recursion to accomplish any of these tasks, but using recursion

makes all of them much easier.

Include the following structure definition at the top of your program:

typedef struct Node{

int x;

int y;

struct Node *left;

struct Node *right;

}Node;

Implement the following functions:

Node* import_tree(char* filename);

The import_tree function takes the file name as input. It returns the root of the newly assembled binary

search tree. You will use this function to create a binary search tree based on the x values of the (x,y)

pairs in the input file. You will call add_node within this function.

Node* add_node(Node *root, Node *new_node);

The add_node function takes the root of the tree and a new_node as inputs. It returns the root of the tree.

The function simply inserts the new node into the proper position within the tree. You should not malloc

within this function. The new node should already have allocated space and valid x and y values before it

is passed to this function. When you create new nodes, remember that the left and right members need to

be set to NULL.

void inorder(Node *root);

The inorder function takes the root of the tree as input and returns nothing. It prints out the tree in inorder

fashion.

void preorder(Node *root);

The preorder function takes the root of the tree as input and returns nothing. It prints out the tree in

preorder fashion

void free_tree(Node *root);

The free_tree function takes the root of the tree as input and returns nothing. It frees every node of the

tree. Remember that you can use val to check for memory leaks. An example of using val is shown below.

Node* delete_node(Node* root, int key);

The delete_node function takes the root of the tree and an x value to remove from the tree as inputs. The

function should be able to delete a node from any part of the tree. If the function is going to delete a node

with children, then the tree will need to be reshaped slightly to accommodate that change. Remember that

you can use your resources (class notes, websites, etc) to help you finish the lab. We will talk briefly

about the process for deletion before class.

int main( int argc, char **argv)

The main function takes the input filename as the single command line argument. You should error check

to ensure that the user enters the correct number of arguments. After error checking, you should call

import_tree

to create a tree from your input file. You should then call

inorder

to print the tree. After

printing, allow the user to delete multiple nodes from the tree. Make sure to error check their input. You

will need to call

delete_node

within some sort of while loop to accomplish this. After the user is done

deleting nodes, use

inorder

and

preorder

to print off the list again. Then call

free_tree

to free all of your

remaining memory.

You can check for memory leaks using the val command. The val command is a wrapper around a

program called Valgrind. After you compile, you can use the val command in the following way:

val ./a.out input.txt

Bonus

For the 5 bonus points write a function to balance the unbalanced binary search tree. You can use

whatever method you want to accomplish this. No output is required.

Sample Outputs

Characters in bold case are inputs from user.

[kpsgf7@tc-m610-login-node623 lab7]$

./a.out

IMPROPER NUMBER OF INPUT ARGUMENTS

./a.out

[kpsgf7@tc-m610-login-node623 lab7]$

./a.out input.txt

(4, 9) -> (5, 4) -> (7, 8) -> (8, 5) -> (21, 30) -> (25, 20) ->

(32, 40) -> (34, 78) -> (58, 43) -> (63, 10) -> (65, 22) ->

Please enter an x value to be deleted from the tree. The number

must be greater than zero:

-1

Please enter an x value to be deleted from the tree. The number

must be greater than zero:

-1

Please enter an x value to be deleted from the tree. The number

must be greater than zero:

-1

Please enter an x value to be deleted from the tree. The number

must be greater than zero:

8

Would you like to delete another node? Enter -1 to quit:

3

Please enter an x value to be deleted from the tree. The number

must be greater than zero:

58

Would you like to delete another node? Enter -1 to quit:

-1

POST DELETION INORDER

(4, 9) -> (5, 4) -> (7, 8) -> (21, 30) -> (25, 20) -> (32, 40)

-> (34, 78) -> (63, 10) -> (65, 22) ->

POST DELETION PREORDER

(4, 9) -> (7, 8) -> (5, 4) -> (21, 30) -> (34, 78) -> (65, 22)

-> (63, 10) -> (32, 40) -> (25, 20) ->