树结构中的 C++ 指针

Question

我正在尝试为航海算法实现一些基本的树结构。我有这样的东西:

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();
        }
}

这应该创建 4 层的递归树，但只创建一层树。我认为这是父指针的问题，但我无法意识到到底发生了什么。

Answer 1

你的代码有几个问题

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);
        }
}

您还可以跟踪树的深度作为每个节点的数据成员。不幸的是，由于您未能提供 Minimal Complete and Verifiable Example , 我不能在这里测试。

另请注意，您的代码没有Node 的析构函数，泄漏了分配给节点的所有内存。当避免那些有利于对象的指针时，这个问题就会消失。由于无论如何 Node 都是在堆上分配的，因此这是 C++ 中合乎逻辑且正确的处理方式。

请进一步注意，您可能希望避免将子项保存在链表中(如果效率很重要，则应避免使用链表)。您可以改用数组或 vector。在这种情况下

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);
        }
    }
}