二進制搜索樹幫助插入功能

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