Question

In: Computer Science

Please in C++ I don't have the binarySearchTree (Carrano) Implement the code of the BinarySeachTree Class...

Please in C++ I don't have the binarySearchTree

(Carrano) Implement the code of the BinarySeachTree Class to solve: 
(Gaddis) Programming Challenger 3. Car Class p. 802 Ch. 13
• Implement a menu of options
• Add a motor vehicle to the tree
• Remove a motor vehicle to the tree
• Search by vehicle model
• Vehicle Inventory Updates
• Take one of the tours to verify the contents of the tree.

Car Class
Write a class named Car that has the following member variables:

  • yearModel. An int that holds the car’s year model.

  • make. A string that holds the make of the car.

  • speed. An int that holds the car’s current speed.

  • In addition, the class should have the following constructor and other member functions.

  • Constructor. The constructor should accept the car’s year model and make as argu- ments. These values should be assigned to the object’s yearModel and make member variables. The constructor should also assign 0 to the speed member variables.

  • Accessor. Appropriate accessor functions to get the values stored in an object’s yearModel, make, and speed member variables.

  • accelerate. The accelerate function should add 5 to the speed member variable each time it is called.

  • brake. The brake function should subtract 5 from the speed member variable each time it is called.

    Demonstrate the class in a program that creates a Car object, and then calls the accelerate function five times. After each call to the accelerate function, get the current speed of the car and display it. Then, call the brake function five times. After each call to the brake function, get the current speed of the car and display it.

Solutions

Expert Solution

#include<iostream>
#include <stdlib.h>
using namespace std;
class Car {
public:
    int yearModel;
    string make;
    int speed;
    //default constructor
    Car()
    {
        this->yearModel = 0;
        this->make = "";
        this->speed = 0;
    }
    //constructor
    Car(int yearModel, string make) {
        this->yearModel = yearModel;
        this->make = make;
        this->speed = 0;
    }
    //accessor methods
    int getYearModel() {
        return this->yearModel;
    }
    string getMake() {
        return this->make;
    }
    int getSpeed() {
        return this->speed;
    }
    //accelerate method
    void accelerate() {
        this->speed = this->speed + 5;
    }
    //break method
    void brake() {
        this->speed = this->speed - 5;
    }
};
//to create a node for bst:it contains car objects and left and right pointers
struct node {
    Car car;
    struct node* left, * right;
    node(Car x)
    {
        car = x;
        left = right = NULL;
    }
};
// Create a node
struct node* newNode(Car car) {
    //struct node* temp = (struct node*)malloc(sizeof(struct node));
    struct node* temp = new node(car);
    temp->car = car;
    temp->left = temp->right = NULL;
    return temp;
}
//to insert a car vehicle in bst based on its yearModel number
struct node* insert(struct node* node, Car car) {
    // Return a new node if the tree is empty
    if (node == NULL)
        return newNode(car);

    // Traverse to the right place and insert the node
    if (car.yearModel < node->car.yearModel)
        node->left = insert(node->left, car);
    else
        node->right = insert(node->right, car);
    return node;
}
// Find the inorder successor
struct node* minValueNode(struct node* node) {
    struct node* current = node;

    // Find the leftmost leaf
    while (current && current->left != NULL)
        current = current->left;

    return current;
}
//to remove the car vehicle from bst based on given yearModel
struct node* deleteNode(struct node* root, int yearModel) {
    // Return if the tree is empty
    if (root == NULL)
        return root;

    // Find the node to be deleted
    if (yearModel < root->car.yearModel)
        root->left = deleteNode(root->left, yearModel);
    else if (yearModel > root->car.yearModel)
        root->right = deleteNode(root->right, yearModel);
    else {
        // If the node is with only one child or no child
        if (root->left == NULL) {
            struct node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            struct node* temp = root->left;
            free(root);
            return temp;
        }
        // If the node has two children
        struct node* temp = minValueNode(root->right);

        // Place the inorder successor in position of the node to be deleted
        root->car.yearModel = temp->car.yearModel;

        // Delete the inorder successor
        root->right = deleteNode(root->right, temp->car.yearModel);
    }
    return root;
}
// search a node based on given yearModel
bool search(struct node* root, int yearModel) {
    // Return if the tree is empty
    if (root == NULL)
        return false;
    if (root->car.yearModel == yearModel) {
        return true;
    }
    // Find the node to be search
    if (yearModel < root->car.yearModel)
        search(root->left, yearModel);
    else
        search(root->right, yearModel);
}
//update the vehicle based on given yearModel
bool update(struct node* root, int yearModel, int updatedYearModel) {
    // Return if the tree is empty
    if (root == NULL)
        return false;
    if (root->car.yearModel == yearModel) {
        root->car.yearModel = updatedYearModel;
        return true;
    }
    // Find the node to be update
    if (yearModel < root->car.yearModel)
        update(root->left, yearModel, updatedYearModel);
    else
        update(root->right, yearModel, updatedYearModel);
}
// Inorder Traversal of bst
void printBST(struct node* root) {
    if (root != NULL) {
        //visiting
        cout << root->car.yearModel << " -> " << root->car.make << " -> " << root->car.speed << endl;
        // Traverse left
        printBST(root->left);
        // Traverse right
        printBST(root->right);
    }
}
//to add multiple vehicle in bst...
struct node *add(struct node* root){
    //creating multiple car objects
    Car car1(2004, "Honda");
    Car car2(2001, "Honda");
    Car car3(1998, "Honda");
    Car car4(2005, "Honda");
    Car car5(2000, "Honda");
    Car car6(1997, "Honda");
    Car car7(2007, "Honda");
    Car car8(2008, "Honda");
    //inserting or adding car objects into the bst
    root = insert(root, car1);
    root = insert(root, car2);
    root = insert(root, car3);
    root = insert(root, car4);
    root = insert(root, car5);
    root = insert(root, car6);
    root = insert(root, car7);
    root = insert(root, car8);

