C++で再帰を使わずにN分木を先行順走査(プレオーダートラバーサル)する方法

はじめに

本記事では、N分木(N-ary Tree)が与えられたときに、その先行順走査(プレオーダートラバーサル)の結果を出力する問題を扱います。ポイントは、再帰呼び出しを使わずにスタックだけで実装するところです。

基本用語の確認

N分木(N-ary Tree)とは、すべてのノードが最大N個の子ノードを持つことができる木構造のことです。たとえば2分木(バイナリツリー)は、各ノードが最大2つの子ノードを持ちます。

先行順走査(Preorder Traversal)は、木のノードを巡回する方法の1つで、まずルートノードを訪問し、その後、子ノードを左から順に訪問していきます。

問題例

次のようなN分木を考えてみましょう。

この木の先行順走査の結果は次のようになります。

12  15  1  4  25  99  4  11  7  19

アルゴリズム:スタックを使った解法

再帰を使わずに先行順走査を実現するには、スタックデータ構造を利用します。手順は以下のとおりです。

1. ルートノードをスタックにプッシュします。
2. スタックからノードをポップし、その値を出力します。
3. ポップしたノードの子ノードを、右から左の順でスタックにプッシュします。こうすることで、スタックの性質(LIFO)により左側の子が先にポップされます。
4. スタックが空になるまで、手順2〜3を繰り返します。

C++による実装例

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int key;
    vector<Node*> child;
};
Node* insertNode(int key){
    Node* temp = new Node;
    temp->key = key;
    return temp;
}
void preOrderTraversal(struct Node* root){
    stack<Node*> tree;
    tree.push(root);
    while (!tree.empty()) {
        Node* curr = tree.top();
        tree.pop();
        cout<<curr->key<<"\t";
        vector<Node*>::iterator it = curr->child.end();
        while (it != curr->child.begin()) {
            it--;
            tree.push(*it);
        }
    }
}
int main(){
    Node* root = insertNode(12);
    (root->child).push_back(insertNode(15));
    (root->child).push_back(insertNode(99));
    (root->child).push_back(insertNode(4));
    (root->child).push_back(insertNode(7));
    (root->child[0]->child).push_back(insertNode(1));
    (root->child[0]->child).push_back(insertNode(4));
    (root->child[0]->child).push_back(insertNode(25));
    (root->child[2]->child).push_back(insertNode(11));
    (root->child[3]->child).push_back(insertNode(19));
    cout<<"PreOrder Traversal of the tree is :\n";
    preOrderTraversal(root);
    return 0;
}

出力結果

PreOrder Traversal of the tree is :
12  15  1  4  25  99  4  11  7  19

計算量

各ノードはスタックにちょうど1回プッシュされ、1回ポップされるため、時間計算量はO(N)(Nはノード数)です。空間計算量は、スタックに最大で木の高さ分のノードが積まれるため、最悪ケースでO(N)となります。

まとめ

再帰を使わずにN分木を先行順走査するには、子ノードをスタックに「右から左」の順で積むことが重要です。このテクニックは、木が深くなり再帰によるスタックオーバーフローのリスクがある場合や、処理を反復形式で統一したい場合に特に役立ちます。