Implementing the tree ADT functions. Be sure do error inputs. #include \"tree_he

ID: 3866910 • Letter: I

Question

Implementing the tree ADT functions. Be sure do error inputs.

#include "tree_head.hpp"

#include <iostream>

using namespace std;

int main()

{

Tree t;

t.push(4);

t.push(2);

t.push(1);

t.push(3);

t.push(6);

t.push(5);

cout<<"t is : "<<endl;

t.print();

Tree t3(t);

t3.push(7);

cout<<"t is : "<<endl;

t.print();

cout<<"t3 is : "<<endl;

t3.print();

Tree t2;

t2.push(2);

t2.push(1);

t2.push(3);

t2 = t;

t2.push(8);

t2.push(9);

t2.push(11);

cout<<"t2 is : "<<endl;

t2.print();

cout<<"t is : "<<endl;

t.print();

t2.deleteNode(1);

t2.deleteNode(5);

cout<<"t2 is : "<<endl;

t2.print();

TreeNode *node = t.find(5);

cout << "found: " << node->value << endl;

node = t.find(100000);

cout << "t.find(100000): " << node << endl;

}

// tree_imp.hpp

// Trees

// Created by Pat Khai on 7/23/17.

#ifndef _TREE_H

#define _TREE_H

#include <cstdlib> // necessary in order to use NULL

class TreeNode

{

public:

TreeNode() : left(NULL), right(NULL) {}

TreeNode* left;

TreeNode* right;

int value;

};

class Tree

{

public:

// Default constructor

Tree();

// Copy constructor

Tree(const Tree& other);

//Destructor

~Tree();

// overloaded Assignment Operator

Tree& operator=(const Tree& other);

// Similar to insert function we discussed earlier

// creates node and inserts it at appropriate position.

void push(int value);

// Returns the address of the node containing the value.

TreeNode* find(int value) const;

// Print the tree data

void print() const;

// Deletes the node with value in the tree and deallocates its memory.

void deleteNode(int value);

private:

// Root of the tree.

TreeNode* start;

//copyOther

// you should implement and use this helper function inside your

// copy constructor and overloadedAssignment operator.

void copyOther(const Tree& other);

// clear

// you should implement and use this function inside your

// destructor to delete all the nodes and free memory

void clear();

// pushFrom

// Recursively push a single element into a tree.

// Use it in your push function.

void pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush);

// findFrom

// Recursively find a single element in a tree.

TreeNode* findFrom(TreeNode* startingPoint, int value) const;

// printFrom

// Recursively print the values in a tree. Use

// pre-order traversal.

// If a tree looks like this:

// 6

// /

// 5 8

// / /

// 0 7 9

// then it should be printed like this:

// 6

// 5

// 0

// 8

// 7

// 9

// Helper function that you should use inside your print function

void printFrom(TreeNode* startintPoint, int numSpaces) const;

// copyFrom

// Recursively copy another tree's nodes. Use

// pre-order traversal. Use this in CopyOther function.

void copyFrom(TreeNode* startintPoint);

// deleteFrom

// should implement and use in the delete function.

// Deletes the node with the value specified in the below function.

void deleteFrom(TreeNode* startintPoint, int value);

// clearFrom

// Recursively delete nodes. Use post-order traversal.

// Use it in clear function.

void clearFrom(TreeNode* startingPoint);

};

#endif /* tree_imp_hpp */

Explanation / Answer

main.cpp

#include "Tree.h"
#include <iostream>
using namespace std;

int main()
{
    Tree t;

    t.push(4);
    t.push(2);
    t.push(1);
    t.push(3);
    t.push(6);
    t.push(5);
    t.deleteNode(4);

    cout<<"t is : "<<endl;
    t.print();


    Tree t3(t);
    t3.push(7);

    cout<<"t is : "<<endl;
    t.print();
    cout<<"t3 is : "<<endl;
    t3.print();

    Tree t2;
    t2.push(2);
    t2.push(1);
    t2.push(3);
    t2.print();

    t2 = t;

    t2.push(8);
    t2.push(9);
    t2.push(11);

    cout<<"t2 is : "<<endl;
    t2.print();
    cout<<"t is : "<<endl;
    t.print();

    t2.deleteNode(1);
    t2.deleteNode(5);

    cout<<"t2 is : "<<endl;
    t2.print();

    TreeNode *node = t.find(5);
    cout << "found: " << node->value << endl;

    node = t.find(100000);
    cout << "t.find(100000): " << node << endl;
}