    return root;
}
int main() {

    Car car1(2020, "OD");
    int i,choice=0,year,year1;
    for (i = 0; i < 5; i++) {
        car1.accelerate();
        cout << "The current speed of car is :" << car1.getSpeed() << endl;
    }
    for (i = 0; i < 5; i++) {
        car1.brake();
        cout << "The current speed of car is :" << car1.getSpeed() << endl;
    }
    
    
    struct node* root = NULL;
    
    do{
        cout<<"Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit"<<endl;
        cout<<"Please enter your choice "<<endl;
        cin>>choice;
        switch(choice){
            case 1:
                root=add(root);
                break;
            case 2:
                cout<<"Please enter the yearModel of car to remove "<<endl;
                cin>>year;
                cout << "removing vehicle " << endl;
                root=deleteNode(root,year);
                break;
            case 3:
                cout<<"Please enter the yearModel of car to search "<<endl;
                cin>>year;
                cout << "Searching the vehicle with yearModel "<<year << endl;
                if(search(root,year))
                    cout << "Found" << endl;
                else
                    cout << "Not found" << endl;
                break;
            case 4:
                cout<<"Please enter the yearModel of car to update "<<endl;
                cin>>year;
                cout<<"Please enter the yearModel of car to update with "<<endl;
                cin>>year1;
                if(update(root,year,year1))
                    cout << "updated" << endl;
                else
                    cout << "Not found" << endl;
                break;
            case 5:
                cout << "visiting or traversal: " << endl;
                printBST(root);
                break;
            case 6:
                break;
            default:
                cout<<"Please enter the valid choice "<<endl;
            
        }
    }while(choice!=6);

}

Sample input and output of above c++ code:

The current speed of car is :5
The current speed of car is :10
The current speed of car is :15
The current speed of car is :20
The current speed of car is :25
The current speed of car is :20
The current speed of car is :15
The current speed of car is :10
The current speed of car is :5
The current speed of car is :0
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
1
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
5
visiting or traversal:
2004 -> Honda -> 0
2001 -> Honda -> 0
1998 -> Honda -> 0
1997 -> Honda -> 0
2000 -> Honda -> 0
2005 -> Honda -> 0
2007 -> Honda -> 0
2008 -> Honda -> 0
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
3
Please enter the yearModel of car to search
2007
Searching the vehicle with yearModel 2007
Found
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
3
Please enter the yearModel of car to search
2020
Searching the vehicle with yearModel 2020
Not found
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
4
Please enter the yearModel of car to update
2002
Please enter the yearModel of car to update with
2004
Not found
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
4
Please enter the yearModel of car to update
1998
Please enter the yearModel of car to update with
1999
updated
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
5
visiting or traversal:
2004 -> Honda -> 0
2001 -> Honda -> 0
1999 -> Honda -> 0
1997 -> Honda -> 0
2000 -> Honda -> 0
2005 -> Honda -> 0
2007 -> Honda -> 0
2008 -> Honda -> 0
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
2
Please enter the yearModel of car to remove
2000
removing vehicle
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
5
visiting or traversal:
2004 -> Honda -> 0
2001 -> Honda -> 0
1999 -> Honda -> 0
1997 -> Honda -> 0
2005 -> Honda -> 0
2007 -> Honda -> 0
2008 -> Honda -> 0
Please choose: 1 for adding new vehicle. 2 for removing a vehicle. 3 for Searching a vehicle. 4 for Updating a vehicle. 5 for visiting or printing bst. 6 for quit
Please enter your choice
6


Code Screen shots:

Code explainations:

As per the requirments I have crated a class Car with required info.

Now I have created a structure to make binary search tree with car objects.

While adding or inserting a car object in bst i have used the car yearModel number.

While searching a vehicle in bst i also used the yearModel number.

While updating a vehicle in bst I used yearModel number of that vehicle and updated with given yearModel number..

While removing a vehicle in bst I used yearModel number of that vehicle and removed it from bst

for making a tour to visit each vehicle of bst i have implemented inorder traversal of bst.


Related Solutions

