C++で実装する二分木の反時計回りスパイラル走査：アルゴリズムとサンプルコードを解説

二分木の反時計回りスパイラル走査(Anti-Clockwise Spiral Traversal)とは、木のノードを渦巻き状に、かつ通常とは逆向きの順序でたどっていく走査方法です。根(トップのノード)から開始し、レベル(深さ)ごとに左右の方向を交互に切り替えながら、木の外側から内側へと渦を描くようにノードを出力していきます。

下図は、二分木を反時計回りにスパイラル走査した際の訪問順序を示したものです。

アルゴリズムの流れ

二分木をスパイラル走査するためのアルゴリズムは、次の手順で動作します。

1. 2つの変数 i と j を用意し、i は最上位レベル「1」、j は木の高さでそれぞれ初期化します。
2. 出力の向き(左から右/右から左)を管理するフラグを用意します。フラグの初期値は false(0)です。
3. i <= j の間ループを継続します。フラグが false の間は、レベル i のノードを右から左へ出力し、フラグを true に反転させて i を1つ進めます。
4. フラグが true になったら、レベル j のノードを左から右へ出力し、フラグを false に戻して j を1つ減らします。
5. この処理を、二分木全体が出力し終わるまで繰り返します。

C++での実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    struct Node* left;
    struct Node* right;
    int data;
    Node(int data) {
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int height(struct Node* root) {
    if (root == NULL)
        return 0;
    int lheight = height(root->left);
    int rheight = height(root->right);
    return max(1 + lheight, 1 + rheight);
}
void leftToRight(struct Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        leftToRight(root->left, level - 1);
        leftToRight(root->right, level - 1);
    }
}
void rightToLeft(struct Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        rightToLeft(root->right, level - 1);
        rightToLeft(root->left, level - 1);
    }
}
int main() {
    struct Node* root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->right->left = new Node(5);
    root->right->right = new Node(7);
    root->left->left->left = new Node(10);
    root->left->left->right = new Node(11);
    root->right->right->left = new Node(8);
    int i = 1;
    int j = height(root);
    int flag = 0;
    while (i <= j) {
        if (flag == 0) {
            rightToLeft(root, i);
            flag = 1;
            i++;
        } else {
            leftToRight(root, j);
            flag = 0;
            j--;
        }
    }
    return 0;
}

実行結果

1 10 11 8 3 2 4 5 7

上記のコードでは、まず height() 関数で木の高さを求め、その後 leftToRight() と rightToLeft() という2つの再帰関数を使って指定レベルのノードを出力しています。メインの while ループ内でフラグの値を交互に切り替えることで、外側のレベルから内側のレベルへと渦巻状にノードが表示されます。

計算量

• 時間計算量: O(n × h)(n はノード数、h は木の高さ)。木が一方に偏っている最悪ケースでは O(n²) となります。
• 空間計算量: O(h)。再帰呼び出しで使用するスタック領域に依存します。