Tree with multiple children using vector

Question

I'm trying to make a tree with multiple children, this tree should look the following:

      n 
/     |     \
n2    n3     n4
|
n5  

Every node has its own factor, my task is to count the quantity of all nodes, for example the quantity of n5 is n.factor * n2.factor * n5.factor.

I think that the problem is in pointers, but I don't know how I can deal with it.

Some ideas on what might be wrong are below in the code.

Obiekt.h

#include <string>
using namespace std;
class Obiekt
{
private:
string name;


public:
    Obiekt();
    Obiekt(string name);

    void wyswietlObiekt();
    string getName();

    ~Obiekt();
};

Node.h:

#include "Obiekt.h"
#include <vector>
#include <string>


using namespace std;

class Node {

public:

    Node();
    Node(Obiekt ob, double factor);

    void add(Node node);
    void show();
    vector<Node> getChildrenList();
    double getFactor();
    Obiekt getObiekt();


private:
    vector<Node> children;
    double factor;
    Obiekt obiekt;

};

Node.cpp:

#include "Node.h"
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdlib>

using namespace std;


Node::Node()
{
    obiekt = Obiekt();
    factor = 0.0;
}

Node::Node(Obiekt ob, double mn)
{
    obiekt = ob;
    factor = mn;
}

void Node::show()
{
    for (int i = 0; i < children.size(); i++) {

        cout << children[i].getFactor() << endl;
    }
}


void Node::add(Node node)
{
    children.push_back(node);
}



vector<Node> Node::getChildrenList()
{
    return children;
}

double Node::getFactor()
{
    return factor;
}

Obiekt Node::getObiekt()
{
    return obiekt;
}

Tree.h:

#include <string>
#include <vector>
#include "Node.h"

using namespace std;


class Tree
{

public:
    Tree();

    void addNode(Node *parent, Obiekt o, double mnoznik);
    void addNode(Node *parent, Node wezel);
    void deleteTree();
    double countNodes(Node node, string key);
    vector<Node*> getList();
    double search(string key);

private:
    vector<Node*> nodeTree;
    Node root;
};

and Tree.cpp:

#include "Tree.h"
#include <string>
#include <vector>
#include <iostream>
#include <sstream>
#include <cstdlib>

using namespace std;

Tree::Tree()
{
    root = Node();
}

void Tree::addNode(Node *parent, Obiekt o, double mnoznik)
{
    Node n(o, mnoznik);

    nodeTree.push_back(&n);

    if (parent == NULL)
    {
        root = Node(o, mnoznik);
        cout << "mnoznik korzenia: " << root.getFactor() << endl;
    }
    else
    {
        parent->add(n);
    }
}

void Tree::addNode(Node *parent, Node wezel)
{
    nodeTree.push_back(&wezel);

    if (parent == NULL)
    {
        root = wezel;
        cout << "mnoznik korzenia: " << root.getFactor() << endl;
    }
    else
    {
        parent->add(wezel);
        cout << "added: " << wezel.getFactor() << endl;
    }
}

double Tree::countNodes(Node node, string key)
{
    int rozmiar = nodeTree.size();

    double factor = node.getFactor();
    double iloczynTemp = 1.0;
    double quantity = 0.0;

    for (Node node : node.getChildrenList())
    {
        iloczynTemp = factor * node.getFactor();

        if (node.getObiekt().getNazwa() == key)
        {
            quantity = quantity + iloczynTemp;
        }

        quantity = quantity + countNodes(node, key);
    }

    return quantity;
}

double Tree::search(string key)
{
    double wynik = 0.0;
    for (Node *n : nodeTree)
    {
        if (n->getObiekt().getNazwa() == key)
        {
            wynik = wynik + n->getFactor();
        }
    }
    return wynik;
}


void Tree::deleteTree()
{
    nodeTree.clear();
}


vector<Node*> Tree::getList()
{
    return nodeTree;
}

int main()
{

    Tree tree;

    Node n(Obiekt("n"), 1.0);

    tree.addNode(NULL, n);

    Node n2(Obiekt("n2"), 2.0);
    tree.addNode(&n, n2);
    Node n3(Obiekt("n3"), 3.0);
    tree.addNode(&n, n3);
    Node n4(Obiekt("n4"), 4.0);
    tree.addNode(&n, n4);

    Node n5(Obiekt("n5"), 5.0);
    tree.addNode(&n2, n5);

    n.show();

    cout << n.getChildrenList().size() << endl;
    cout << n2.getChildrenList().size() << endl;
    cout << n.getChildrenList()[0].getChildrenList().size() << endl;


    system("pause");
    return 0;
}

The problem shows up in main()

cout << n.getChildrenList().size() << endl;      // right result = 3
cout << n2.getChildrenList().size() << endl;     // right result = 1
cout << n.getChildrenList()[0].getChildrenList().size() << endl;  // wrong result, should be 1 like above, but it is 0, why?

Another problem is in countNodes method in Tree.cpp:

    quantity = quantity + countNodes(node, key); // why countNodes(node, key) is 0, it should be 0 when node don't have children, but some of them has.

Thank you in advance, bakii!

Answer 1

This biggest problem I see in this code is you're mixing pointers and passed-by-value items. A bad example:

void Tree::addNode(Node *parent, Obiekt o, double mnoznik)
{
    Node n(o, mnoznik);

    nodeTree.push_back(&n);
    ...

On this line you create a local object on the stack in the context of the addNode() function, then push it's address into your vector. At the end of this function n will go out of scope and the address will no longer be valid. It is likely that on subsequent calls the address will be reused, but you're off in undefined behavior land and Nothing Good can come of it.

For this kind of structure you probably want to be working with pointers all the way through. Instead of allocating a node on the stack like this, you would want something like:

Node* n = new Node(o, mnoznik);
nodeTree.push_back(&n);

In your destructor you would want to delete all of the nodes in the vector.

With more work you may come up with an all-values based tree, or be able to use smart pointers to handle your memory management, but I'm calling that out of scope for this question.