Question posted as a pdf file , too large to paste with tables
1 COMP 2611 – Data Structures Assignment 2 Date Due: Tuesday November 10, 2020 @ 11.55 pm Overview This assignment requires you to write several functions for a binary tree and a binary search tree (BST). You are also required to write a menu-based application to test these functions. The application reads words from a file and stores them in a BST. You are supplied with a Dev C++ project, Assignment2.dev, containing various .h and .cpp files. You do not have to modify the project. The code for this assignment must be written in the BinaryTree.cpp, BinarySearchTree.cpp, and Assignment2.cpp files. There is no need to modify the code in the other files supplied. Definition of a Node in the Binary Tree (In NodeTypes.h) Each node in the binary tree (and by extension, the BST tree) stores a word from the file (or entered by the user) and the number of times the word occurs in the file or was entered by the user. BTNode is defined as follows: struct BTNode { string data; // word from file or entered by user int count; // number of occurrences of the word BTNode * left; // address of left child, if it exists BTNode * right; // address of right child, if it exists BTNode * parent; // address of parent (all nodes except the root) }; 2 Binary Tree Functions (to be written in BinaryTree.cpp) Return Type Prototype of Function and Description BTNode * createBTNode (BTNode * parent, string data) Creates in a node in the binary tree. The code is almost similar to what was covered in the labs. int height(BTNode * root) Returns the height of the binary tree. The height of the tree is the longest path from the root node to any leaf node in the tree. bool isEmptyTree(BTNode * root) Returns true if the binary tree is empty and false, otherwise. bool isEqual(BTNode * root1, BTNode * root2) Returns true if the two binary trees supplied as parameters are identical. Two binary trees are identical if they contain the same values in exactly the same positions in each tree. void preOrder (BTNode * root) Outputs the pre-order traversal of the binary tree. The code must be non-recursive. int weight(BTNode * root) Returns the weight of the binary tree. The weight of a binary tree is the amount of leaves in the tree. int width(BTNode * root) Returns the width of the binary tree. The width of a binary tree is the maximum number of nodes at any level of the tree. The Programming Guidelines section explains how to find the amount of nodes in a given level. 3 Binary Search Tree Functions (to be written in BinarySearchTree.cpp) Return Type Prototype of Function and Description BTNode * ceiling(BTNode * root, string key) Returns the address of the node with the smallest key in the BST that is greater than or equal to key, regardless if key is present in the BST. Returns NULL if there is no such node. BTNode * deleteNode(BTNode * root, string key) Removes the node containing the specified key (if key is present in the BST). Returns the address of the root of the tree without the deleted node. BTNode * floor(BTNode * root, string key) Returns the address of the node with the biggest key in the BST that is less than or equal to key, regardless if key is present in the BST. Returns NULL if there is no such node. BTNode * inOrderPredecessor (BTNode * node) Returns the in-order predecessor of the node supplied as a parameter. Returns NULL if the node is NULL or there is no in-order predecessor of the node. bool insert(BTNode * root, string key) If key is not already present, inserts key into the BST and returns true. If key is present, updates the count of key and returns false. Functions Provided in BinaryTree.cpp int moment (BTNode * root); // finds the moment of the tree void inOrder (BTNode * root); // performs non-recursive in-order traversal void levelOrder (BTNode * root); // performs level-order traversal Functions Provided in BinarySearchTree.cpp BTNode * recTreeSearch (BTNode * root, string key); // performs a recursive search for key in the BST BTNode * treeMinimum (BTNode * root); // finds the smallest node in the BST BTNode * treeMaximum (BTNode * root); // finds the largest node in the BST BTNode * inOrderSuccessor (BTNode * node); // finds the inorder successor of a node in the BST 4 Application Functions (to be written in Assignment2.cpp) Write an application which reads the words from a file and stores them in a BST. The application provides a menu from which various operations are performed. The operations are performed by calling one or more of the binary tree or BST functions written in the two previous sections. The following is the menu that must be displayed: Binary Search Tree (BST) --------------------------------------------- 1. Create BST from File 2. Add Word to BST 3. Delete Word from BST 4. Search for Word in BST 5. Traverse BST 6. What Comes Before Word in BST? 7. What Comes After Word in BST? 8. Compare BSTs 9. Statistics Q. Quit Please enter an option: When an option is selected, the appropriate action must be taken, after which the menu is re- displayed. The following is a description of each option. 1. When this option is selected, the program should allow the user to specify the name of the file containing the words: Please enter the name of the file or M (Menu): If the user enters “M” control should return to the main menu and no BST should be created; if a BST was previously created, this will continue to be the “active” or “current” BST. Otherwise, your program should read the appropriate file and create the BST. The Programming Guidelines section explains how to open a file using a string entered by the user. Several data files will be provided for you to test your application, e.g., Words1.txt. 2. When this option is selected, the program should request the user to specify a word. Please enter the word to insert in the BST or M (Menu): If the user chooses “M”, control should return to the main menu. Otherwise, your program should insert the word into the BST. If the word is already present, its count is updated. The BST should not contain duplicate words. 3. When this option is selected, the program should request the user to specify the word to be deleted. Please enter the word to delete from the BST or M (Menu): If the user chooses “M”, control should return to the main menu. Otherwise, your program should delete the word from the BST, if it is present. 5 4. When this option is selected, the program should prompt for a word and determine if it is present in the BST. Please enter a word to search for or M (Menu): If the user chooses “M”, control should return to the main menu. If the word is not present, display an appropriate message. If it is present, the amount of times it occurred in the file (and user input) must be displayed. 5. When this option is selected, the program should display a pre-order traversal and an in-order traversal of the BST. Use any of the in-order traversals previously discussed. 6. When this option is selected, the program should prompt for a word and display the word that comes immediately before it in the BST. If there is no word that comes before it, display an appropriate message. The word entered by the user may not be present in the BST. 7. When this option is selected, the program should prompt for a word and display the word that comes immediately after it in the BST. If there is no word that comes after it, display an appropriate message. The word entered by the user may not be present in the BST. 8. When this option is selected, the program should allow the user to specify the name of a file from which a new BST will be created; this BST will be compared with the current BST to determine if they are identical. The program should open the file and use the contents of the file to create a BST. Please enter the name of the file to create the BST or M (Menu): If the user chooses “M”, control should return to the main menu. Otherwise, your program should read the data from the file, create the second BST, and check if it is identical to the current BST. Note that the current BST can only be created via Option 1. Data files, e.g., Compare1.txt, will be provided for you to test Option 8. 9. When this option is selected, the program should display the following information about the BST: (1) The number of nodes in the tree. (2) The height of the tree. (3) The width of the tree. (4) The weight of the tree. (5) The smallest word and the biggest word (in alphabetical order) stored in the tree. 6 Programming Guidelines Opening a File Where the Name of the File is Specified by the User To open