Binary Search Tree(=二分検索木)で一つのobjectから別のobjectに「再帰的に(自分が自分を呼んで)」コピーするメソッドを探しています。例えば、tree1に(BreadthFirst =上から下へ、左から右への数え方で)5 3 8 2 4 7と入っていたとすればそのtree1をルートから辿ってそれらの要素をtree2にそのままコピーするメソッドです。tree2 = tree1;は今回は使ってはいけないことになっています。言語はJavaですが、アルゴリズムが欲しいだけなのでCやC++でも構いません。また、日本語のサイトでも英語のサイトでも構いません。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2003/11/22 17:21:32
  • 終了:--

回答(1件)

id:sasada No.1

sasada回答回数1482ベストアンサー獲得回数1332003/11/22 18:52:15

ポイント40pt

http://www.hatena.ne.jp/list

人力検索はてな - 質問一覧

 URLはダミーです。

 なかなかコードが見つかりません (汗;

 ごめんなさい。

 二文探索木ですから、

  1) tree1の部分木の値(真ん中の値)を、tree2に挿入

  2) それより小さい値(左枝)を処理

  3) それより大きい値(右枝)を処理

と、再帰処理するだけなのですが。

 もうすこしアルゴリズムっぽく書くと、

 (0) tree1のルートをターゲットノードとする。

 (1) そのノードが値も左右の枝も持たなければ (5)へ。

 (2) そのノードの持つ値をtree2に挿入する。

 (3) tree1の左枝の要素を再帰的に処理する。

   (左枝の要素のルートをターゲットノードにして(1)へ)

 (4) tree1の右枝の要素を再帰的に処理する。

 (5) 一つ上のレベルに戻る。いまのレベルがtree1のルートなら終了。

みたいな。

 これではお役に立ちませんか?

 ちなみに、B-treeへの挿入や探索は書きURLのような感じです。

 以下、おまけです。

 アルゴリズムの解説です。

 JAVAによるデータ構造の本です。

id:donataka

ようやく出来ました。

sasadaさんのアルゴリズムが役に立ちました。

下のメソッドを実行すると”ego”にtree1とまったく同じ構造の二分探索木が出来上がります。

ただ、これをtree2のオブジェクトとして返す方法が分かりませんのですが、これはまた別の問題なので今回の質問に対しては解決です。

ありがとうございました!

public IntBSTNode copy(IntBSTNode source) {

IntBSTNode leftCopy, rightCopy;

if(source != null) {

System.out.println(source.key);

leftCopy = copy(source.left);

rightCopy = copy(source.right);

IntBSTNode ego = new IntBSTNode(source.key, source.left, source.right);

System.out.println(ego.key + ” Ego!”);

}

return source;

}

2003/11/24 03:53:11

コメントはまだありません

この質問への反応(ブックマークコメント)

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません