人力検索はてな
モバイル版を表示しています。PC版はこちら
i-mobile

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

●質問者: donataka
●カテゴリ:コンピュータ 学習・教育
✍キーワード:C++ Java object TREE アルゴリズム
○ 状態 :終了
└ 回答数 : 1/1件

▽最新の回答へ

1 ● sasada
●40ポイント

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のような感じです。

http://aglaia.c.u-tokyo.ac.jp/~yamamoto/Programming/alg_data/nod...

以下、おまけです。

http://www-lab09.kuee.kyoto-u.ac.jp/~xieq/intern/algorithm.html

http://www.fc.u-tokai.ac.jp/~oki/98/nibungi/40nibun.html

二分探索木の挿入

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

http://www.gihyo.co.jp/books/syoseki-contents.php/4-7741-1632-7

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

◎質問者からの返答

ようやく出来ました。

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;

}

関連質問


●質問をもっと探す●



0.人力検索はてなトップ
8.このページを友達に紹介
9.このページの先頭へ
対応機種一覧
お問い合わせ
ヘルプ/お知らせ
ログイン
無料ユーザー登録
はてなトップ