Ошибка выделения памяти при попытке распечатать содержимое дерева в 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), которая при вызове на узле root дерева выше печатает содержимое дерева в этом формате:

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. Я знаю, что эта ошибка является результатом попытки доступа к памяти, которая как-то недоступна / недоступна, но я изо всех сил пытаюсь понять, что это действительно означает в моем случае. Мой метод 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

Проблема

Этот код очень вероятно нарушает правило 3 . Следующий оператор:

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

создает клон узла. Если вы не предусмотрели правило 3, но внедрили деструктор, клон будет использовать те же указатели на те же дочерние элементы, что и исходный узел. К сожалению, когда вы выходите из функции print(), клон уничтожается, а деструктор уничтожает детей. Весь последующий доступ к этим дочерним элементам будет затем обращаться к объекту, который больше не существует, который является 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
  }
}