Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の7_D問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#7「木構造」では、根付き木、二分木について紹介します。
問題（7_D: Reconstruction of a Tree）
問題はリンク先をご覧ください。
AOJ ALDS1 7_D問題: Reconstruction of a Tree
先行順巡回と中間順巡回の頂点の列から、後行順巡回の列を求めます。
頂点の巡回方法について
7_C問題の問題文で、以下の定義が紹介されました。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/7/ALDS1_7_C
- 根節点、左部分木、右部分木の順で節点の番号を出力する。これを木の先行順巡回 (preorder tree walk) と呼びます。
- 左部分木、根節点、右部分木の順で節点の番号を出力する。これを木の中間順巡回 (inorder tree walk) と呼びます。
- 左部分木、右部分木、根節点の順で節点の番号を出力する。これを木の後行順巡回 (postorder tree walk) と呼びます
Preorder は、根→左部分木→右部分木 の順に巡回します。Inorder は、左部分木→根→右部分木 の順に巡回します。Preorder の最初の要素は木構造全体の根となります。この要素の値を Inorder から探すと、全体の木を、左部分木と右部分木に分割することができます。その左部分木と右部分木を再帰的に走査して、最後に根を出力すると、Postorder の巡回が復元できます。
上記の手順は、以下の擬似コードで実現できます。[L, R) と半開区間で処理をしています。
以下の擬似コードを実装する。
dfs(L, R)
if L >= R
return
c = next_preorder() // Preorder での次の節点
m = inorder.find(c) // Inorder における c の位置
dfs(L, m)
dfs(m + 1, R)
print c // Postorder で c を出力C++ プログラム例（ALDS1 7_D）
上記の擬似コードをそのまま実装しました。以下が、C++プログラムとなります。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n;
int pos;
vector<int> pre, in, post;
void dfs(int L, int R)
{
if (L >= R) {
return;
}
int root = pre[pos];
++pos;
int m = find(in.begin(), in.end(), root) - in.begin();
dfs(L, m);
dfs(m + 1, R);
post.push_back(root);
}
int main()
{
cin >> n;
for (int i = 0; i < n; ++i) {
int pos;
cin >> pos;
pre.push_back(pos);
}
for (int i = 0; i < n; ++i) {
int pos;
cin >> pos;
in.push_back(pos);
}
pos = 0;
dfs(0, n);
for (int i = 0; i < n; ++i) {
cout << post[i] << " \n"[i == n - 1];
}
return 0;
}上記プログラムは、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
トピック#7では、木構造、特に頂点の巡回順序について学ぶことができました。
引き続き、ALDS1 の問題を紹介していきます。