//#include <stdio.h>
#include<iostream>
#include "Tree.h"
using namespace std;

//default constructor
Tree::Tree(){
start = nullptr;
}

//copy constuctor
// must make the first node be nullpointer or copy constructor will never work!
Tree::Tree(const Tree& other):start(nullptr){
//sent to private data
copyOther(other);
}

void Tree::copyOther(const Tree& other){
//send to private data
copyFrom(other.start);
}

void Tree::copyFrom(TreeNode* startintPoint){
    if (startintPoint == nullptr){
        return;
    }
    push(startintPoint->value);
    copyFrom(startintPoint->left);
    copyFrom(startintPoint->right);
}

Tree::~Tree(){
    clear ();

}
//copy constructor
Tree& Tree::operator=(const Tree& other){
    //check to see if they equal each other
    if (this != &other){
        //delete last list
        clear();
        //copy the other list
        copyOther(other);

    }
    //returns pointer to object
    return *this;

}
void Tree::push(int value){
    //first create a new node like in bst example
    TreeNode* N1 = new TreeNode();
    N1->value = value;

    // if this is the first number, make it the root
    if (start == nullptr){
        start = N1;
        return;
    }

    //like insertNode, push value into tree with node and value
    pushFrom(start,N1);
}

void Tree::pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush){

    if(startingPoint->value < nodeToPush->value){
        //check to seee if the left side is empty
        if (startingPoint->right == nullptr){
            startingPoint->right = nodeToPush;
        }else{
            //continue to traverse through the list
            pushFrom(startingPoint->right, nodeToPush);
        }

    }else {
        if (startingPoint->left == nullptr){
            startingPoint->left = nodeToPush;
        }else{
            //continue to traverse through the list
            pushFrom(startingPoint->left, nodeToPush);
        }

    }

}

TreeNode* Tree::find(int value)const{
//implement the find FRom function
return findFrom(start,value);
}

TreeNode* Tree::findFrom(TreeNode* startingPoint, int value) const{

    //check if list is empty
    if (startingPoint == nullptr) {
        //cout << "That value does not exist. ";
        return NULL;
    }

    //basecase
    if (startingPoint->value == value){
        cout <<"Found " << value << endl;
        return startingPoint;

        //recuriseve statments
    }else if (value < startingPoint->value){
        return findFrom(startingPoint->left, value);
    }else{
        return findFrom(startingPoint->right, value);
    }

}

void Tree::deleteNode(int value){
    ///helper funcito of deleteFrom
    deleteFrom(start, value);

}

TreeNode* Tree::findMin(TreeNode* startintPoint){
    if (startintPoint==NULL){
        return;
    }
    while(startintPoint->left != NULL){
        startintPoint = startintPoint->left;
    }
    return;
}
void Tree::deleteFrom(TreeNode* startintPoint, int value){
    //from example in class, deleting a node

    if (startintPoint == NULL){
        return;
    }
    else if(value < startintPoint->value){
        deleteFrom(startintPoint->left, value);
        return;
    }else if(value < startintPoint->value){
        deleteFrom(startintPoint->right, value);
        return;
    }else{
        if (startintPoint->left == NULL && startintPoint->right == NULL){
            delete startintPoint;
            startintPoint = nullptr;
            return;
        }
        else if(startintPoint->left == NULL){
            TreeNode* temp = startintPoint;
            startintPoint = startintPoint->right;
            delete temp;
            return;
        }
        else if(startintPoint->right == NULL){
            TreeNode* temp = startintPoint;
            startintPoint = startintPoint->left;
            delete temp;
            return;
        }
        else{
            TreeNode* temp = findMin(startintPoint->right);
            startintPoint->value = temp->value;
            startintPoint->right = deleteFrom(startintPoint->right, temp->value);
            return;
        }
    }
}

