テクノロジー編25: データ構造

子節点を再帰的に探索していく方法。
迷路を探索する際に、 1 つの道を進んでいき、行き止まりにぶつかったら引き返して別の道を進むイメージ。
一般にスタックや再帰関数を用いて実装される。
メモリの使用量が比較的少ないものの、実装を誤ると無限ループに陥る場合がある。

DFS の一種で、「自分、左の子、右の子」の順番で記録する。
トポロジカル順が保たれる。
木のコピーを作成する際に便利。

DFS の一種で、「左の子、右の子、自分」の順番で記録する。
数式の構文木から逆ポーランド記法の数式を得たり、木の削除をおこなったりする際に便利。

逆ポーランド記法について: 情報処理入門 テクノロジー編03 chapter 3
https://paiza.jp/works/technology/primer/beginner-technology3/79202

DFS の一種で、「左の子、自分、右の子」の順番で記録する。
2 分探索木において、節点の値を昇順に得ることができる。

深さが浅い節点から順に探索していく方法。
水面に石が落ちたときの波紋の広がり方に近いイメージ。
キューを用いて実装される。
一般には DFS と比べるとメモリを多く消費するが、最短経路問題に応用することができる。