Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の7_C問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#7「木構造」では、根付き木、二分木について紹介します。
問題（7_C: Tree Walk）
問題はリンク先をご覧ください。
木の巡回方法をいくつか試します。
頂点の巡回方法について
この問題では、すべての頂点を巡回するアルゴリズムとして3種類紹介しています。以下は、問題文から引用しました。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C
- 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
- 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
- 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます
入力例1の木構造を図示すると以下となります。この画像は、7_B問題から引用させていただきました。
先行順巡回は、0→1→2→3→4→5→6→7→8 となります。
中間順巡回は、2→1→3→0→6→5→7→4→8 となります。
後行順巡回は、2→3→1→6→7→5→8→4→0 となります。
C++ プログラム例（ALDS1 7_C）
7_B問題で作成したプログラムをベースにします。ただし、頂点の親や深さや高さを出力する必要がなくなっているため、構造は簡単になっています。
基本的な構造は以下となります。
- 関数 xxx_dfs で巡回する順番を定めます。配列 order に巡回する頂点の順番を格納します。
- 先行順巡回を処理する pre_dfs、中間順巡回を処理する in_dfs、後行順巡回を処理する post_dfs は、order に格納するコードの場所が異なるだけです（18、32、46行目）。
以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;
typedef struct {
int parent;
int left;
int right;
} binary_tree;
vector<binary_tree> G;
vector<int> order;
void pre_dfs(int v)
{
order.push_back(v);
if (G[v].left != -1) {
pre_dfs(G[v].left);
}
if (G[v].right != -1) {
pre_dfs(G[v].right);
}
}
void in_dfs(int v)
{
if (G[v].left != -1) {
in_dfs(G[v].left);
}
order.push_back(v);
if (G[v].right != -1) {
in_dfs(G[v].right);
}
}
void post_dfs(int v)
{
if (G[v].left != -1) {
post_dfs(G[v].left);
}
if (G[v].right != -1) {
post_dfs(G[v].right);
}
order.push_back(v);
}
int main()
{
int n;
cin >> n;
G.resize(n);
set<int> root;
for (int i = 0; i < n; ++i) {
root.insert(i);
}
for (int i = 0; i < n; ++i) {
int id, left, right;
cin >> id >> left >> right;
G[id].left = left;
if (left != -1) {
G[left].parent = id;
root.erase(left);
}
G[id].right = right;
if (right != -1) {
G[right].parent = id;
root.erase(right);
}
}
int r = *(root.begin());
order.clear();
pre_dfs(r);
cout << "Preorder" << endl;
for (int i = 0; i < n; ++i) {
cout << " " << order[i];
}
cout << endl;
order.clear();
in_dfs(r);
cout << "Inorder" << endl;
for (int i = 0; i < n; ++i) {
cout << " " << order[i];
}
cout << endl;
order.clear();
post_dfs(r);
cout << "Postorder" << endl;
for (int i = 0; i < n; ++i) {
cout << " " << order[i];
}
cout << endl;
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
先行順巡回と後行順巡回は、競技プログラミングの問題でも問われることがあります。先行順巡回は頂点を始めて訪れた順を、後行順巡回は頂点を去った順を表します（配列 order を更新するコードの位置もそうなっています）。
引き続き、ALDS1 の問題を紹介していきます。
