CS2092D-ASSIGNMENT 7 Solved

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 binary-search-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 with distinct keys (with values in the range [1,106]) and perform the operations insertion, deletion, search, successor, predecessor 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’, ‘c’, ‘r’, ‘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.

•   Successor(T,x) - finds the soccessor of the node x in the BST T and prints the data in the successor node.

•   predecessor(T,x) - finds the predecessor of the node x in the BST T and prints the data in the predecessor node.

•   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’, ‘c’, ‘r’, ‘i’, ‘p’, ‘t’, or ‘e’ followed by at most one integer. The integers, if given, are in the range [1,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 by calling the function INSERT().

•   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 calling the function DELETE().

•   Character ‘s’ is followed by an integer separated by space. This operation is to find the node with this integer as key in T by calling the function SEARCH().

•   Character ‘c’ is followed by an integer separated by space. This operation is to find successor of the node with this integer as key in T by calling the function SUCCESSOR().

•   Character ‘r’ is followed by an integer separated by space. This operation is to find predecessor of the node with this integer as key in T by calling the function PREDECESSOR().

•   Character ‘i’ is to perform inorder traversal of T by calling the function INORDER().

•   Character ‘p’ is to perform preorder traversal of T by calling the function PREORDER().

•   Character ‘t’ is to perform postorder traversal of T by calling the function POSTORDER()

•   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 ‘c’, if the successor is present in T, then print the data in the successor node. If successor is not present in T, then print -1.

•   For option ‘r’, if the predecessor is present in T, then print the data in the predecessor node. If predecessor 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 c 25 c 55 r 45 r 13 i

p t

s 10 s 25 d 55 d 13 d 10 d 25

i

s 25 e

Sample Output :

45

-1

25

-1

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