二分岐の実装

[Wseiwisyuois]

今学校で二分木を勉強しています。
そこでわからないところがあるので教えてください。
問題は下のプログラムで、traverse()とaddNode()とdelNode()を実装せよという問題なのですが、traverse()とaddNode()は解けたんですけどdelNode()がわかりません。
いろいろネットでも調べたのですが、いまだに解けません...
delNode()をどうすればいいか教えてください!
--------------------------------------------------------------------------------------

コード:

#include <iostream>
using namespace std;

class BinTree{
private:
  class BinNode{
  public:
    int idata;
    BinNode *left,*right;
    BinNode(int a=0){idata=a;left=right=0;}
    void printNode(){cout << idata << " ";}
  };
  BinNode *root;
  void traverse(BinNode *rp);
  void addNode(BinNode *rp,BinNode *node);
  BinNode *delNode(BinNode *rp,int x);
public:
  BinTree(){root=0;}
  void printTree(){traverse(root);}
  void insert(int x){
    BinNode *np=new BinNode(x);
    if(!root)root=np;
    else addNode(root,np);
  }
  void remove(int x){root=delNode(root,x);}
};

void BinTree::addNode(BinNode *rp,BinNode *node){
  if(rp->idata>node->idata){
    if(rp->left!=NULL)
      addNode(rp->left,node);
    else{
      rp->left=node;
    }
  }
  else{
    if(rp->right!=NULL)
      addNode(rp->right,node);
    else{
      rp->right=node;
    }
  }
}

BinTree::BinNode *BinTree::delNode(BinNode *rp,int x){
 } 
void BinTree::traverse(BinNode *rp){  
  if(rp==NULL)return; 
  if(rp->left!=NULL){
    traverse(rp->left);
  }
  rp->printNode();
  if(rp->right!=NULL){
    traverse(rp->right);
  }
}





int main(){
  BinTree bt;    // 空の二進木を作成
  int x;

  cout << "正整数をいくつか入力せよ --> ";
  while(cin >> x && x >0){    // 負数が入力されるまで正整数を入力
    bt.insert(x);    // x をデータとして持つノードを木に追加
  }

  bt.printTree();    // bt の木全体を表示する
  cout << endl;

  while(cout << "削除したい正整数 --> " && cin >> x && x > 0){
    bt.remove(x);
    bt.printTree();
    cout << endl;
  }

  return 0;
}

-----------------------------------------------------------------------------------------
ちなみに実行結果は
正数値をいくつか入力せよ --> 8 10 3 9 5 1 12 4 11 -1
1 3 4 5 8 9 10 11 12
消去したい正数値 --> 8
1 3 4 5 9 10 11 12
消去したい正数値 --> 1
3 4 5 9 10 11 12
消去したい正数値 --> 12
3 4 5 9 10 11
消去したい正数値 --> 1
左エラー:1:そのようなノードはありません
3 4 5 9 10 11
消去したい正数値 --> 12
右エラー:12:そのようなノードはありません
消去したい正数値 --> -1
終了

よろしくお願いします。

コード:

[usao]

・課題でしょうか？　個人的なものでしょうか？
・addNode()を見るに，要素の格納法には法則性があるんですよね？
　だったらその法則性に従い，削除すべきノードを探索すればよいのではないでしょうか．
・消去対象があったかどうかを知る必要があるなら BinTree::remove() は戻り値で情報を返すとか．
・あと，BinTreeにはデストラクタが欲しいところ．

＃各ノードに親へのポインタを持たせると各操作の実装が楽かも？

[Wseiwisyuois]

課題です。
書き加えて良いところはBinTree::BinNode *BinTree::delNode(BinNode *rp,int x){} この関数の中だけです。
ずっと考えてきたんですがわかりません>_<
期限も今日までなので焦っています。
答えを教えてください、お願いしますm(__)m

[usao]

BinTreeの他のところに手を加えてはいけないのだとしても
>traverse()とaddNode()とdelNode()を実装せよという問題
とのことなので，addNode()はご自身で実装されたものと思うのですが．

addNode()を見た感じ，
　あるノード（仮にノードＡと呼ぶことにすると）とその子ノードとの関係が
　・Ａの左の子は，Ａよりも小さいデータ値を持つ
　・Ａの右の子は，Ａのデータ値以上のデータ値を持つ
…となるように二分木が構築されていると思います．
（そのようにしろ，という問題だったものと想定します）
↓
BinTree::remove()では，削除したいノードを　データ値で　指定されているみたいなので
この法則を手掛かりにして，指定データ値をもつノードを探せばいいと思います．
(0)delNode()が最初にremove()から呼び出されたとき，引数rpはルートノードを指しています．
(1)rpがNULLだったら削除対象ノードはありません．おわり．
(2)rpのデータ値と削除指定データ値との大小関係をチェックします．
　・rpのデータ値==削除指定データ値　であれば，rpが削除すべきノードを指している
　・rpのデータ値 > 削除指定データ値　であれば　rp=rp->left　として(1)へ
　・それ以外なら rp~rp->right として(1)へ
↓
削除対象ノードが見つかったとき→これを削除します．
どうやれば効率的に削除できるのか？については検索すれば見つかると思います．
http://www40.atwiki.jp/spellbound/pages/1763.html
とか．

その他：
・remove()の実装を見ると．delNode()は削除処理を行った結果の木のルートノードへのポインタを返さないとならないみたい．
・remove()が戻り値を返せないとなると，「削除するノードがなかった」というメッセージの出力はdelNode()内でやるのだろうか？

[Wseiwisyuois]

いろいろ考えてみて

コード:

BinTree::BinNode *BinTree::delNode(BinNode *rp,int x){
  BinNode *p=rp;
  BinNode *pb;

  if(p->idata==x){
    BinNode *cn=NULL;
    if(p->left!=NULL && p->right==NULL){
      cn=p->left;
    }
    else if(p->left==NULL && p->right!=NULL){
      cn=p->right;
    }
    else if(p->left==NULL && p->right==NULL){
      cn=NULL;
    }
    else{
      
    } 
  }
  else if(p->idata>x){
    pb=p;
    p=p->left;
    delNode(p,x);
  }
  else{
    pb=p;
    p=p->right;
    delNode(p,x);
  }
}

ここまで作ったんですが、子が２つある時がサイトとかを見ても理解できません。教えてください。
それ以外はこれで大丈夫でしょうか？

[余裕がなければやる気もでない]

なぜそこまで再帰にこだわるのか、疑問ですね。関数呼び出しのオーバーヘッドや一つで十分な変数を何度も量産するのはどうみても無駄ですね。
まず、節を削除するとき、木を二度たどる必要があります。
1.削除対象を探すとき。
2.削除対象をルートとし、左分木最大または右分木最小を探すとき。（ついでに、見つかったとき最大（最小）を指す元のポインタをNULLにしておく）
（子が1つのとき、子のいるほうを探す。子が2つあるとき、最大または最小のどちらかを探す）
そのうえで、もし元のルートが削除され、新しいルートに変わった場合、新しいルートのポインタを返せばいいです。

[box]

二分木を再帰で実装しようとすること自体は、ごく自然なことだと思います。
質問者さんのコードについては、読んでいないのでコメントは差し控えます。

[かずま]

ここまで作ったんですが、子が２つある時がサイトとかを見ても理解できません。教えてください。
それ以外はこれで大丈夫でしょうか？

大丈夫じゃないのは明らかでしょ。

BinTree::BinNode * を返さなければならないのに return がどこにも
ありません。pb や cn に設定した値は使用されていません。
一致するものがないとき、どんどん深い所へ降りて行こうとしますが、
そんなことはできません。

ということで、もうちょっとましなコードを示しますが、ここは解答を
そのまま書いてはいけないそうなので、一部隠しておきます。

コード:

BinTree::BinNode *BinTree::delNode(BinNode *rp, int x)
{ 
    if (rp->idata == x) { 
        BinNode *p;
        if (rp->left == NULL && rp->right == NULL)
            p = NULL;
        else if (rp->right == NULL)
            p = rp->left;
        else if (rp->left == NULL)
            p = rp->right;
        else {
            BinNode **lp = &rp->right;
            while ((*lp)->left) lp = &(*lp)->left;
            p = *lp;
            *lp = p->right;
            p->left = rp->left;
            p->right = rp->right;
        }
        [ ここにあるコードが必要 ]
        return p;
    }
    if (rp->idata > x)
        if (rp->left)
            rp->left = delNode(rp->left, x);
        else
            cout << "左ノード:" << x << ":そのようなノードはありません\n";
    else 
        if (rp->right)
            rp->right = delNode(rp->right,x);
        else
            cout << "右ノード:" << x << ":そのようなノードはありません\n";
    return rp;
}

理解したら、このコードにコメントをつけてみてください。