尝试在 C++ 中打印树的内容时出现内存分配错误

Question

我的问题可能有一个简单的解决方案，但到目前为止我一直无法找到它。我是 C 语言的新手，这是我用 C++ 编写的第一个程序。

我有一个函数 create_complete_tree(int nr_child_nodes, int tree_depth)，它生成一棵深度为 int tree_depth 的树，其中每个节点（最后一行除外）都有 int nr_child_nodes 个子节点。 create_complete_tree(2,4) 生成一棵这样开始的树：

                      1
                     / \
                    /   \
                   2     9
                  / \   / \
                 3   6 10 13
                /\   /\/\ /\
                     ...

我正在尝试创建一个函数 print(std::ostream& str)，当在上面树的根节点上调用时，以这种格式打印树内容：

node_1
   node_2
      node_3
         node_4
         node_5
      node_6
         node_7
         node_8
   node_9
      node_10
         node_11
         node_12
      node_13
         node_14
         node_15

稍后我会担心添加缩进，但现在我只专注于以正确的顺序打印节点。这是我目前所拥有的：

void node::print(std::ostream& str) {
    str << this->get_name() << std::endl;

    for (int i = 0; i < this->get_nr_children(); i++) {
        node child = (*this->get_child(i));
        child.print(str);
    }
}

此函数打印节点 1-8，但随后出现 Segmentation fault: 11 错误。我知道这个错误是由于试图访问某种方式 unavailable/off-limits 的内存而导致的，但我很难理解这对我的情况意味着什么。我的 create_complete_tree 方法如下所示：

void node::create_complete_tree(int nr_child_nodes, int tree_depth) {
    if (tree_depth == 1) {
        return;
    } else {
        while (this->get_nr_children() < nr_child_nodes) {
            node* new_child = new node();
            this->add_child(new_child);
            (*new_child).create_complete_tree(nr_child_nodes, tree_depth - 1);
        }
    }
}

每个节点的子节点指针存储在一个名为 child_nodes 的向量中。感谢您抽时间阅读。如果有任何回复可以帮助我找到解决方案并更好地理解内存分配，我将不胜感激。

Answer 1

问题

此代码极有可能侵权the rule of 3。以下语句：

    node child = (*this->get_child(i));

创建节点的克隆。如果您没有提供规则 3，但实现了析构函数，则克隆将使用与原始节点相同的指向相同 children 的指针。不幸的是，当您随后离开 print() 函数时，克隆被销毁并且析构函数将销毁 children。所有对这些 children 的后续访问将访问一个不再存在的 object，即 UB。

段错误可能是 UB 的症状。如果不查看 node 的构造函数、复制构造函数、赋值和析构函数实现，我无法确定。但是看到这段代码，还有很多类似的问题，我会很惊讶这会是另一个问题 ;-)

可能的解决方案

无论如何，正确的解决方案是实施 3 所缺少的内容。因为如果不这样做，您将在许多情况下遇到类似的问题。

另一种解决方案（不是互斥的）是使用指针而不进行克隆：

void node::print(std::ostream& str) {
  str << this->get_name() << std::endl;

  for (int i = 0; i < get_nr_children(); i++) { // this-> is not needed
    node *child = this->get_child(i);         // pointer assignment without cloning
    child->print(str);                        // member invokation for a pointer
  }
}

尝试在 C++ 中打印树的内容时出现内存分配错误

Memory allocation error when attempting to print contents of a tree in C++

c++

tree

pointers

segmentation-fault

问题

可能的解决方案