二分木を反時計回りにスパイラル走査するアルゴリズムをC++で実装する方法

はじめに：反時計回りのスパイラル走査とは

本記事では、二分木を反時計回りにスパイラル状（渦巻き状）に走査するという興味深い問題を取り上げます。通常のレベル順走査（幅優先探索）とは異なり、レベルごとに走査方向を切り替えながら、木の外周から内側へとノードを訪問していくのが特徴です。

走査のイメージは以下の図の通りです。

この木を反時計回りに走査すると、出力順序は次のようになります。

1, 8, 9, 10, 11, 12, 13, 14, 15, 3, 2, 4, 5, 6, 7

アルゴリズムの考え方

基本となるアイデアはシンプルです。上位レベルと下位レベルから同時に攻めていき、交互に方向を変えながら出力します。

• ポインタ i をレベル1（最上位）から、ポインタ j を木の高さ（最下層）からスタートさせます。
• フラグ（flag）が false のときは、レベル i のノードを右から左へ出力し、i を1つ進めます。
• フラグが true のときは、レベル j のノードを左から右へ出力し、j を1つ下げます。
• i が j を超えるまでこの処理を繰り返します。

擬似コード

Begin
    i := 1, j := height of the tree
    flag := false
    while i <= j, do
        if flag is false, then
            print tree elements from right to left for level i
            flag := true
            i := i + 1
        else
            print tree elements from left to right for level j
            flag := false
            j := j - 1
        end if
    done
End

C++による実装例

以下はC++での実装例です。木の高さを求める関数、指定レベルのノードを左から右へ出力する関数、右から左へ出力する関数を組み合わせて、反時計回りの走査を実現しています。

#include<iostream>
using namespace std;
class Node {
    public:
        Node* left;
        Node* right;
        int data;
    Node(int data) { //ノードを生成するコンストラクタ
        this->data = data;
        this->left = NULL;
        this->right = NULL;
    }
};
int getHeight(Node* root) {
    if (root == NULL)
    return 0;
    //左右の部分木の高さをそれぞれ求める
    int hl = getHeight(root->left);
    int hr = getHeight(root->right);
    return 1 + max(hl, hr); //根のぶんだけ1を加算
}
void printLeftToRight(class Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        printLeftToRight(root->left, level - 1);
        printLeftToRight(root->right, level - 1);
    }
}
void printRightToLeft(struct Node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1)
        cout << root->data << " ";
    else if (level > 1) {
        printRightToLeft(root->right, level - 1);
        printRightToLeft(root->left, level - 1);
    }
}
void antiClockTraverse(class Node* root) {
    int i = 1;
    int j = getHeight(root);
    int flag = 0; //走査方向を切り替えるためのフラグ
    while (i <= j) {
        if (flag == 0) {
            printRightToLeft(root, i);
            flag = 1; //左から右へ出力するようフラグを設定
            i++;
        }else {
            printLeftToRight(root, j);
            flag = 0; //右から左へ出力するようフラグを設定
            j--;
        }
    }
}
int main() {
    struct Node* root;
    root = new Node(1);
    root->left = new Node(2);
    root->right = new Node(3);
    root->left->left = new Node(4);
    root->left->right = new Node(5);
    root->right->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(8);
    root->left->left->right = new Node(9);
    root->left->right->left = new Node(10);
    root->left->right->right = new Node(11);
    root->right->left->left = new Node(12);
    root->right->left->right = new Node(13);
    root->right->right->left = new Node(14);
    root->right->right->right = new Node(15);
    antiClockTraverse(root);
}

実行結果

1 8 9 10 11 12 13 14 15 3 2 4 5 6 7

計算量の目安

この実装の計算量は以下の通りです。

• 時間計算量： 最悪 O(n²)。指定レベルまで再帰的に降りていくため、1レベルの走査に O(n) かかり、それを木の高さの回数だけ繰り返すためです。
• 空間計算量： O(h)（h は木の高さ）。再帰呼び出しのスタックが主な要因です。

なお、deque（両端キュー）を活用した反復的な実装に書き換えれば、時間計算量を O(n) まで改善することも可能です。

まとめ

二分木の反時計回りスパイラル走査のポイントは、「上端レベルは右から左、下端レベルは左から右」という方向の交互切り替えです。フラグ1つで方向を管理しながら、上下のレベルを挟み込むように処理を進めることで、直感的に実装できます。木構造の走査アルゴリズムの理解を深める良い題材なので、ぜひご自身でもコードを動かして試してみてください。