void Tree::print() const{

    printFrom(start, 0);

}

void Tree::printFrom(TreeNode* startingPoint, int numSpaces) const
{
    //basecase
    if (startingPoint == nullptr) {
        return; // type void so we dont return anyting
    }

    for (int i = 0; i < numSpaces; i++) {
        cout << " ";
    }

    cout << startingPoint->value << endl;
    numSpaces = numSpaces+2;
    printFrom(startingPoint->left,numSpaces);
    printFrom(startingPoint->right,numSpaces);
}

void Tree::clear(){

    if (start == nullptr){
        return;
    }

    clearFrom(start);
    start = nullptr;
}

void Tree::clearFrom(TreeNode* startingPoint){
    //check if its already empty
    if (startingPoint == nullptr){
        return;
    }
    clearFrom (startingPoint->left);
    clearFrom (startingPoint->right);
    // getting an error here as a 'signal SIGBARRT' but this is how the book deleted a treeptr
    delete startingPoint;


    // print();
}

Tree.h

#ifndef _TREE_H
#define _TREE_H

#include <cstdlib> // necessary in order to use NULL

class TreeNode
{
public:
    TreeNode() : left(NULL), right(NULL) {}

    TreeNode* left;
    TreeNode* right;
    int value;
};

class Tree
{
public:
    // Default constructor
    Tree();

    // Copy constructor
    Tree(const Tree& other);

    //Destructor
    ~Tree();

    // overloaded Assignment Operator
    Tree& operator=(const Tree& other);

    // Similar to insert function we discussed earlier
    // creates node and inserts it at appropriate position.
    void push(int value);

    // Returns the address of the node containing the value.
    TreeNode* find(int value) const;

    // Print the tree data
    void print() const;

    // Deletes the node with value in the tree and deallocates its memory.
    void deleteNode(int value);

    //help with delete function
    void findM(int value);




private:
    // Root of the tree.
    TreeNode* start;

    //copyOther
    // you should implement and use this helper function inside your
    // copy constructor and overloadedAssignment operator.
    void copyOther(const Tree& other);

    // clear
    // you should implement and use this function inside your
    // destructor to delete all the nodes and free memory
    void clear();

    // pushFrom
    // Recursively push a single element into a tree.
    // Use it in your push function.
    void pushFrom(TreeNode* startingPoint, TreeNode* nodeToPush);

    // findFrom
    // Recursively find a single element in a tree.
    TreeNode* findFrom(TreeNode* startingPoint, int value) const;

    // printFrom
    //
    // Recursively print the values in a tree. Use
    // pre-order traversal.
    //
    // If a tree looks like this:
    //
    //           6
    //          /
    //         /
    //        5      8
    //       /      /
    //      /      /
    //     0      7     9
    //
    // then it should be printed like this:
    //
    // 6
    //   5
    //     0
    //   8
    //     7
    //     9
    //
    // Helper function that you should use inside your print function
    void printFrom(TreeNode* startintPoint, int numSpaces) const;

    // copyFrom
    // Recursively copy another tree's nodes. Use
    // pre-order traversal. Use this in CopyOther function.
    void copyFrom(TreeNode* startintPoint);

    // deleteFrom
    // should implement and use in the delete function.
    // Deletes the node with the value specified in the below function.
    void deleteFrom(TreeNode* startintPoint, int value);

    TreeNode* findMin(TreeNode* start);


    // clearFrom
    // Recursively delete nodes. Use post-order traversal.
    // Use it in clear function.
    void clearFrom(TreeNode* startingPoint);
};

#endif

Navigate

Implementing the diff function by using array subtraction and vector indexing. D

Implementing your own Tree ADT! Use the tree.h file which has all the methods to

Implementing the tree ADT functions. Be sure do error inputs. #include \"tree_he

Question

Explanation / Answer

Related Questions

Navigate