VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
321(5): ピッコロ ◆YAZTByPXwc6o 2019/02/19(火)23:10 ID:hrS7nHTV(8/8)調 AAS
ところでご質問させていただきたく
https://light.dotup.org/uploda/light.dotup.org575301.png
このような二分木があった場合に
ノードをたどって1 2 3 4 5 6 7という
順番に値を出力したく、これを再帰を使わずに実装したく
どのように実装すればよいでしょうか
皆様のお知恵を拝借したく
教えていただきたく
よろしくお願いします
326: 2019/02/19(火)23:16 ID:T0Xa9ami(5/8)調 AAS
>>321
ピラフの命の輝きを見よ!!
https://gist.github.com/kingpilaf/
https://gist.github.com/sleeping-marple/
https://gist.github.com/MistyBloom/
_,ｌ;;;;;;;;;;;;;l,,_
,.ｒ'´;: 八 '::..ﾞヽ
,.'＿＿_ _立_ _＿;;ミﾞ;、 フT
l厄巳厄 i王i ,.巳厄巳ｌ 夕 ヒ
,.-'l i,.:' ヽ:.、 ;.:' ' ヽ |,.、
/{´ｉY´ヾｰtｯ-ヽ'' ｋｰtr-,'´lri ＿l＿
{_i,入::.. ｀￣￣,'i!ヽ;｀￣´ ﾞ::.}rﾘ ｉ,＿
ヽ_ﾉiヾ ;:. ＿ i': ll!:,ｨ .＿ .: j,ノ
ｯｼﾞ::;;| ,r'´;;:＞￣弋´;;::ヽ;r1:ﾞ'ｲｨ ┬‐宀
弍::::::::l i':;r'´ ,.-ｰｰ-､.ヾ;:;i. |:::::::ｽ ﾉ□隹
彡;:::ｌ l::l ' ---;:, ﾞ l::l |::;;ｬ` 、
,r',广ヽl::l ::. .: ﾞ:. l:lﾉ^i`､ 三刃
,ｲ（:::j i::iヽ :. .: ／l:l'" l:ヽヽ 口心
|;:;.＼＼ l::l ', :;:::..::. / l:l,r''／;::;;|
333(21): 2019/02/20(水)02:40 ID:B2QSVSiS(1/5)調 AAS
>>321
すべてのノードについて、左の子以下の数は、自分の数よりも小さく、
右の子以下の数は、自分の数よりも大きくなる
これは普通の2分探索木で、
C++ のSTL にある、map・set というコンテナだろ
でも皆、再帰を使って実装しているのでは？
再帰を使わない方法は、思いつかない
346(1): 333 2019/02/20(水)23:54 ID:B2QSVSiS(5/5)調 AAS
二分木
https://ja.wikipedia.org/wiki/%E4%BA%8C%E5%88%86%E6%9C%A8
行きがけ順、通りがけ順、帰りがけ順探索[編集]
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。
従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。
根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、
部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、
片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。
二分探索木では通りがけ順探索は、ノードを大きさ順（あるいは大きさの逆順）に調べることになる。
>>321
は、通りがけ順でしょ
ところで、ピラフ大王は、ピッコロ大魔王になったのですか？
354: 333 2019/02/21(木)08:40 ID:JBRYA9bz(3/4)調 AAS
順位キュー(優先度付きキュー、priority queue)は、ダイクストラ・A* で使っている。
確か、2分ヒープと同じで、最小値だけがtop に来る。
他のノードの関係は、保証されないのだったかな？
>>321
の図で説明すると、
まず、4に来るとキューに、[4, 2, 6] を追加すると、[2, 4, 6]となる
削除しないで、peek だけすると、最小は2なので、2へ行き、[1, 3] を追加すると、[1, 2, 4, 6, 3]となる
そこでpeekすると、最小は1なので、1へ行き、追加するものはないので、
1をpop して、peekすると、最小は2なので、2へ戻り、
2をpopして、peekすると、最小は3なので、3へ行き、追加するものはないので、
3をpopして、peekすると、最小は4なので、4へ戻り、追加するものはないので、
4をpopして、peekすると、最小は6なので、6へ行き、[5, 7] を追加すると、[5, 6, 7]となる
そこでpeekすると、最小は5なので、5へ行き、追加するものはないので、
5をpopして、peekすると、最小は6なので、6へ戻り、
6をpopして、peekすると、最小は7なので、7へ行き、追加するものはないので、
7をpopすると、キューが空
プログラミング・コンテスト・チャレンジブック、第2版、2012
言語は、C++で、ほとんど全てのアルゴリズムを網羅。
問題数も多く、パズル感覚で楽しめる。
AIやシミュレーションゲームの参考になる
359(1): 333 2019/02/22(金)06:28 ID:43iXBVf1(1/2)調 AAS
順位キューではなく、スタックで考えてみた
>>321
の図で説明すると、
まず、4に来ると、スタックに大きい方から、[6, 4, 2] をpush する
削除しないで、末尾をpeek だけすると、最小は2なので、2へ行き、
一旦、2をpop してから、[3, 2, 1] をpushすると、[6, 4, 3, 2, 1]となる。
(一旦、2をpopして、順番を変えるのがミソ)
そこでpeekすると、最小は1なので、1へ行き、追加するものはないので、
1をpop して、peekすると、最小は2なので、2へ戻り、
2をpopして、peekすると、最小は3なので、3へ行き、追加するものはないので、
3をpopして、peekすると、最小は4なので、4へ戻り、追加するものはないので、
4をpopして、peekすると、最小は6なので、6へ行き、
一旦、6をpop してから、[7, 6, 5] をpushすると、[7, 6, 5]となる
そこでpeekすると、最小は5なので、5へ行き、追加するものはないので、
5をpopして、peekすると、最小は6なので、6へ戻り、
6をpopして、peekすると、最小は7なので、7へ行き、追加するものはないので、
7をpopすると、スタックが空
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.040s