バイナリ検索ツリーからノードを削除する

Question

バイナリ検索ツリーからノードを削除する関数を作成しようとしています。私は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; 
} 

Answer 1

あなたのコードは2人の子供と完全に動作していますか？あなたが提供したスニペットは、（1）子供がいない、（2）左の子どもが指している子供が1人、（3）右の子どもが指している子供が1人... 3人の子供がいる最後のケース単に存在しません...

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

私はあなたが使っているもののソースを追跡することができました。上の関数（ストリーム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