勝手に解いてろとか言わないで…
ALDS1_7_A, B, Cは、木構造（根付き木、二分木）です
根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge
二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge
木構造を使うときの基本
まあ、木構造単体でプログラミングコンテストの問題が出されることはほとんど無さそうなのですが…*1
- とりあえず、構造体 or クラスで以下のような型を作る
- 木構造の１要素を１つのNodeというクラスで表現します。中には親要素のid、左と右の要素のidを持ちます。
- Rubyの場合はStructを使うと楽にそういうのが作れる、Generics無しにそれを配列型にできるし
Node = Struct.new(:parent, :left, :right) nodes = Array.new(N) { Node.new }
ALDS1_7_A - 根付き木
１つの節（ノード）に複数の子がくっつく場合の構造。
用意した関数を紹介しておく
get_depth ( id, nodes )
その接点の深さを求める
get_children ( id, nodes )
その接点の直下の子ノードを求める
ALDS1_7_B - 二分木
１つの節（ノード）に２つの子しかつかない場合の構造。
用意した関数を紹介しておく
get_depth ( id, nodes )
その接点の深さを求める
get_height ( id, nodes )
その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree - Stack Overflow)
get_sibling ( id, nodes )
その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか２択になる
ALDS1_7_C - 木の巡回
木の巡回には３種類あるという話。
- 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
- 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
- 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。
用意した関数を紹介しておく
pre_parse ( root, nodes )
根節点、左部分木、右部分木の順で節点の番号を出力する
in_parse ( root, nodes )
左部分木、根節点、右部分木の順で節点の番号を出力する
post_parse ( root, nodes )
左部分木、右部分木、根節点の順で節点の番号を出力する
