C ++, BTree Insert

Question

Привет, это код из моего класса SearchTree.Узел * - это структура с типом m_info типа int и m_left (меньшие узлы по информации) и m_right (большие узлы по информации)

void SearchTree::insert(const int &x) {
  Node* tempo = m_root;
  while (tempo != nullptr) {
    if (tempo->m_info >= x) {
      tempo = tempo->m_left;
    } else {
      tempo = tempo->m_right;
    }
  }
  tempo = new Node(x);
}

Я пытаюсь вставить новый узел в дерево.Но, похоже, мне что-то не хватает в управлении памятью.Там есть указатель на новый узел, но он не связан с m_root.Я запутался здесь.Я действительно люблю силу c ++, но она изгибает мою логику.

Что мне здесь не хватает?

Answer 1

Вы не можете сохранить указатель только в темпе.Темп является копией вашей текущей позиции в дереве.Вы должны присвоить его фактической переменной.

Мое решение этой проблемы состояло бы в том, чтобы проверить, является ли child дочерним элементом nullptr, прежде чем выполнять итерацию

void SearchTree::insert(const int &x) {
  if (!m_root) {
      m_root = new Node(x);
      return;
  }
  Node* tempo = m_root;
  while (true) {
    if (tempo->m_info >= x) {
      if (!tempo->m_left) {
        tempo->m_left = new Node(x);
        return;
      }
      tempo = tempo->m_left;
    } else {
      if (!tempo->m_right) {
        tempo->m_right = new Node(x);
        return;
      }
      tempo = tempo->m_right;
    }
  }
}

Также вы должны использовать умные указатели вместо необработанных указателей..

Альтернативным решением является указатель на указатель.Я не проверял, но вы можете попробовать

void SearchTree::insert(const int &x) {
  Node** tempo = &m_root;
  while (*tempo) {
    if ((*tempo)->m_info >= x) {
      tempo = &(*tempo)->m_left;
    } else {
      tempo = &(*tempo)->m_right;
    }
  }
  *tempo = new Node(x);
}

На этом изображении вы можете видеть.Если вы используете Node* tempo = m_root, то tempo содержит копию значения в m_root.Если вы измените tempo, то m_root останется без изменений.

Если вы используете Node** tempo = &m_root, тогда tempo - указатель на m_root.Вы можете изменить от m_root до tempo.

Answer 2

Вы продолжаете продвигаться tempo, пока оно не станет равным nullptr.В этот момент вы оставили дерево, и все, что у вас есть под рукой, - указатель на ничто.Обратите внимание, что, в частности, программа не может определить, какой узел, который вы посетили в последний раз, привел к тому, что tempo стал null.

Вместо этого вам нужно сделать остановку на один шаг раньше : Хотя tempo все еще указывает на узел, но на следующем шаге он указывает на null.Теперь у вас все еще есть действующий узел дерева, и вы можете присоединить к нему вновь выделенный узел.