CODEWITHSUNDEEP
c++vectordata-structuresbinary-treebinary-search-tree
Grant Ronterio
Grant Ronterio

Reputation: 49

C++ Binary Tree Using Vector

I am tasked with storing a binary tree within a vector. Within each node is stored an int ID, int Age, and a string name.

The nodes are stored and organized within the vector by ID.

When storing the binary tree within a vector, I am using the algorithm 2i and 2i+1 to dictate a node's left and right child respectively.

I have managed to create an insert method that I believe satisfies these conditions and inserts a node into a vector, however, after attempting to insert these nodes into the vector

50 21 Tim

75 22 Steve

I notice that it is not actually inserting these nodes into the vector.

I placed a line that prints the index after insertion, and I have realized that after the first insertion, index no longer updates.

An example Running the insert method using this example

enter image description here

Is there something wrong with my insert() method?

Here is my code.

#include "BinaryTree.h"
#include <string>
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
int index = 0;

struct Node
{
    int ID;
    int age;
    string name;

    Node()
    {

    }

    Node(int id, int Age, string nm)
    {
        this->ID = id;
        this->age = Age;
        this->name = nm;
    }
};

vector<Node> binaryTree(30);


BST::BST()
{

}



void BST::start()
{
    int choice;


    cout << "What would you like to do?" << endl;
    cout << "1. Add a node to the tree" << endl;
    cout << "2. Delete a node from the tree" << endl;
    cout << "3. Find a node in the tree" << endl;
    cout << "4. Report the contents of the tree" << endl;
    cout << "5. Exit program" << endl;

    cin >> choice;

    if (choice == 1)
    {
        insert();
    }

    if (choice == 2)
    {
        Delete();
    }

    if (choice == 3)
    {
        find();
    }

    if (choice == 4)
    {
        report();
    }


}


void BST::insert()
{
    int ID;
    int AGE;
    string NAME;
    int root = 1;

    bool success = false;
    cout << "Please enter the ID number, age and name:" << endl;

    do
    {
        cin >> ID >> AGE >> NAME;
    } while (ID < 0);

    Node *tree = new Node(ID, AGE, NAME);


    if (index == 0)
    {
        binaryTree[1] = *tree;
    }

    if (index > 0)
    {
        do
        {
            if (tree->ID > binaryTree.at(root).ID)
            {
                root = 2 * root + 1;

            }

            if (tree->ID < binaryTree.at(root).ID)
            {
                root = 2 * root;
            }

            if (binaryTree.at(root).ID == NULL)
            {
                binaryTree.at(root) = *tree;
                cout << "Added!" << endl;
                cout << "Vector size: " << binaryTree.size() << endl;
                success = true;
            }
        } while (!success);
    }

    index++;
    cout << index << endl;
    delete tree;

    start();
}

EDIT: I realized that I failed to check against index, so I changed it from '=' to '==' comparison to start the loop. However, Now I am getting a _Xout_of_range("invalid vector subscript"); exception thrown by the vector class

Here is the error.

enter image description here

Upvotes: 0

Views: 9440

Answers (1)

Aconcagua
Aconcagua

Reputation: 25518

do
{
    cin >> ID >> AGE >> NAME;
} while (ID < 0);

Not the actual problem, but you should check std::cin for its state after this operation - if the user did enter invalid input ("xyz"), cin remains in failure state and you won't ever get valid input... Additionally, if you make id and age unsigned, you don't have to check for negative input.

My personal variant:

for(;;)
{
    std::cin >> id >> age >> name;
    if(std::cin)
        // input is valid!
        break;
    std::cout << "invalid input" << std::endl; // some better text?
    std::cin.clear();
    std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');
}

See this answer for details...

if (index = 0)
//        ^ this is an assignment! always sets index to 0 and then
//          checks the value; for COMPARISON, you need to use ==
{
    binaryTree[1] = *tree;
//             ^ and when do you ever fill index 0???
}

The assignment instead of comparison is what actually is causing your problem!

If index shall represent the number of elements in the vector, you can drop it entirely, use binaryTree.size() instead...

if (binaryTree.at(root).ID == NULL)
{
    binaryTree.at(root) = *tree;
    cout << "Vector size: " << binaryTree.size() << endl;
}

Wait, are you going to pre-fill the vector with default values??? If so, binaryTree.size() will always have the same size... And you possibly need a huge pre-allocated array and are likely to get poor fill grades. Coming back to later. Be aware that NULL is a macro that shall represent null pointers (if you really are dealing with, prefer the nullptr keyword instead!). Don't use it for integer comparisons, use the value 0 directly.

Additionaly: at will throw an exception, if the vector is not large enough. And then? Prefer using the index operator, but before, check if the vector is large enough. If not, increase the vector's size appropriately (e. g. make it twice its previous size).

Node* tree = new Node(id, age, name);
binaryTree[x] = *tree;
delete tree;

Well, why then on the heap anyway? Simply do it this way:

Node             tree(id, age, name);
//  no pointer!  creating object directly on the stack!
binaryTree[x] = tree; // assign directly
// no delete necessary, object will be destructed automatically when leaving scope

In the current case not necessary, moving and copying result in the same, but with more complex objects, moving instead of copying might have a value, so you could optimise to:

binaryTree[x] = std::move(tree); // creates an rvalue reference...

Coming back to the size/fillgrade problem: Binary trees are only efficient, if you keep them balanced. Generally, in runtime, if stored in array like structures such as vectors, in memory, too. So you should keep your tree balanced. A variant might be not starting at the root of the tree, but simply appending the element at the end (use push_back) and then move it upwards as long as it is bigger than the parent node, if in the left tree, or smaller than, if in the right tree. If you provide a move constructor, you can use std::swap to interchange elements. This alternative approach additionally avoids the need of sentinel values (node.id == 0)...

Edit in reply to your comment:

OK, now first lets include index 0 in the algorithm, too, there is no need to skip position 0.

Then, your problem might be already the first insertion: Have you assured that the vector really contains already two dummy elements? Better lets consider we have an empty vector right from the start. Then we simply can do:

unsigned int index = 0;
// renaming root to index, assuming we dropped
// the other index variable already
// benefit: you can clearly differentiate my and your code...

Node node(id, age, name);
for(;;)
{
    if(index <= binaryTree.size()) // covers empty vector, too, as 0 <= 0...
    {
        binaryTree.resize(index + 1);
        // vector with size of n can store n elements
        // at indices [0 .. n - 1] - deduce the inverse yourself
        // and you know why index + 1...
        binaryTree[index] = node;
        // if we needed to resize, the new elements are unoccupied
        // anyway, so we simply can insert and are done...
        break;
    }
    if(binaryTree[index].id == 0)
    {
        // sentinel found, can insert here:
        binaryTree[index] = node;
        break;
    }
    // now calculate the child index just as before
}

Calculation of next child index has an error, too, though:

 if (tree->ID > binaryTree.at(root).ID)
     root = 2 * root + 1;

 if (tree->ID < binaryTree.at(root).ID)
     root = 2 * root;

And what, if the ids are the same??? At least one of these must contain the equality, too, otherwise you will get caught in an infinite loop. But then, one condition gets exactly the inverse of the other, so you can simply use if/else:

 if (node.id > binaryTree[index].id)
     index = 2 * index + 1;
 else
     index = 2 * index;

Now some nice tuning: In C++, comparisons always result boolean values, these then promoted to (unsigned) int always get either 0 or 1, so you can, if you like, shorten above to the following one-liner (well, my renaming applies again...):

 index = 2 * index + (tree->ID > binaryTree[index].ID);

Upvotes: 1

Related Questions