- 締切済み
4分木の探索プログラミングについて
全零で初期化した二次元配列の要素の値を ある条件を満たすまで再帰的に処理して値を返していくような プログラムを書いています そこで４分木を使わなければならなくなりました。 4分木の参考サイトが少ないのでアルゴリズムがわからないのですが 二分木の拡張版のようなもので複雑な再帰処理が必要になるでしょうか。
- wanimaru7101
- お礼率14% (1/7)
- C・C++・C#
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
みんなの回答
- chelsea-chan
- ベストアンサー率50% (1/2)
- kmee
- ベストアンサー率55% (1857/3366)
その4分木でどんな処理したいかによるでしょう。 基本は一緒です。 二分木で左右の子に対して処理するように、4分木の各子に対して処理すればいいわけです。
補足
なんとなくイメージがつかめたので コーディングしてみます。 ありがとうございます。
関連するQ&A
- 二分探索木を用いての探索
Ｃ言語でプログラミングしています。 二分探索木を用いて探索するプログラムなのですが 与えられた値の前後の値（与えられた値より大きく(小さく）てその値 に一番近いもの）を見つけたいのですが分かりません。 いろいろとネット等で調べてみると「挿入してその左右を見る」 となっているのですが…。 普通の二分探索木ではだめなのでしょうか？ よろしくお願いします。
- 締切済み
- C・C++・C#
- アルゴリズム(2分探索木)の問題について
２分探索木のアルゴリズムに関する問題について質問させていただきます。 [問題] 集合Sに対する2文探索木とは、ラベルつきの2分木で、 その頂点vにはSのある要素l(v)がラベルとしてつけられている。 l(v)は次の性質を満たす。 １．vの左部分木の頂点uに対して l(u) < l(v) 2．vの右部分木の頂点uに対して l(u) > l(v) 3．Sの任意の要素aに対して l(v) = a となる頂点vはちょうどひとつある。 図はキーワード集合{begin,else,end,if,then}をあらわす2分探索木の例である。 いま、集合Sを表す2分探索木と要素aが与えられているときa∈Sならば"はい"、 そうでなければ"いいえ"を出力するアルゴリズムを考える。 このアルゴリズムは、木の根rについて一回だけ再帰手続きSEARCH(a,r)を呼び出せばよい。 ただし、SEARCH(a,v)はvを根とする部分木中に要素aが含まれているかを判定する。 含まれているときに値"はい"を、そうでなければ値"いいえ"を返す。 ・アルゴリズム procedure SEARCH(a,v): if a = l(v) then return "はい" else if a < l(v) then if vが左の子wを持つ then return SEARCH( ア ) else return "いいえ" else イ 以下の問題に答えよ。 (1) 上のアルゴリズムのア,イを埋めよ。 (2) 上のアルゴリズムを参考にして、集合Sからのデータの削除DELETE(a,S)を考える。 削除すべき要素aが頂点vのラベルであったとする。そのとき次の3つの場合について、行うべき操作を記述せよ。 (i) 頂点vが葉である (ii) 頂点vの子が1個ある (iii) 頂点vの子が2個ある 以上です。 設問(1)は解けました。 答えは ア: a,w イ: a > l(v) then if vが右の子wを持つ then return SEARCH(a,w) else return "いいえ" になるのではないかと思います。 設問(2)についてなのですが、それぞれの場合について、どのような操作をすればよいのかは、 参考書などを読んで理解したのですが、どのように記述したらよいかがわかりません。 長文になってしまい申し訳ないのですが、回答よろしくお願いいたします。
- ベストアンサー
- その他（プログラミング・開発）
- 二分探索木のheight(高さ?)を見つけるアルゴリズム
Binary Search Tree(=二分探索木)のheight(高さ?)を見つけるメソッドを作りたいのですが、 そのアルゴリズムが頭にうまく浮かびません。 まず思いついたのは一つ一つのNode(=ノード)をそれぞれのLeaf(=リーフ、葉?)まで辿っていって それらのheightを全部記憶させておいて後で比較するという…最も原始的な方法です。 しかし、Treeの大きさも未知なので用意する変数の数も未知になって どう考えても不適当でしょう(当たり前か(^^ゞ)。 Recursion(=再帰)を使えばいいのでしょうか? そうだとしてもどうすればいいのか…。 アルゴリズムがパッと浮かぶ方、どうか教えて下さい。
- ベストアンサー
- Java
- Cのプログラミングについての質問です
全零で任意のサイズの二次元配列を用意して、その中の要素の一つをランダムに選んで1に初期化する。 その選んだ要素の上下左右どれか一つをランダムに選んで1に初期化する。 再び1に初期化した要素を選んだら今度は0に初期化する。 以上の処理を任意の回数繰り返して、1同士が必ず上下左右で隣接してる配列を生成したいのですが、 どのように書いたら実現できるでしょうか。
- 締切済み
- C・C++・C#
- 線形と二分探索により探索を行うプログラムについて教えてください
２０個の配列にデータを入れ（プログラム内で初期化と代入を行って良い）入力した数を探索するプログラムをCmachineで作成したいのですが、線形探索により探索を行うプログラムと二分探索により探索を行うプログラムの作り方を教えていただけないでしょうか？
- 締切済み
- C・C++・C#
- C言語 2分木探索について質問です
Ｃ言語初心者です。 2分木構造体 struct node{ int data; Tree left_subtree; Tree right_subtree; } を上記のように定義した場合、 2分木の根節点のポインタ struct node *Tree を引数として与えられたとき、 2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t);を再帰呼び出しで作成してみたのですが、正しいでしょうか？ ■2分木内の節点に保持された整数データの総和を戻り値として返す関数 int sum_data(Tree t) { // 左分木、右分木のどちらも存在しなければ根節点の値を返す if ((t->left_subtree == NULL) && (t->right_subtree == NULL)) { return t->data; } else// どちらか存在していれば再帰呼び出しする { return (t->data + sum_data(t->left_subtree) + sum_data(t->right_subtree)) } } ご指摘ありましたら、お願いしますm(_ _)m
- ベストアンサー
- C・C++・C#
- ２分木の配列
次の表の２分木を配列で表現したものである、２分木の図示について教えてください。 （配列の説明） ・数値は説（ノード）の値である。 ・ポインタ１欄は左の子（左部分木）の添付を表し、値が０のときは左の子が存在しないことを意味する。ポインタ２欄は右の子（右部分木）の添付を表し、値が０の時は右の子が存在しないことを意味する。 ・木の根は値Ａである 添字 値 ポインタ１ ポインタ２ １ Ａ ２ ３ ２ Ｂ ０ ４ ３ Ｃ ５ ０ ４ Ｄ ０ ０ ５ Ｅ ６ ７ ６ Ｆ ０ ０ ７ Ｇ ０ ０
- ベストアンサー
- その他([技術者向] コンピューター)
- プログラミング分かりませんJAVA
キーボードから数値をにゅうりょくし配列変数のじを指定することで、配列要素の値を標示するプログラムを作成する問題です 配列は次のように初期化 int data[]={1,2,3,4,16,32,64,128,256,512} 実行結果 字＞０ ０番目の値は１ 字＞９ ９番目の値は５１２ 字＞５ ５番目の値は３２
- 締切済み
- Java
- ２次元配列のマスを数える方法を教えてください！！
C++において、２次元配列の要素で上下左右に連続して塗り潰されている集まりをカウントする方法を教えてください！！ 10*10の２次元配列を用意して、上下左右に連続して塗り潰されている集まりを関数の再帰処理を用いてカウントするプログラムを作りたいのですがわかりません。 問題例 ◇◆◇◇◇◆◇◆ ◆◆◇◆◇◇◇◆ ◇◇◇◆◆◆◇◆ この場合集まりは4です! 配列はstring型で多バイトの文字をカウントします。 回答お願いします！！
- 締切済み
- C・C++・C#
- ２次元配列のマスを数える方法を教えてください！！
C++において、２次元配列の要素で上下左右に連続して塗り潰されている集まりをカウントする方法を教えてください！！ 10*10の２次元配列を用意して、上下左右に連続して塗り潰されている集まりを関数の再帰処理を用いてカウントするプログラムを作りたいのですがわかりません。 問題例 ◇◆◇◇◇◆◇◆ ◆◆◇◆◇◇◇◆ ◇◇◇◆◆◆◇◆ この場合集まりは4です! 配列はstring型で多バイトの文字をカウントします。 回答お願いします！！
- 締切済み
- C・C++・C#
補足
場合によって子の数が変わるので、たぶんB木なのかもしれません。ありがとうございます