Функция вставки двоичного дерева поиска

Question

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

bool bst::insert(string StudentName, int IDNumber) { 

class node *temp = root; 
class node *n=new node (StudentName, IDNumber); 

    if (root==NULL) { 
     root = n; 
     return true; 
    } 
    if (temp -> ID == n->ID) 
     return false; 

    while (temp) { 
     if (n-> ID < temp-> ID) 
     { temp -> left = n; 
      temp -> left -> parent= temp; 
      temp = temp -> left; 
      return true; 
     } 
     else 
     { 
      temp->right=n; 
      temp -> right ->parent=temp; 
      temp = temp -> right; 
      return true; 
     } 
    } 
    return false; 
} 

Answer 1

Проблема в коде находится внутри цикла while. Цикл будет работать только один раз, потому что вы всегда return, в обоих случаях. Таким образом, вы можете добавить только 3 узла (или меньше, в зависимости от значений), и вы никогда не проверяете, существует ли узел уже.

Чтобы исправить это, вы должны изменить свой код, чтобы сделать следующее:

while (temp) { 
    if (n-> ID < temp-> ID) 
    { 
     if(temp->left) 
      temp = temp->left 
     else 
     { 
      temp -> left = n; 
      temp -> left -> parent= temp; 
      return true; 
     } 
    } 
    else 
    { 
     // Analogously as for left 
    } 
} 
return false; // This should never happen, but we have to return... 

И я должен признать, найти ответ wasn't hard