数式が読み込まれない場合は1回再読み込みしてみてください。基本情報-テクノロジ系-データ構造とアルゴリズムこんにちは、ももやまです。木構造にある各ノードを1度だけ訪問することを探索(走査)と呼びます。深さ優先探索(DFS)幅優先探索(BFS)の2つとなります。postorder)の3つに分けることができます*1。2つで実際に(木以外のグラフなどを)探索した場合にどのような順番で探索できるかについてはこちらの記事にまとめているのでもし興味があればご覧ください。行きがけ順とは行きがけ順は、「最初にノードを訪問する」タイミングが早い順に各ノードを探索していく方式です。右側のノードに移動の順で探索を行います。先に進めなくなったときは、1つ戻って探索できるノードがあるか探します。根まで戻ったときに探索できるノードがなくなったときが探索終了です。上の木構造の場合、行きがけ順による探索の過程は、まず15を訪問し、左側へ10を訪問し、左側へ4を訪問、左右両方なくなったので、1つ戻り10の右側をチェック14を訪問、左側へ12を訪問、左右両方なくなったので、3つ戻り15の右側をチェック19を訪問、左側へ17を訪問、全ノードチェック完了のようになります。行きがけ順を正しく求める魔法の一筆書き試験ではよく「行きがけ順」を求めさせる問題が出題されます。そこで、今回は簡単に行きがけ順を求めるテクニックを紹介したいと思います。下のように根からすべてのノードを反時計回りするように一筆書き(緑の線)をします。下のように再帰を用いることで簡単に記述することができます。木構造の根を指すポインタです。通りがけ順とは通りがけ順は、途中(左側のノードに移動できなくなったタイミング)でノードを訪問するタイミングが早い順に各ノードを探索していく方式です。右側のノードに移動の順で探索を行います。行きがけ順と同じように先に進めなくなったときは、1つ戻って探索できるノードがあるか探します。根まで戻ったときに探索できるノードがなくなったときが探索終了です。右側へ行き、さらに左側へ行き、17を出力(19は左側に行けるため出力できない)1つ戻り19を出力、全ノード出力完了のようになります。通りがけ順を正しく求める魔法の一筆書き「通りがけ順(中間順)」も一筆書きの魔法のテクニックで簡単に求めることができちゃいます!まず、行きがけ順と同じように下のように根からすべてのノードを反時計回りするように一筆書き(緑の線)をします。一筆書きをしたときに、ノードの下側(黄丸部分)を通った順番がなんとそのまま通りがけ順となります!なお2分探索木の場合、通りがけ順は必ずデータの昇順となるので必ず頭に入れておきましょう。cなどの文字になった2分探索木が出題されることがあります。通りがけ順の求め方(魔法の一筆書き)も頭にいれておきましょう。下のように再帰を用いることで簡単に記述することができます。木構造の根を指すポインタです。帰りがけ順とは帰りがけ順は、最後(左右両方のノードに移動できなくなったタイミング)にノードを訪問するタイミングが早い順に各ノードを探索していく方式です。移動できなくなったデータ出力の順で探索を行います。行きがけ順、通りがけ順と同じように先に進めなくなったときは、1つ戻って探索できるノードがあるか探します。根まで戻ったときに探索できるノードがなくなったときが探索終了です。帰りがけ順を正しく求める魔法の一筆書き「帰りがけ順(後行順)」も一筆書きの魔法のテクニックで簡単に求めることができちゃいます!まず、行きがけ順、通りがけ順と同じように下のように根からすべてのノードを反時計回りするように一筆書き(緑の線)をします。下のように再帰を用いることで簡単に記述することができます。木構造の根を指すポインタです。幅優先探索とは幅優先探索は、深さごとに浅い順かつ左側から探索していく方式です。そのため、探索開始地点に近い点からまんべんなく探索が行われます。幅優先探索で走査を行うプログラム幅優先探索での走査は、深さ優先探索のように再帰を用いたプログラムでは表現できないので、下のようなデータ構造「キュー」を使って表現します*2。;さらに、下のようにキューの操作関数を用意します。下のように書くことができます。}}6.練習問題では、2問ほど2分探索木の走査練習をしてみましょう。練習1つぎの2分探索木がある。幅優先探索による走査したときにノードを走査する順番を答えなさい。練習22分木の走査の方法には、その順序によって次の三つがある。前順:節点,左部分木,右部分木の順に走査する。間順:左部分木,節点,右部分木の順に走査する。後順:左部分木,右部分木,節点の順に走査する。図に示す2分木に対して前順に走査を行い,節の値を出力した結果はどれか。午前問12]ア:abchidefjgkイ:abechidfjgkウ:hcibdajfegkエ:hicdbjfkgeaおまけ:間順(通りがけ順)、後順(帰りがけ順)、幅優先探索による走査もやってみよう!7.練習問題の答え練習1魔法の一筆書きで順番を求めていきましょう。9魔法の一筆書きをしたときにノードの左側を通る順番がそのまま行きがけ順。9魔法の一筆書きをしたときにノードの下側を通る順番がそのまま通りがけ順。通りがけ順を求めたときは解答が昇順になっていることを確かめること。2魔法の一筆書きをしたときにノードの右側を通る順番がそのまま通りがけ順。6深さごと(浅いところが先)に左側から順番に探索したものが幅優先探索。k)練習1と同じく魔法の一筆書きで前順(行きがけ順)を求めていきましょう。よって答えはアとなる。k魔法の一筆書きをしたときにノードの下側を通る順番がそのまま間順(通りがけ順)。a魔法の一筆書きをしたときにノードの右側を通る順番がそのまま後順(帰りがけ順)。k深さごと(浅いところが先)に左側から順番に探索したものが幅優先探索。8.さいごに今回は2分探索木の4つの走査方法についてまとめていきました。行きがけ順、通りがけ順、帰りがけ順は、すべてのノードを反時計周りで囲って、特定の位置を通過する順番がそのまま走査順なるのでぜひ覚えておきましょう!次回は基本的なソートアルゴリズムについてまとめていきたいと思います。*1:行きがけ順、通りがけ順、帰りがけ順の説明なしにいきなり「深さ優先探索」と言われた場合は、(必ず根からスタートする)行きがけ順を指していると思ってもらってOKです。システムオートマトンPrologCLOSEサイト内検索を行います。はてなブログPro数学と情報が得意な大学生です。累計:リアルタイム現在の閲覧者数:。