0

二分探索木からノードを削除する関数を作成しようとしています。ノードが 2 つの子を持つ 3 番目のケースが発生しましたが、ノードに子が 1 つまたはまったくない場合、コードが機能しません。

これは、本から直接コピーしたコードです。本から得たこのコードは間違っていますか?

template <class elemType>
void bSearchTreeType<elemType>::deleteFromTree
(nodeType<elemType>* &p)
{
nodeType<elemType> *current; //pointer to traverse the tree
nodeType<elemType> *trailCurrent; //pointer behind current
nodeType<elemType> *temp; //pointer to delete the node
if (p == NULL)
cout << "Error: The node to be deleted is NULL."
<< endl;
else if (p->lLink == NULL && p->rLink == NULL)
{
temp = p;
p = NULL;
delete temp;
}
else if (p->lLink == NULL)
{
temp = p;
p = temp->rLink;
delete temp;
}
else if (p->rLink == NULL)
{
temp = p;
p = temp->lLink;
delete temp;
}
4

1 に答える 1

0

コードが2人の子供で完全に機能していることを確認しますか？上記のスニペットは3つのケースのみを処理するため、（1）子がない、（2）左のptrが指す子が1つ、（3）右のptrが指す子が1つ...最後のケースでは、子が2つあります。 、単に存在しません。。。

だからあなたの質問に答えるために：はい、あなたが提供した上記のコードは間違っているようです（別名不完全）。

私はあなたが使用しているもののソースを追跡することができました。上記の関数内に次のコードがありますか（のストリームの後に追加されますelse if）、それとも存在しませんか？

else
{
    current = p->llink;
    trailCurrent = NULL;

    while(current->rlink != NULL)
    {
        trailCurrent = current;
        current = current->rlink;
    } //end while

    p->info = current->info;

    if(trailCurrent == NULL) //current did not move; 
                             //current == p->llink; adjust p
        p->llink = current->llink;
    else
        trailCurrent->rlink = current->llink;

    delete current;
}//end else
于 2012-04-29T02:31:14.023 に答える