CS2092D Assignment #9 Solution

QUESTIONS

1. The Binary Search Tree (BST) data structure supports many of the dynamic-set operations. A BST is organized as a binary tree in which each node is an object that contains a key value. In addition to a key and satellite data, each node contains attributes left, right, and p that point to the nodes corresponding to its left child, its right child, and its parent, respectively. If a child or the parent is missing, the appropriate attribute contains the value NIL. The root node is the only node in the tree whose parent is NIL. The keys in a binary search tree are always stored in such a way as to satisfy the binarysearch-tree property:
• Let x be a node in a binary search tree. If y is a node in the left subtree of x, then
y.key ≤ x.key. If y is a node in the right subtree of x, then y.key ≥ x.key.
Write a program to create a Binary Search Tree T and perform the operations insertion, deletion, search and traversals(inorder, preorder and postorder) on T. Input should be read from console and output should be shown in console. Your program should include the following functions.
• Main() - creates the Binary Search Tree T with T as the root node (which is NIL initially) and repeatedly reads a character ‘a’, ‘d’, ‘s’, ‘i’, ‘p’, ‘t’, or ‘e’ from the console and calls the sub-functions appropriately until character ‘e’ is entered.
• CreateNode(k) creates a new node with key value k and returns a pointer to the new node. All the pointer attributes of the new node are set to NIL.
• Insert(T,x) - inserts the node x into the BST T.
Note: The caller of this function is assumed to create the node x using the CreateNode() function.
• Delete(T,x) - deletes the node x from the BST T.
Note: The caller of this function is assumed to invoke Search() function to locate the node x.
• Search(T,k) - searches for a node with key k in T, and returns a pointer to a node with key k if one exists; otherwise, it returns NIL.
• Inorder(T) - performs recursive inorder traversal of the BST T and prints the data in the nodes of T in inorder.
• Preorder(T) performs recursive preorder traversal of the BST T and prints the data in the nodes of T in preorder.
• Postorder(T) performs recursive postorder traversal of the BST T and prints the data in the nodes of T in postorder.
Input format:
• Each line contains a character from ‘a’, ‘d’, ‘s’, ‘i’, ‘p’, ‘t’, or ‘e’ followed by at most one integer. The integers, if given, are in the range [−106,106].
• Character ‘a’ is followed by an integer separated by space. In this operation, a node with this integer as key is created and inserted into T.
• Character ‘d’ is followed by an integer separated by space. In this operation, the node with this integer as key is deleted from T and the deleted node’s key is printed.
• Character ‘s’ is followed by an integer separated by space. This operation is to find the node with this integer as key in T.
• Character ‘i’ is to perform inorder traversal of T.
• Character ‘p’ is to perform preorder traversal of T.
• Character ‘t’ is to perform postorder traversal of T.
• Character ‘e’ is to ‘exit’ from the program.
Output Format: • The output (if any) of each command should be printed on a separate line.
• For option ‘d’, print the deleted node’s key. If a node with the input key is not present in T, then print -1.
• For option ‘s’, if the key is present in T, then print 1. If key is not present in T, then print -1.
• For option ‘i’, print the data in the nodes of T obtained from inorder traversal.
• For option ‘p’, print the data in the nodes of T obtained from preorder traversal.
• For option ‘t’, print the data in the nodes of T obtained from postorder traversal.
Sample Input :
a 25 a 13 a 50 a 45 a 55 a 18
i
p
t
s 10s 25 d 55 d 13 d 10 d 25 i
s 25
e
Sample Output :
13 18 25 45 50 55
25 13 18 50 45 55
18 13 45 55 50 25
-1
1
55
13
-1
25
18 45 50
-1
2. Suppose in a car show room, the car details like model number, model name and price are stored in a BST. Modify the Binary Search Tree T in Qn No.1 so as to store for each car model number, model name and price. Assume that model number of a car is unique and the car details are organised in the BST, based on the value of model number of a car. Write a function Modify(n, p) that modifies the price of a car with model number as n with new price p. Declare model number and price as integers and model name as string.
Input format:
• Each line contains a character from ‘a’, ‘d’, ‘s’, ‘i’, ‘m’, or ‘e’ followed by the arguments required for the corresponding operation.
• Character ‘a’ is followed by an integer n, a string s and an integer p separated by space. In this operation, a new node with model number as n, model name as s and price as p is inserted to T.
• Character ‘d’ is to delete the node with next integer as model number from T. Character ‘d’ and integer are separated by space.
• Character ‘s’ is followed by an integer separated by space. This operation is to find the car details with this integer as model number in T.
• Character ‘m’ is followed by two integers separated by space. This operation is to modify the price of a car with first integer as model number into second integer as new price in T.
• Character ‘i’ is to perform inorder traversal of T.
• Character ‘e’ is to ‘exit’ from the program.
Output Format:
• The output (if any) of each command should be printed on a separate line.
• For options ‘d’, print the deleted car’s details in the order model number, model name, price separated by space. If a node with the input key is not present in T, then print -1.
• For option ‘s’, if the key is present in T, then print all the details of that car in the order model number, model name, price separated by space. If key is not present in T, then print -1.
• For option ‘i’, print the data in the nodes of T obtained from inorder traversal. Each car’s details are written on a separate line in the order model number, model name, price separated by space.
i
s 2010 s 2000 d 1999 d 1990 d 2010 d 2000
i
Sample Output :
1990 xca 130000
1999 fgha 550000
2000 abv 250000 2014 vta 500000
-1
2000 abv 250000
1999 fgha 550000
1990 xca 130000
-1
2000 abv 250000 2014 vta 500000
-1