c++ - 插入方法未正确比较

Question

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

Answer 1

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

    50
   /  \
  40   60
   \
    50

So, what you'd like to do is keep checking the duplicate age as you traverse down the tree instead of doing if(t->age == parent->age). You can update your while loop as follows-

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 的内存。