without changing the driver program (main) do the following: Implement the member function clone()which creates a new BST and then copies the original BST to cloned BST by preserving the shape of the original BST. (Hint: use a preorder traversal.) Implement the member function perfectlyEquals() which returns true if both BSTs contain same set of elements and same shape. public BinarySearchTree

without changing the driver program (main) do the following: Implement the member function clone()which creates a new BST and then copies the original BST to cloned BST by preserving the shape of the original BST. (Hint: use a preorder traversal.) Implement the member function perfectlyEquals() which returns true if both BSTs contain same set of elements and same shape. public BinarySearchTree

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter17: Linked Lists

Section: Chapter Questions

Problem 9PE

See similar textbooks

Similar questions

JAVA CODE Learning Objectives: Detailed understanding of the linked list and its implementation. Practice with inorder sorting. Practice with use of Java exceptions. Practice use of generics. You have been provided with java code for SomeList<T> class. This code is for a general linked list implementation where the elements are not ordered. For this assignment you will modify the code provided to create a SortedList<T> class that will maintain elements in a linked list in ascending order and allow the removal of objects from both the front and back. You will be required to add methods for inserting an object in order (InsertInorder) and removing an object from the front or back. You will write a test program, ListTest, that inserts 25 random integers, between 0 and 100, into the linked list resulting in an in-order list. Your code to remove an object must include the exception NoSuchElementException. Demonstrate your code by displaying the ordered linked list and…
A- Declare a self-referential structure for a linked list having one data StudentNode field called GPA (float), and one pointer to StudentNode called next. B- Write a non-recursive function - that counts all the GPAS that are less than or equal to 2 in your linked list starting from the head of the list. Example: If the list is 1.9->2->3.5->4->1.8, the function should return 3. C- Write a recursive function that prints all the GPAS that are higher or equal to 3.5 in your linked list starting from the head of the list. Example: If the list is 1.9->2->3.5->4->1.8, the function should print: 3.5->4.
Write a C++ class called BSTArray with five basic functions for the BST: insert, search, findmin, findmax, and print: 1. int search(x): Find and return the index that stores element x using binary search tree mechanism. Print out all the elements in the search path. You must use the binary tree search algorithm. In other words, do NOT just do a linear search of the array. If the x value is not found, report an error and return -1. 2. int findmax( ): Find and return maximum value in BST. You must use the binary tree search algorithm. In other words, do NOT just perform a linear search of the array. If the tree is empty, return -1. 3. int findmin( ): Find and return minimum value in BST. In other words, do NOT just perform a linear search of the array. If the tree is empty, return -1. 4. void print( ): Print out the BST structure in the form of an array with index. Specifically, print the index of the array and the value stored at that index starting at zero and ending at the capacity of…
PYTHON: Please fix my code to print the correct traversals, especially at the def functions, because I could not print the correct results of the inorder, postorder, and preorder traversals from the user input. #POSTORDERclass Node: def __init__(self, data): self.left = None self.right = None self.data = data # Insert Node def insert(self, data): if self.data: if data < self.data: if self.left is None: self.left = Node(data) else: self.left.insert(data) elif data > self.data: if self.right is None: self.right = Node(data) else: self.right.insert(data) else: self.data = data # Print the Tree def PrintTree(self): if self.left: self.left.PrintTree() print(self.data),…
- the constructor needs to initialize tailPtr to nullptr - insert(): modify it to update prev pointers as well as next pointers. - remove(): modify to update prev pointers as well as next pointers. Add a new public member function to the LinkedList class named reverse() which reverses the items in the list. swap each node’s prev/next pointers, and finally swap headPtr/tailPtr. Demonstrate your function works by creating a sample list of a few entries in main(), printing out the contents of the list, reversing the list, and then printing out the contents of the list again to show that the list has been reversed. Note: your function must actually reverse the items in the doubly-linked list, not just print them out in reverse order! we won't use the copy constructor in this assignment, and as such you aren't required to update the copy constructor to work with a doubly-linked list. @file LinkedList.cpp */ #include "LinkedList.h" // Header file#include <cassert>#include…
Using C languge, implement programmer defined-data types with linked lists. A set of integers may be implemented using a linked list.Implement the following functions given the definition:typedef struct node* nodeptr;typedef struct node{int data;nodeptr next;}Node;typedef Node* Set;Set initialize();- simply initialize to NULLvoid display(Set s);- display on the screen all valid elements of the listSet add(Set s, elem);- simply store elem in the listint contains(Set s, int elem);- search the array elements for the value elemSet getUnion(Set result, Set s1, Set s2);- store in the set result the set resulting from the union of s1 and s2- x is an element of s1 union s2 if x is an element of s1 or x is an element of s2Set intersection(Set result, Set s1, Set s2);- store in the set result the set resulting from the intersection of s1 and s2- x is an element of s1 intersection s2 if x is an element of s1 and x is an element of s2Set difference(Set result, Set s1, Set s2);- store in the set…
Suppose we have class named NumberList that holds a linked list of double values. In this section you will modify the class by adding recursive member functions. The functions will use recursion to traverse the linked list and perform the following operations: • Count the number of nodes in the list. To count the number of nodes in the list by recursion, we introduce two new member functions: numNodes and countNodes. countNodes is a private member function that uses recursion, and numNodes is the public interface that calls it. • Display the value of the list nodes in reverse order. To display the nodes in the list in reverse order, we introduce two new member functions: displayBackwards and showReverse. showReverse is a private member function that uses recursion, and displayBackwards is the public interface that calls it.
In c++, Write a Binary Search Tree for strings datatype, using pointers Besure that it has a method that can Rebalance the tree. See below for driver file Testing requirments: int main() { myBTS BTS1; // Declare/Instanitate an instance of the BTS BTS1.inTree("Fred"); BTS1.inTree("Able"); BTS1.inTree("Tuyet"); BTS1.inTree("Mojo"); BTS1.inTree("Linda"); BTS1.inTree("Leena"); BTS1.inTree("Xoe"); BTS1.inTree("Zohe"); BTS1.inTree("Alfred"); BTS1.inTree("Thanos"); BTS1.inTree("koji"); BTS1.inTree("Hally"); BTS1.inTree("Lee"); BTS1.inTree("Mode"); cout << "Number of names in the tree: " << BTS1.count() << endl; if ( BTS1.verify () ) // Function returns a Boolean value { cout << "BST Verified" <
Write a struct Student that has member variables: (string) first name, (int) age and (double) fee. Write the functions as described in the class for the following purposes.1. Write a c++ function to create a dynamic sorted (in ascending order according to the age)doubly linked list, where the data component of each node is an instance of the structStudent.2. Write a function to insert the instances in the linked list. You also need to write a function to find the spot for insertion of the nodes.3. Write a function to remove the node from the linked list.4. Write a function to count the elements of the linked list.5. Write a function to determine check whether an element belongs to the linked list.6. Write a function to print the linked list (from head node) on the console.7. Write a function to print the linked list (from tail node) on the console. Implement the above functions as follows.Initially, the list must have five nodes that are the instances of the struct whose member…
For this assignment, you need to implement link-based List and derivative ADTs in Java. To complete this, you will need the following: A LinkNode structure or class which will have two attributes - a data attribute and a pointer attribute to the next node. The data attribute of the LinkNode should be the Money class of Lab 1. A Singly Linked List class which will be composed of three attributes - a count attribute, a LinkedNode pointer/reference attribute pointing to the start of the list and a LinkedNode pointer/reference attribute pointing to the end of the list. Since this is a class, make sure all these attributes are private. The attribute names for the Node and Linked List are the words in bold in #1 and #2. For the Linked List, implement the most common linked-list behaviors as explained in class - getters/setters/constructors/destructors for the attributes of the class, (a) create new list, (b) add data, (c) delete data, (d) find data, (e) count of data items in the…
I ASK THIS QUESTION HERE AND YOUR EXPERT SOLVE IT THIS WAY BUT CAN YOU WRITE THE main ( ) FOR THIS CODE Consider the following implementation of the node and doubly linked-list: template <class type>class node{public:type info;node<type> * next;// nextnode<type> * prev;//back }; template <class type>class doubly_linked_list{//data membersprivate:node<type> *head, *tail;int length;public:doubly_linked_list(){head = tail = NULL;length = 0;}bool isEmpty(){ // return (head==NULL);if (head == NULL)return true;elsereturn false;} void Append(type e){node<type> *newnode = new node<type>;newnode->info = e;if (isEmpty()){newnode->next = NULL;newnode->prev = NULL;head = newnode;tail = newnode;}else{tail->next = newnode;newnode->prev = tail;newnode->next = NULL;tail = newnode;}++length; } void Display(){if (isEmpty()) { cout << "The linked list is empty !!!!"; return; }cout << "list elements: ";node<type> *…
A BST is constructed in the usual way using the node definition below. Write a function int child2( bst node t *curr) that returns the number of nodes that have 2 children. typedef struct BST NODE T {int data;struct BST NODE T *left, *right; } bst node t; int child2( bst node t *curr){ }