【C++】再帰を使わない二分木の中順（Inorder）トラバーサルの実装方法

二分木を中順（Inorder）でトラバースするとは、まず左部分木を訪問し、次にルート（根）ノード、最後に右部分木を訪問する手法のことです。特に二分探索木（BST）に対して中順トラバーサルを行うと、キーが昇順に出力されるという重要な性質があります。本記事では、再帰を使わずにスタックを活用して中順トラバーサルを実装するC++プログラムを紹介します。

アルゴリズム

再帰を使わない中順トラバーサルは、明示的なスタックを用いて以下の手順で実現します。

Begin
    Function inOrder():
        スタック s を宣言する
        現在のノード current を root に設定する
        current が NULL でない かつ スタックが空でない 間、以下を繰り返す
            current が NULL でない間、以下を繰り返す
                current をスタックの先頭にプッシュする
                左の子ノードを current に設定する
            current をスタックの先頭ノードに設定する
            スタックの先頭ノードをポップする
            current の値を出力する
            右の子ノードを current に設定する
    ルート・左ノード・右ノードに要素を挿入して木を構築する
    inOrder() を呼び出して木をトラバースする
End.

サンプルコード

#include<bits/stdc++.h>
using namespace std;

struct n {
    int d;
    struct n* l;
    struct n* r;
    n (int d) {
        this->d = d;
        l = r = NULL;
    }
};

void inOrder(struct n *root) {
    stack<n *> s;
    n *current = root;

    while (current != NULL || s.empty() == false) {
        while (current != NULL) {
            s.push(current);
            current = current->l;
        }

        current = s.top();
        s.pop();

        cout << current->d << " ";
        current = current->r;
    }
}

int main() {
    struct n *root = new n(7);

    root->l = new n(6);
    root->r = new n(2);
    root->l->l = new n(1);
    root->l->r = new n(9);

    inOrder(root);
    return 0;
}

コードの解説

このプログラムでは、再帰呼び出しの代わりにスタックがトラバーサルの状態を管理します。処理の流れは以下のとおりです。

1. 現在のノードから左方向へ進みながら、通過したノードをすべてスタックにプッシュしていきます。
2. 左端に到達したら、スタックの先頭からノードをポップし、その値を出力します。
3. ポップしたノードの右部分木へ移動し、スタックが空になるまで同じ処理を繰り返します。

再帰では呼び出しスタックが暗黙的に「戻るべきノード」を記憶していましたが、この実装ではそれを明示的なスタックで代替しています。そのため、深い木を扱う場合でも呼び出しスタックのオーバーフローを気にせずにトラバースできるのが利点です。

実行結果

1 6 9 7 2

このサンプルコードで構築される二分木は次の構造です。

        7
       / \
      6   2
     / \
    1   9

中順トラバーサルは「左 → 根 → 右」の順でノードを訪問するため、出力は「1 → 6 → 9 → 7 → 2」となります。