1

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

我应该只看到插入失败一次，因为 James 重复插入。相反，我的代码似乎创建了两个 50 岁的节点并且无法插入 vivian

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;
            }
        }
    }
4

2 回答 2

0

您的代码中的问题是您假设在 BST 中，如果插入重复值，它肯定是原始值的子值，这是不正确的。例如，考虑这种情况。

    50
   / \
  40 60
   \
    50

因此，您想要做的是在遍历树时不断检查重复的年龄，而不是执行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-04T12:38:58.873 回答
0

我认为这

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

应该

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

if (n.compare(temp))通过每次检测到相同年龄时写入，当名称不同时它会失败。

于 2013-11-04T13:47:43.773 回答