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 の重複挿入で挿入が失敗するのは 1 回だけです。代わりに、私のコードは 2 つの age 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

こう思う

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 に答える
0

あなたのコードの問題は、BST で重複した値が挿入された場合、元の値の子になると想定していたことですが、これは正しくありません。たとえば、このケースを考えてみましょう。

    50
   / \
  40 60
   \
    50

したがって、あなたがしたいことは、 を行う代わりに、ツリーをたどる際に重複する age をチェックし続けることです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 に答える