Блог

Я новичок в C , и я уверен, что с этим вопросом должно быть легко справиться, но я думаю, что я упускаю некоторые основные понятия. В коде реализовано двоичное дерево, и нас просят определить количество узлов в этом двоичном дереве. Как вы можете видеть в классе Node, узел имеет два указателя-члена: левый, который указывает на узел слева, правый, который указывает на узел справа. Входным сигналом является корневой узел. В любом случае, я нашел такое решение:

1. Создайте вектор узлов, которые я назвал узлами в коде, и добавьте корневой узел, и установите количество узлов (howManyNodes в коде) равным 1.
2. Пока nodes не пуст (в начале мы добавляем корневой узел), проверьте, есть ли у него левый и правый указатели. Если они доступны (т. Е. Не nullptr), добавьте эти указатели в вектор узлов (я использую insert). В то же время увеличьте количество узлов (howManyNodes в коде) на единицу.
3. После проверки, имеет ли конкретный узел левый и правый указатели, я удаляю этот узел из списка, для чего я использую функцию pop_back() .
4. В конце вектор будет пустым, и я получу howManyNodes в качестве ответа.

Вот код, и я только реализовал функцию count. Остальное взято из шаблона.

 #include <iostream>
#include <vector>


class Node {
public:
  Node *left, *right;
  Node() { left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};

// I implement this part
int count(Node *n) {

    int howManyNodes = 1;
    std::vector<Node> *nodes = new std::vector<Node>;
    nodes->push_back(*n);

    while (!nodes->empty()){

      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes  = 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes  = 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}
// I implement this part.


int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  // This should print a count of six nodes
  std::cout << count(n) << std::endl;

  // Deleting n is sufficient to delete the entire tree
  // because this will trigger the recursively-defined
  // destructor of the Node class.
  delete n;
  n = nullptr;

  return 0;
}
  

Проблема в том, что я никогда не смогу избавиться от ошибки сегментации. Как я искал, это происходит, когда код пытается получить доступ к памяти, к которой он не должен. Мой код может быть легко исправить, но у меня есть следующие вопросы:

1. Если std::vector использует память кучи для своих членов, зачем мне нужно определять здесь новый вектор? В основной функции (которую я не писал) все написано new , тогда я предположил, что я также должен использовать new, когда это возможно, но я не понимаю логики.
2. В моем коде я хочу использовать ссылки, потому что я хочу получить доступ только к указателям узлов, а не изменять их — я узнал, что использование самого объекта требует создания копий и замедляет процесс, поэтому не предпочтительнее -. Какая часть моего кода пытается изменить какие-либо указатели?
3. Теперь, когда я определил новый вектор, должен ли я также удалить его и сделать его равным nullptr, прежде чем возвращать значение?

Заранее спасибо!

Проблема с вашим Node классом заключается в том, что он не следует правилу 3/5/0, и всякий раз, когда вы делаете копию a Node , и вы делаете много копий, у вас возникают проблемы, потому left right что узлы будут удалены, как только скопированный объект выйдет из области видимости, а затем снова, когда вы вызываете delete себя.

Краткое изложение ошибок в вашей count реализации:

 int count(Node *n) {
    int howManyNodes = 1;
    // doesn't make sense to allocate vector dynamically
    // also you forgot to delete it
    std::vector<Node> *nodes = new std::vector<Node>;
    // keeping nodes as value will copy them, which leeds to double free
    nodes->push_back(*n);
    while (!nodes->empty()){
      // another copy - thus another problem, but this time "only" a memory leak since you don't delete it
      Node* trial = new Node(nodes->back());
      if (trial->left){
          std::cout << trial->left << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->left);
          howManyNodes  = 1;
      }
      if (trial->right){
          std::cout << trial->right << std::endl;
          // another copy
          nodes->insert(nodes->begin(), *trial->right);
          howManyNodes  = 1;
      }
      nodes->pop_back();
  }
  return howManyNodes;
}
  

Как это может быть реализовано без копирования каких-либо объектов:

 void count(Node* n, intamp; numNodes)
{
  numNodes  ;
  Node* left = n->left;
  Node* right = n->right;
  if (left) count(left, numNodes);
  if (right) count(right, numNodes);
}

int main() {

  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();
  int numNodes{0};
  count(n, numNodes);
  std::cout << numNodes << std::endl;
  delete n;
  return 0;
}
  

Это рекурсивный подход, поэтому, возможно, не самый лучший. Если вам действительно нужно реализовать какое-то дерево вручную, используйте std::unique_ptr , удалите явно конструктор копирования / присваивание и реализуйте метод count внутри вашего Tree класса, если вы планируете иметь подобный sth.

Как объяснил @pptaszni, в моем коде я делал копии экземпляров, и это вызывало проблемы. Рекурсивный подход, предложенный @pptaszni, намного проще и предпочтительнее, о чем я раньше не мог подумать. Я также исправил свой подход, передав указатели вместо значений. Это работает:

 #include <iostream>
#include <vector>


class Node {
public:
  Node *left, *right;
  Node() { left = right = nullptr; }
  ~Node() {
    delete left;
    left = nullptr;
    delete right;
    right = nullptr;
  }
};


int count(Node *n) {

    int howManyNodes = 1;
    std::vector<Node*> nodes = {};
    nodes.push_back(n);

    while (!nodes.empty()){

      Node* trial = nodes.back();
      if (trial->left){
          nodes.insert(nodes.begin(), trial->left);
          howManyNodes  = 1;
      }
      if (trial->right){
          nodes.insert(nodes.begin(), trial->right);
          howManyNodes  = 1;
      }
      nodes.pop_back();
  }

  // Implement count() here.

  return howManyNodes;
}

int main() {

  
  Node *n = new Node();
  n->left = new Node();
  n->right = new Node();
  n->right->left = new Node();
  n->right->right = new Node();
  n->right->right->right = new Node();

  // This should print a count of six nodes
  std::cout << count(n) << std::endl;

  // Deleting n is sufficient to delete the entire tree
  // because this will trigger the recursively-defined
  // destructor of the Node class.
  delete n;
  n = nullptr;

  return 0;
}