CODEWITHSUNDEEP
c++recursionconstructortreethis
Daria Lewandowska
Daria Lewandowska

Reputation: 11

C++ pointers in tree structure

I'm trying to implement some basic Tree structure for sea navigation algorithm. I've got something like this: 

class Point {
    float lng;
    float lat;
};

class Node {
public:
    Node *parent;
    std::list<Node> *childern;
    Point *point;
    Node::Node(Node *prnt, Point *point);
    void Node::calcChildrens();
};
Node::Node(Node *prnt, Point *point)  {
    this->parent = prnt;
    this->point = point;
    this->childern = nullptr;
}
int counter = 0;
void Node::calcChildrens() {

    for (int i = 0; i < 5; i++) {

        Point *p = new Point(someValX, someValY);
        Node n = Node(this, p);

        if (this->childern == NULL) this->childern = new list<Node>;
        this->childern->push_back(n);
        if (counter < 4) {
            counter++;
            n.calcChildrens();
        }
}

This should create 4 level's of recursion tree, but creates just one level of tree. I think it's the problem with parent pointers but i can't realize what really is happening.

Upvotes: 0

Views: 1688

Answers (1)

Walter
Walter

Reputation: 45414

There are several issues with your code

struct Point {   // we want public access, hence struct not class
    float lng;
    float lat;
};

struct Node {    // if all members a public, use struct
    Node*parent = nullptr;             // provide default argument
    std::list<Node> children;          // hold a list, not a pointer to one
    Point point;                       // hold a Point, not a pointer to one
    Node(Node*p, const Point&x)
    : parent(p), point(x) {}           // use initialization list
    void calcChildren(size_t levels);  // avoid global variable counter; use correct English
};

void Node::calcChildren(size_t levels)
{
    if(levels--)
        for(int i = 0; i < 5; i++) {   // really 5? 4 children seems more logical
            // construct child in place, avoid copying a Node    
            children.emplace_back(this, Point{someValX, someValY});
            children.back().calcChildren(levels);
        }
}

You may also keep track of the tree depth as a data member for each node. Unfortunately, as you failed to provide a Minimal Complete and Verifiable Example, I cannot test this here.

Note also that your code had no destructor for Node, leaking all memory allocated with a node. This problem disappears when avoiding those pointers is favour of objects. As Nodes are allocated on the heap anyway, this is the logical and correct way of doing things in C++.

Note further that you may want to avoid keeping the children in a linked list (linked lists are to be avoided if efficiency is important). You may instead use an array or vector. In this case

struct Node {    // if all members a public, use struct
    Node*parent = nullptr;             // provide default argument
    std::vector<Node> children;        // hold a vector, not a pointer to one
    Point point;                       // hold a Point, not a pointer to one
    Node(Node*p, const Point&x)
    : parent(p), point(x) {}           // use initialization list
    void calcChildren(size_t levels);  // avoid global variable counter; use correct English
};

void Node::calcChildren(size_t levels)
{
    if(levels--) {
        children.reserve(5);
        for(int i = 0; i < 5; i++) {
            // construct child in place, avoid copying a Node    
            children.emplace_back(this, Point{someValX, someValY});
            children.back().calcChildren(levels);
        }
    }
}

Upvotes: 2

Related Questions