動的データ構造について

質問

二分探索木で，指定した節点を削除するプログラムを作りたいのですが，うまくいきません．

typedef struct node *NodeP;
typedef struct node{
int data; /* 節点データ */
NodeP lp, rp; /* 左右部分木へのポインタ */
} Node;

void dltNod(NodeP *root, NodeP dlt_p, NodeP prn)
/* *rootを根とした二分探索木から，節点dlt_pを削除する関数 */
/* prn は dlt_p の親を表すこととする. */
{
if(dlt_p->lp == NULL && dlt_p->rp == NULL){
/* 子がない節点 */
if(dlt_p == *root) *root = NULL;
else if(prn->lp == dlt_p) prn->lp = NULL;
else prn->rp = NULL;
}
else if(dlt_p->lp == NULL || dlt_p->rp == NULL){
/* 子が1つある節点 */
NodeP dson = (dlt_p->lp == NULL) ? dlt->rp : dlt_p->lp;
if(dlt_p == *root) *root = dson;
else if(prn->lp == dlt_p) prn->lp = dson;
else prn->rp = dson;
}
else{
/* 子が2つある節点 */
NodeP lson = dlt_p->lp;
prn = dlt_p;
while(lson->rp != NULL) {prn = lson; lson = lson->rp;}
dlt_p->data = lson->data;
dltNod(root, lson, prn);
}
}

子が2つある場合のみ正常に動き，他の場合は節点の削除が行われません．
どうすれば正常に動くでしょうか？
ヒントを頂けたら幸いです，よろしくお願いします．

回答No.1

aigaion · ベストアンサー

アルゴリズムは問題ないように見えますが・・・

節点を作るときにちゃんと初期値としてNULLを入れてます？
この有無をNULLで判定しているようなので入れ忘れていたら
すべての節点が2つの子を持つと判定されるような気がします。

質問とは関係なさげだけど気になった点。
実験段階なので実装してないだけだと思いますがNULL代入するだけでなく領域解放をお忘れなく。

NodeP dson = (dlt_p->lp == NULL) ? dlt->rp : dlt_p->lp;

は

NodeP dson = (dlt_p->lp == NULL) ? dlt_p->rp : dlt_p->lp;

ですよね？

お礼

＞節点を作るときにちゃんと初期値としてNULLを入れてます？
もしかしたら忘れてるかもしれません．
御指摘ありがとうございます!!

＞領域解放
freeですね，最後に入れるつもりです．

＞NodeP dson = (dlt_p->lp == NULL) ? dlt_p->rp : dlt_p->lp;
御指摘の通りです，すいませんでした;;

回答No.3

asuncion

「どううまくいかないか」を明記してほしいところです。
また、「ノードの作成がうまくいっていないため」に
うまく削除ができないことも可能性としてはあり得ます。
そこで、ノード削除関数だけでなく、コード全体と
テスト用のデータも提示してください。

お礼

無事解決しました、ありがとうございました！

補足

＞どううまくいかないか
　3
2
という木で，2を削除したいときに
3
とならなかったり
5
　8
　　13
という木で，8を削除したいときに
5
　3
とならないということです.

全体コードは今学校のPCに入っているので，
早くても月曜日にしかアップできないんです…;;;
ごめんなさい．

回答No.2

JaritenCat

> 子が2つある場合のみ正常に動き，他の場合は節点の削除が行われません．
最初の関数呼び出しで、親ノードの設定が正しくできてないのでは？

お礼

もしかしたらそうかもしれません;;
確認してみます，ありがとうございました！