Question
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
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) ->
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started