Implement a non-binary tree class in C++

Question

I've been trying to implement a tree class in c++ but I can't manage to make it work. I have implemented it like this:

class Tree {
    private:
    int root;  
    vector<Tree> children;  


    public:
    Tree(int root);
    int getRoot();
    vector<Tree> getChildren();
    void addChild(Tree& child);
    void printTree();
    bool isTreePresent(Tree element, queue<Tree> q);
};

With these associated functions:

Tree::Tree(int root){
    this->root = root;
}

int Tree::getRoot(){
    return root;
}

vector<Tree> Tree::getChildren(){
    return this->children;
}

void Tree::addChild(Tree& child){
    children.push_back(child);
}

void Tree::printTree(){
    queue<Tree> nextToPrint;

    cout << "Edges:" << endl;
    nextToPrint.push(*this);
    while (!nextToPrint.empty()) {
        for (int i = 0; i < nextToPrint.front().getChildren().size(); i++){
                nextToPrint.push(nextToPrint.front().getChildren()[i]);
                cout << "{" << nextToPrint.front().getRoot() << ", " << nextToPrint.front().getChildren()[i].getRoot() << "}" << endl;
        }
        nextToPrint.pop();
    }
    cout << endl;
}

As you can see, I've define a tree (as well as a node) as an int value and a vector of its children. It works a bit, but when I try to add children to already added element like this:

Tree a(5);
Tree tmp1(1);
Tree tmp2(2);
Tree tmp3(3);

a.addChild(tmp1);
tmp1.addChild(tmp2);
a.addChild(tmp3);

a.printTree();

It doesn't work. My tree is only made of a, the root, and 2 children : tmp1 and tmp3. At least that is what is displayed by my printTree function. When I use printTree on tmp1 though, it does display the tmp2 child.

Is this a problem with my print function ? Or is it a problem with my class in general ?

I have tried to make the children vector a vector of addresses of Trees, but it still didn't worked. I also tried to add children in the right order and it worked:

// This order works
tmp1.addChild(tmp2);
a.addChild(tmp1);
a.addChild(tmp3);

Unfortunately, I need to add children to already existing children for what I plan to do with these trees (I need them to make a spanning tree of a graph).

`a.addChild(tmp1)` copies `tmp1` into the tree. Any changes you make to the original, such as `tmp1.addChild(tmp2);`, does not affect that copy. If you want to change the node in the tree, you need to define some way of accessing it. — molbdnilo, Apr 16 '23 at 10:19

Cosemuckel · Answer 1 · 2023-04-16T10:31:30.183

0

When modifying tmp1, after adding it to a, these changes will not affect the added child in a, as a std::vector does not store references to elements. You could change the vector<Tree> children to vector<Tree*> children and then:

Tree* a = new Tree(5);
Tree* tmp1 = new Tree(1);
Tree* tmp2 = new Tree(2);
Tree* tmp3 = new Tree(3);

a->addChild(tmp1);
tmp1->addChild(tmp2);
a->addChild(tmp3);

a->printTree();

That would be the simplest approach. Note that you will have to free these when you're done. Otherwise refer to this post about vectors of references.

edited Apr 16 '23 at 10:31

answered Apr 16 '23 at 10:21

Cosemuckel

397
1
8

@kasimaru13 note that this doesn't provide the parent `Tree` object with ownership of the `Tree`s you add as children. You'd need to call `delete` in the main function after you're done with the tree object. If you want the `Tree` object to have ownership of the children, you should use move semantics, `void addChild(Tree&&)` or `void addChild(std::unique_ptr&&)`, if you need stable addresses. This would result in the same issues, but at least you wouldn't be able to accidentally make a copy; `a.addChild(tmp1);` wouldn't compile - you'd need `a.addChild(std::move(tmp1));` – fabian Apr 16 '23 at 10:41
I just don't understand, why using only one '&' would not work? If I add to the vector of children a reference to a tree, modifying this tree would also modify what is inside the vector from what I've understood. Then why doesn't it work like this ? I am still new to C++, I'm coming from C and this is very confusing for me – kasimaru13 Apr 16 '23 at 12:53
`&` is an lvalue reference, which means it can only be bound to an lvalue (i.e., a named variable or an expression that yields a named variable). `&&` is an rvalue reference, which means it can only be bound to an rvalue (i.e., an expression that does not have a name, such as a literal or the result of a function call). Here `&&` would be used, because the `std::unique_ptr` is only created in the function call. See the c++ reference: https://en.cppreference.com/w/cpp/language/reference – Cosemuckel Apr 16 '23 at 13:33

score 0 · Answer 2 · answered Apr 16 '23 at 13:25

This problem comes up over and over again when designing data structures in C++. As you will have realized from the previous answers and comments there are several different ways to solve it. Every coder uses their own selection from the possibilities, learns how to use it properly, and then thinks that it is the best and simplest.

For myself, I always use shared pointers. IMHO it allows the most natural looking application code with no need to hand code object deletion.

class myClass {
...
};

typedef std::shared_ptr<myClass> myClass_t;

std::vector< myClass_t > vector_of_myClass_objects;

.... populate vector .... 

myClass_t working_object = vector_of_myClass_objects[ 100 ];


// execute modify() on 100th object pointed to by vector

working_object->modify();

Implement a non-binary tree class in C++

2 Answers2