なんとな~くしあわせ?の日記

「そしてそれゆえ、知識そのものが力である」 (Nam et ipsa scientia potestas est.) 〜 フランシス・ベーコン

AOJ - ALDS1_7_A, B, C (木構造) を解いてみた

勝手に解いてろとか言わないで…

ALDS1_7_A, B, Cは、木構造(根付き木、二分木)です

根付き木 | アルゴリズムとデータ構造 | Aizu Online Judge
二分木 | アルゴリズムとデータ構造 | Aizu Online Judge
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge
木の復元 | アルゴリズムとデータ構造 | Aizu Online Judge

木構造を使うときの基本

まあ、木構造単体でプログラミングコンテストの問題が出されることはほとんど無さそうなのですが…*1

  • とりあえず、構造体 or クラスで以下のような型を作る
  • 木構造の1要素を1つのNodeというクラスで表現します。中には親要素のid、左と右の要素のidを持ちます。
  • Rubyの場合はStructを使うと楽にそういうのが作れる、Generics無しにそれを配列型にできるし
Node = Struct.new(:parent, :left, :right)
nodes = Array.new(N) { Node.new }

ALDS1_7_A - 根付き木

1つの節(ノード)に複数の子がくっつく場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_children ( id, nodes )

その接点の直下の子ノードを求める

ALDS1_7_B - 二分木

1つの節(ノード)に2つの子しかつかない場合の構造。

自分の回答

用意した関数を紹介しておく

get_depth ( id, nodes )

その接点の深さを求める

get_height ( id, nodes )

その接点の高さを求める、深さと逆のため再帰的にノードを求める必要がある(Finding height in Binary Search Tree - Stack Overflow)

get_sibling ( id, nodes )

その接点と同じ階層にあるノードを求める、二分木の場合隣接するものはあるかないか2択になる

ALDS1_7_C - 木の巡回

木の巡回には3種類あるという話。

  • 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
  • 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
  • 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます。

自分の回答

用意した関数を紹介しておく

pre_parse ( root, nodes )

根節点、左部分木、右部分木の順で節点の番号を出力する

in_parse ( root, nodes )

左部分木、根節点、右部分木の順で節点の番号を出力する

post_parse ( root, nodes )

左部分木、右部分木、根節点の順で節点の番号を出力する

使用例?

単純な木構造って、実務でも競プロでも使うことが稀な気がする。すごい単純なデータが問題で、なおかつ階層がキーになる場合に使えばいいのかな?いい問題があれば追記します。

追記: 木構造の問題です

A Rational Sequence 2 – Kattis, Kattis

*1:木構造よりも、それの発展系のグラフアルゴリズムの出題が多そう