AVL trouver le successeur

Question

C'est mon mon successeur func:

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()

Mon instructeur nous a donné un fichier rempli de données aléatoires. Je place toutes ces données dans l'arborescence, la méthode d'insert fonctionne, mais une fois la méthode de suppression, la fonction successeur renvoie à un moment donné la même valeur du nœud pour lequel je recherche un successeur. Cela ne devrait pas pouvoir se produire correctement? Ma fonction successeur est-elle correcte? Si vous voulez voir la méthode de suppression, il suffit de le mentionner.

Answer 1

Votre définition du successeur est déjà imparfaite: si le nœud n'a pas de nœud droit, le successeur est l'un de ses ancêtres: le premier dont l'enfant gauche est le nœud ou l'un de ses ancêtres. Ce n'est que si aucun ancêtre de ce type existe, le successeur n'est pas le successeur. Personnellement, je retournerais un itérateur au nœud mais sinon le code semble être OK.