C++で木の巡回を実装する

木構造を持つデータを探索するアルゴリズムに、木の巡回と呼ばれるものがあります。今回は３種類の木の巡回を取り上げ、それらを実装してみます。

木の巡回

木の巡回とは、ある木に属する全てのノードを順番に１回づつ訪問するアルゴリズムのことを指します。木の巡回にはいくつかの方法があります。今回は３つ紹介します（いずれも深さ優先探索と呼ばれる方法に属するものです）。

木の巡回順序

• 先行順巡回（Preorder Tree Walk）：根→左部分木→右部分木

• 中間順巡回（Inorder Tree Walk）：左部分木→根→右部分木

• 後行順巡回（Postorder Tree Walk）：左部分木→右部分木→根

例を見てみましょう。次のような木を考えます。

この木に対して、それぞれの方法で巡回すると、各ノードは次のような順番で訪問されることになります。

• 先行巡回順：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

中間巡回順、後行巡回順についてはちょっとわかりづらいかもしれません。そういうときは、木が再帰的な構造を取っていることを再確認してみるとよいと思います。例えば、ノード１、２、３から成る部分木は、１を根とする木になっています。

問題を解いてみる

Aizu Online Judgeの問題を解きます。
木の巡回 | アルゴリズムとデータ構造 | Aizu Online Judge

上で紹介した３つの巡回アルゴリズムを、preorder, inorder, postorderという再帰関数を用いて実装しています。いずれも根から葉に向かって進み、葉に当たったら戻るという操作を行っています。違いは出力のタイミングです。気をつけてください。
また、各ノードの情報をNode構造体で保持します。ノードが存在しないときは、値をNILとしておきます。

#include<iostream>
using namespace std;

#define NIL -1  // ノードが存在しないことを示す

struct Node {
  int parent, left, right;   // 親、左の子、右の子
};

void preorder(Node T[], int id) {
  if (id == NIL) return;
  cout << " " << id;
  if (T[id].left != NIL) preorder(T, T[id].left);
  if (T[id].right != NIL) preorder(T, T[id].right);
}

void inorder(Node T[], int id) {
  if (id == NIL) return;
  if (T[id].left != NIL) inorder(T, T[id].left);
  cout << " " << id;
  if (T[id].right != NIL) inorder(T, T[id].right);
}

void postorder(Node T[], int id) {
  if (id == NIL) return;
  if (T[id].left != NIL) postorder(T, T[id].left);
  if (T[id].right != NIL) postorder(T, T[id].right);
  cout << " " << id;
}

int main() {
  int i, n, id, left, right;
  Node T[25];

  cin >> n;

  // 初期化
  for (i = 0; i < n; i++) {
    T[i].parent = NIL;
    T[i].left = NIL;
    T[i].right = NIL;
  }

  for (i = 0; i < n; i++) {
    cin >> id >> left >> right;
    T[id].left = left;
    T[id].right = right;
    T[left].parent = id;
    T[right].parent = id;
  }

  // rootを探す
  int root = 0;
  for (i = 0; i < n; i++) {
    if (T[i].parent == NIL) {
      root = i;
      break;
    }
  }

  cout << "Preorder" << endl;
  preorder(T, root);
  cout << endl;

  cout << "Inorder" << endl;
  inorder(T, root);
  cout << endl;

  cout << "Postorder" << endl;
  postorder(T, root);
  cout << endl;
  
  return 0;
}

この木に対応する入力は、

9
0 1 4
1 2 3
2 -1 -1
3 -1 -1
4 5 8
5 6 7
6 -1 -1
7 -1 -1
8 -1 -1

出力は

Preorder
 0 1 2 3 4 5 6 7 8
Inorder
 2 1 3 0 6 5 7 4 8
Postorder
 2 3 1 6 7 5 8 4 0

となり、正しい結果が得られています。

まとめ

二分木の各ノードを訪問するプログラムを実装しました。探索アルゴリズムの初歩といったところでしょうか。
次は木の巡回に関数に関する問題を解いてみようと思います。

参考

渡部有隆. プログラミングコンテスト攻略のためのアルゴリズムとデータ構造. Ozy, 秋葉拓哉協力. 株式会社マイナビ. 2015.