DO NOT COPY other answers answers! They are wrong! C++ Code must be written as stated in the Instructions. Should be able
Posted: Fri Jul 08, 2022 6:40 am
DO NOT COPY other answers answers! They are wrong!
C++ Code must be written as stated in the Instructions.
Should be able to run a makefile using the followingcommands:
User:~$ ~/p03/p03 input.dat output.dat
The task of this project is to implement a binary search tree with lazy deletion in C++. We can assume the data type of the elements is int. The class structures are specified by the following UML class diagram. Please follow the specification to name your classes, identifiers and functions. You may also add helper functions and additional fields as you see fit. LazyBinarySearch Tree - root: TreeNode* + insert(key: int): bool + remove(key: int): bool + findMin(): int + findMax(): int + constains(key: int): bool + print(): string + height(): int + size(): int TreeNode + key: int + left: TreeNode* + right: TreeNode* + deleted: bool insert should insert a new element as a leaf node. The valid set of keys is all integers in the range [1,99]. If the new element would be a duplicate of a non-deleted element already in the tree, then insert should do nothing. However, if the new element is not a duplicate of a non-deleted element, but is a duplicate of a deleted element, then insert should "undelete" the deleted element in-place rather than physically inserting a new copy of the element. The return value of insert should indicate whether insert logically (as opposed to physically) inserted a new element. remove should not physically remove an element from the tree. Rather, it should mark the specified element as logically deleted. If the specified element is not in the tree or is already marked as deleted, then remove should do nothing. The return value of remove should indicate whether remove logically deleted an element. findMin should return the value of the minimum non-deleted element, or -1 if none exists. findMax should return the value of the maximum non-deleted element, or -1 if none exists. contains should return whether the given element both exists in the tree and is non-deleted. print should perform a pre-order traversal of the tree and print the value of each element, including elements marked as deleted. However, elements that are marked as deleted should be preceded by a single asterisk (*). Every pair of adjacent elements should be separated by whitespace in the printing, but no whitespace should occur between an asterisk and the element
with which it is associated. Leading and trailing whitespace is tolerable, but it will be ignored. (no additional messages should be printed, either). An example of the output is as follows: 45 30 25 47 50 *60 height should return the height of the tree, including "deleted" elements. size should return the count of elements in the tree, including "deleted" ones. The valid set of keys is all integers in the range [1,99]. Every function that accepts a key argument should show an appropriate message (e.g., illegal argument: value not in range) if and only if the argument is invalid. Along with the LazyBinary SeacrTree class, please also prepare another source file that has a main function. You should name this file as p03.cpp, and follow existing examples to create the makefile, through which the name of the executable should be p03. Please note: this time we don't have generic types, so in your makefile you may need to build an object file for each of your LazyBinary SeacrTree class and TreeNode class. This main function will take two command line arguments. The first argument will be the input file name and second will be output file name. The input file will be given to the program and the output file will be generated by the program. This main function will create an instance of LazyBinary Search Tree and do the operations specified in the input file. The format of the input file (e.g. input.dat) will be similar as: insert: 98 insert:67 insert:55 insert:45 print remove: 84 remove: 45 contains:45 findMin findMax print height size insert: 84 insert: 32 insert: 32 print findMin insert: 980 insert hiha
{insert and remove will be followed by ":" semicolon and the key to be inserted/removed. You have to check for validity of the key as well as the line in the file. } The corresponding correct output file (e.g., output.dat) will be similar as: true true true true 98 67 55 45 false true false 55 98 98 67 55 * 45 3 4 true true false 98 67 55 *45 32 84 32 Error: insert (illegal argument: not in range) Error: insert (no key) Error: hiha (invalid command)
- Do Not Copy Other Chegg Answers They Are Wrong C Code Must Be Written As Stated In The Instructions Should Be Able 1 (262.92 KiB) Viewed 46 times
- Do Not Copy Other Chegg Answers They Are Wrong C Code Must Be Written As Stated In The Instructions Should Be Able 2 (199.65 KiB) Viewed 46 times
Should be able to run a makefile using the followingcommands:
User:~$ ~/p03/p03 input.dat output.dat
The task of this project is to implement a binary search tree with lazy deletion in C++. We can assume the data type of the elements is int. The class structures are specified by the following UML class diagram. Please follow the specification to name your classes, identifiers and functions. You may also add helper functions and additional fields as you see fit. LazyBinarySearch Tree - root: TreeNode* + insert(key: int): bool + remove(key: int): bool + findMin(): int + findMax(): int + constains(key: int): bool + print(): string + height(): int + size(): int TreeNode + key: int + left: TreeNode* + right: TreeNode* + deleted: bool insert should insert a new element as a leaf node. The valid set of keys is all integers in the range [1,99]. If the new element would be a duplicate of a non-deleted element already in the tree, then insert should do nothing. However, if the new element is not a duplicate of a non-deleted element, but is a duplicate of a deleted element, then insert should "undelete" the deleted element in-place rather than physically inserting a new copy of the element. The return value of insert should indicate whether insert logically (as opposed to physically) inserted a new element. remove should not physically remove an element from the tree. Rather, it should mark the specified element as logically deleted. If the specified element is not in the tree or is already marked as deleted, then remove should do nothing. The return value of remove should indicate whether remove logically deleted an element. findMin should return the value of the minimum non-deleted element, or -1 if none exists. findMax should return the value of the maximum non-deleted element, or -1 if none exists. contains should return whether the given element both exists in the tree and is non-deleted. print should perform a pre-order traversal of the tree and print the value of each element, including elements marked as deleted. However, elements that are marked as deleted should be preceded by a single asterisk (*). Every pair of adjacent elements should be separated by whitespace in the printing, but no whitespace should occur between an asterisk and the element
with which it is associated. Leading and trailing whitespace is tolerable, but it will be ignored. (no additional messages should be printed, either). An example of the output is as follows: 45 30 25 47 50 *60 height should return the height of the tree, including "deleted" elements. size should return the count of elements in the tree, including "deleted" ones. The valid set of keys is all integers in the range [1,99]. Every function that accepts a key argument should show an appropriate message (e.g., illegal argument: value not in range) if and only if the argument is invalid. Along with the LazyBinary SeacrTree class, please also prepare another source file that has a main function. You should name this file as p03.cpp, and follow existing examples to create the makefile, through which the name of the executable should be p03. Please note: this time we don't have generic types, so in your makefile you may need to build an object file for each of your LazyBinary SeacrTree class and TreeNode class. This main function will take two command line arguments. The first argument will be the input file name and second will be output file name. The input file will be given to the program and the output file will be generated by the program. This main function will create an instance of LazyBinary Search Tree and do the operations specified in the input file. The format of the input file (e.g. input.dat) will be similar as: insert: 98 insert:67 insert:55 insert:45 print remove: 84 remove: 45 contains:45 findMin findMax print height size insert: 84 insert: 32 insert: 32 print findMin insert: 980 insert hiha
{insert and remove will be followed by ":" semicolon and the key to be inserted/removed. You have to check for validity of the key as well as the line in the file. } The corresponding correct output file (e.g., output.dat) will be similar as: true true true true 98 67 55 45 false true false 55 98 98 67 55 * 45 3 4 true true false 98 67 55 *45 32 84 32 Error: insert (illegal argument: not in range) Error: insert (no key) Error: hiha (invalid command)