【C++】再帰を使わずに二分木を中順走査（In-order Traversal）するプログラム

二分木を中順（In-order）で走査する場合、まず左の部分木を訪問し、次に根（ルート）、最後に右の部分木を訪問します。中順走査では、キーが昇順に出力されるという特徴があります。この記事では、再帰を使わずに二分木を中順走査するC++プログラムを紹介します。

非再帰中順走査の仕組み

再帰を使わない中順走査では、スタックを利用します。大まかな手順は以下のとおりです。

1. 現在のノードがNULLになるまで、ノードをスタックにpushしながら左の子へ移動します。
2. 左端に到達したら、スタックの先頭ノードをpopしてその値を出力します。
3. 取り出したノードの右の子へ移動し、スタックが空かつ現在のノードがNULLになるまで1〜2を繰り返します。

アルゴリズム

Begin
    構造体 n を宣言する。
        整数型のメンバ d を宣言する。
        構造体 n へのポインタ l を宣言する。
        構造体 n へのポインタ r を宣言する。
        構造体 n のコンストラクタを宣言する。
            引数として整数変数 d を受け取る。
            this->d = d
            l = r = NULL
    関数 inOrder(struct n *root) を宣言する。
        スタック s を宣言する。
        構造体 n へのポインタ current を宣言する。
            n *current = root で初期化する。
        while (current != NULL || s.empty() == false)
            while (current != NULL)
                s.push(current)
                current = current->l
            current = s.top()
            s.pop()
            current->d を出力する。
            current = current->r
    木の各ノードに値を挿入する。
    inOrder(root) を呼び出して木を走査する。
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(6);
    root->l = new n(4);
    root->r = new n(7);
    root->l->l = new n(8);
    root->l->r = new n(5);
    root->r->l = new n(9);
    root->r->r = new n(10);
    inOrder(root);
    return 0;
}

コードのポイント

• 構造体 n は、ノードの値 d と左右の子へのポインタ l・r を持ちます。
• コンストラクタでノード生成時に値を設定し、子ポインタをNULLで初期化しています。
• inOrder() 関数では stack<n *> を使い、左方向へ進みながらノードを一時的に退避させます。
• 左端に到達したらスタックからノードを取り出して値を出力し、右の部分木へ移動します。

実行結果

8 4 5 6 9 7 10

この出力は、木のノードを「左→根→右」の順に訪問した結果であり、キーが昇順に並んでいることが確認できます。