二进制搜索树帮助插入功能

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