VBSで便利なプログラムを作れスレ 2 (853ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡
321(5): ピッコロ ◆YAZTByPXwc6o 2019/02/19(火)23:10 ID:hrS7nHTV(8/8) AAS
ところでご質問させていただきたく
画像ﾘﾝｸ[png]:light.dotup.org
このような二分木があった場合に
ノードをたどって1 2 3 4 5 6 7という
順番に値を出力したく、これを再帰を使わずに実装したく
どのように実装すればよいでしょうか
皆様のお知恵を拝借したく
省2
326: 2019/02/19(火)23:16 ID:T0Xa9ami(5/8) AAS
AA省
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
二分木
外部ﾘﾝｸ:ja.wikipedia.org
行きがけ順、通りがけ順、帰りがけ順探索[編集]
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。
従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。
根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、
部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、
省5
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]となる
省13
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して、順番を変えるのがミソ)
省10
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.031s