AVL найти преемника

Question

Это моя функция-преемник:

int 
BalancedTree::successor( TreeNode *node ) // successor is the left-most child of its right subtree,
{ 
  TreeNode *tmp = node;
  int successorVal = -1;
  tmp = tmp->m_RChild;

  if( NULL != tmp )
  {
    while( NULL != tmp->m_LChild )
      tmp = tmp->m_LChild;

    // now at left most child of right subtree
    successorVal = tmp->m_nodeData;
  }

  return successorVal;

} // successor()

Мой инструктор дал нам файл, заполненный случайными данными.Я помещаю все эти данные в дерево, метод вставки работает, но как только метод удаления запускается, функция-преемник в какой-то момент возвращает то же значение узла, для которого я ищу преемника.Это не должно произойти правильно?моя функция преемника правильна?Если вы хотите увидеть метод удаления, просто упомяните об этом.

Answer 1

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