插入方法没有正确比较

我有这种插入方法应该是将节点插入到包含人名和年龄的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

插入方法没有正确比较

回答

相关问题