8.16 Implement code for the BSTRemove operation. Implement node removal functionality for the BinarySearchTree. The base...
8.16 Implement code for the BSTRemove operation. Implement node removal functionality for the BinarySearchTree. The base remove function has already been implemented for you, but you need to fill in the implementation for Case 1, Case 2, and Case 3 of the algorithm as described in the lecture notes. Note, the pseudo-code in the lecture should work with minimal modifications. However, it would be a good learning exercise to try to implement them from scratch if you have time. //C++...
(Java) Implement a RightThreadTree class as an extension of a BinarySearchTree A right-threaded tree is a...
(Java) Implement a RightThreadTree class as an extension of a BinarySearchTree A right-threaded tree is a binary search tree in which each right link that would normally be null is a "thread" that links that node to its inorder successor. The thread enables nonrecursive algorithms to be written for search and inorder traversals that are more efficient than recursive ones. Implement a RightThreadTree class as an extension of a BinarySearchTree. You will also need an RTNode that extends the Node...
Write pseudo code for the following parts of class BinarySearchTree: a) find(x) b) contains(x) c) add(x)...
Write pseudo code for the following parts of class BinarySearchTree: a) find(x) b) contains(x) c) add(x) d) remove(x) e) splice(x) f) min() g) max() h) pred() i) succ() j) floor() k) ceil()
IN JAVA. I have the following code (please also implement the Tester to test the methods...
IN JAVA. I have the following code (please also implement the Tester to test the methods ) And I need to add a method called public int remove() that should remove the first integer of the array and return it at the dame time saving the first integer and bring down all other elements. After it should decrease the size of the array, and after return and save the integer. package ourVector; import java.util.Scanner; public class ourVector { private int[]...
I have a homework class, but I don't really understand anything and I have to submit...
I have a homework class, but I don't really understand anything and I have to submit my homework next week. Homework must be written in C ++ program language. Can someone help me please... Working with classes (everything written below is one task): Define a class Date that contains integer variables for day, month, and year. 1.1. Create the necessary methods for the class: set, get, default constructor, constructor with arguments. 1.2. Create a method that calculates the number of...
I have code for an AVL tree. I Have have a node class and tree class....
I have code for an AVL tree. I Have have a node class and tree class. I need a  node object that refrences the root(top) of the tree. my current code throws NullPointerException when I try to access the root properties. here is the important snippets of my code, it is in java. public class Node { private Node left=null,right=null; public int height=1; private String Item; private int balance=0; Node(String item) { this.Item=item; } } -------------------------------------------------- public class AVLTree { public...
This code is an expression of cp command in c language. But I don't understand this...
This code is an expression of cp command in c language. But I don't understand this code very well. Please explain in notes one by one.(in detail) #include<stdio.h> #include<stdlib.h> #include<fcntl.h> #include<errno.h> #include<stdlib.h> #include<unistd.h> #include<sys/types.h> #include<sys/stat.h> #include<unistd.h> int main(int argc, char *argv[]) { char ch; int src, dst; struct stat st; if(argc != 3) { printf("argument error \n"); printf("usage: ./a.out src dest \n"); exit(0); } if (stat(argv[1], &st) == -1) { perror("stat : "); exit(-1); } src = open(argv[1], O_RDONLY); if(src...
This code is an expression of cp command in c language. But I don't understand this...
This code is an expression of cp command in c language. But I don't understand this code very well. Please explain in notes one by one. #define SIZE 1024 #include<string.h> #include<stdio.h> #include<sys/types.h> #include<fcntl.h> #include<unistd.h> #include<stdlib.h> #include<sys/stat.h> int main(int argc, char *argv[]){ if(argc != 3){ perror("argument 부족\n"); exit(0); } struct stat frstatbuf; FILE* fr = fopen(argv[1], "r"); if(fr == NULL){ perror("read file 읽기 오류\n"); exit(0); } int frfd = fileno(fr); fstat(frfd, &frstatbuf); FILE* fw=fopen(argv[2], "w+"); int fwfd=fileno(fw); fchmod(fwfd,frstatbuf.st_mode&(S_IRWXU|S_IRWXG|S_IRWXO)); char buf[1024]; while(1){...
C++ Please Fill in for the functions for the code below. The functions will implement an...
C++ Please Fill in for the functions for the code below. The functions will implement an integer list using dynamic array ONLY (an array that can grow and shrink as needed, uses a pointer an size of array). Additional public helper functions or private members/functions can be used. The List class will be instantiated via a pointer and called similar to the code below: class List { public: // Default Constructor List() {// ... } // Push integer n onto...
C++ Please Fill in for the functions for the code below. The functions will implement an...
C++ Please Fill in for the functions for the code below. The functions will implement an integer stack using deques ONLY. It is possible to use only one deque but using two deques also works. Additional public helper functions or private members/functions can be used. The Stack class will be instantiated via a pointer and called as shown below: Stack *ptr = new Stack(); ptr->push(value); int pop1 = ptr->pop(); int pop2 = ptr->pop(); bool isEmpty = ptr->empty(); class Stack{     public:...
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT