二分木のコピー

ニ分木の構造を持つクラスを作ったのですが、
コピーはどうやって実装すればいいんでしょうか？（深いコピーです）
（参考になるサイトがあれば教えてください。。。）

また、ヒープツリーであれば配列をごっそり入れ替えるだけでコピーが出来るんでしょうか？（階層は変わらないとして）

No.1 ベストアンサー 回答者： Tacosan 回答日時： 2010/04/06 17:27

二分木を deep copy するって, 普通に再帰的にコピーすればいいと思うんだけど.... 具体的な実装を示したうえで「ここでこんな風に困っている」というのが出てくれば, それなりにアドバイスできるかもしれん.

ヒープツリーの方は, 配列で実装しているならその配列をコピーすればいい. もちろん付随するデータがあるならそれもコピーする必要があるけど, あなたがどう実装しているか知らないのでその辺は適当に判断してくれ.

この回答へのお礼

回答ありがとうございます。
汚いソースコードで恥ずかしいんですけども、、
一応動いてるんですけど他の人の実装はどうなってるか知りたいです。
// ノードのコピー
Node* BinaryTree::CopyNode(Node* src) {
　Node* p = NULL;
　if (src == NULL) return NULL;
　p = new Node(src->GetData());
　Node* c = CopyDFO(src->GetChild());
　if (c != NULL) p->SetChild(c);
　　Node* n = CopyDFO(src->GetNext());
　　if (n != NULL) p->SetNext(n);
　　return p;
}

お礼日時：2010/04/06 17:55

No.4 回答者： rabbit_cat 回答日時： 2010/04/07 01:52

木の探索は、再帰でもまあいいけど、キューを使えば再帰にする必要もない。

1. キューのルートノードを入れる
2. もし、キューが空なら終了
3. キューからノードを一個取り出す。
4. 取り出したノードの子ノード（ニ分木なら２個）をキューにいれる
5. 今注目しているノードについての処理
　（深いコピーしたいなら、ここで、コピー木の作成処理をすればよい）
6. 2,に戻る

って感じです。
キューをFIFO（First In First Out）にすれば、幅優先探索
キューをLIFO（Last In First Out）にすれば、深さ優先探索
になります。

この回答へのお礼

回答ありがとうございます。
え、ホントですか。考えてみます。

お礼日時：2010/04/07 14:24

No.3 回答者： BLK314 回答日時： 2010/04/07 01:09

newを使っているということはC++ですね。

C++ならコンテナは（なるべく）自作せずにSTLを使うべきでしょう。
http://brain.cc.kogakuin.ac.jp/~kanamaru/lecture …

STLなら、「コピーをどう実装しよう」という悩みは根本から解決されます。

「実装する必要がない」からです。

これぞ、究極の解決策と思いませんか？

プログラミングで言われることに次の言葉があります。

「バグを作らない究極の方法がある。
それはプログラムを作らないことだ！」

STLに関する情報は書籍も沢山ありますし、
サイトもあります。

この回答へのお礼

回答ありがとうございます。
クラスの構造が木なのでSTL関係ないです。。。

お礼日時：2010/04/07 14:22

No.2 回答者： Tacosan 回答日時： 2010/04/06 22:53

CopyDFO がどんなものなのかわかりませんが, 基本的にはそんな感じ.

ただ, 最初の new Node が失敗するとイタいことになりそう. 再帰の途中で new が失敗したときのことも気をつける必要がありそうです (中途半端にコピーしたものができることになる).
それと, c や n が NULL でないことを確認してるけど, この確認って本当は不要なのでは?

この回答へのお礼

ありがとうございます。
見直してみます

お礼日時：2010/04/07 14:21