插入方法沒有正確比較

我有這種插入方法應該是將節點插入到包含人名和年齡的BST中。樹本身按年齡排序，每個節點包含具有該年齡段的人的鏈表。這棵樹插入方法沒有正確比較

我的插入方法不正確地比較這些節點彼此。輸入像

insert 1 50 john 
insert 1 30 elvis 
insert 1 90 david 
insert 1 50 james 
insert 1 95 abel 
insert 1 80 esther 
insert 1 95 vivian 
insert 1 95 barbara 
insert 1 50 james

我應該只看到插入失敗一次，重複插入詹姆斯。相反，我的代碼似乎讓兩個年齡段50個節點和失敗在插入維維安

Input Command: insert 1 50 john 
Input Command: insert 1 30 elvis 
Input Command: insert 1 90 david 
Input Command: insert 1 50 james 
Input Command: insert 1 95 abel 
Input Command: insert 1 80 esther 
Input Command: insert 1 95 vivian 
    --- Failed. 
Input Command: insert 1 95 barbara 
     --- Failed. 
Input Command: insert 1 50 james

我不清楚爲什麼會這樣。它甚至似乎沒有在正確的時間進行比較。

無論是這裏的方式是我的代碼

bool insert(const int &a, const string &n) { 
     BinaryNode* t = new BinaryNode; 
     BinaryNode* parent; 
     t->it = t->nameList.begin(); 
     t->nameList.insert(t->it ,n); 
     t->age = a; 
     t->left = NULL; 
     t->right = NULL; 
     parent = NULL; 

     if(isEmpty()){ 
      root = t; 
      return true; 
     } 
     else { 
      BinaryNode* curr; 
      curr = root; 
      while(curr) { 
       parent = curr; 
       if(t->age > curr->age) 
        curr = curr->right; 
       else 
        curr = curr->left; 
      } 

      if(t->age == parent->age) { 
       for(list<string>::iterator ti = parent->nameList.begin(); ti != parent->nameList.end(); ti++) { 
        string temp = *ti; 
        cout << temp << endl; 
        if(n.compare(temp)) 
         return false; 
        else if(ti == parent->nameList.end()) 
         parent->nameList.insert(ti,n); 
       } 
       return true; 
      } 

      if(t->age < parent->age) { 
       parent->left = t; 
       return true; 
      } 
      else { 
       parent->right = t; 
       return true; 
      } 
     } 
    }

來源

2013-11-04 user2754048

在你的代碼的問題是，您認爲在BST，如果一個重複的值插入時，它必將是原始值的一個孩子，這是不正確的。例如，考慮這種情況。

所以，你想要做的就是繼續檢查重複的年齡，向下遍歷樹而不是做if(t->age == parent->age)。您可以更新while循環如下 -

while(curr){ 
    parent = curr; 
    if(t->age == curr->age){ 
     //Check for duplicate name here 
    } 
    else if(t->age > cur->age) 
     curr = curr->right; 
    else 
     curr = curr->left; 
}

此外，你應該騰出新節點t的內存失效的條件。

來源

2013-11-04 12:38:58 Shubham

我覺得這

if(n.compare(temp)) 
    return false; 
else if(ti == parent->nameList.end()) 
    parent->nameList.insert(ti,n);

應該由每次檢測到同年齡時的名稱不同，它沒有寫if (n.compare(temp))是

if(!n.compare(temp)) 
    return false; 
else if(ti == parent->nameList.end()) 
    parent->nameList.insert(ti,n);

。

來源

2013-11-04 13:47:43

插入方法沒有正確比較

回答

相關問題