C++で実装するN分木の先行順走査(プレオーダートラバーサル)

N分木(n-ary tree)が与えられたとき、そのノードの値を先行順走査(プレオーダートラバーサル)で訪問した結果を求める問題を考えてみましょう。

例として、次のような木が入力された場合を考えます。

この場合の出力は [1, 3, 5, 6, 2, 4] となります。

解き方のアプローチ

この問題は、再帰を使うことでシンプルに解くことができます。手順は以下の通りです。

• 結果を格納するための配列 ans を用意します

• root を引数に取る preorder() メソッドを定義します

• root が null(空)である場合は、空のリストを返します

• root の値を ans の末尾に追加します

• root の children 配列に含まれるすべての子ノード i に対して、preorder(i) を再帰的に呼び出します

• 最後に ans を返します

実装例

それでは、以下のC++による実装を見てみましょう。コード全体の流れをつかむことで、より深い理解につながります。

#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
    cout << "[";
    for(int i = 0; i<v.size(); i++){
        cout << v[i] << ", ";
    }
    cout << "]"<<endl;
}
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) {
        val = _val;
    }
    Node(int _val, vector<Node*> _children) {
        val = _val;
        children = _children;
    }
};
class Solution {
public:
    vector<int> ans;
    vector<int> preorder(Node* root) {
        if (!root)
            return {};
        ans.emplace_back(root->val);
        for (auto i : root->children)
            preorder(i);
        return ans;
    }
};
main(){
    Solution ob;
    Node *node5 = new Node(5), *node6 = new Node(6);
    vector<Node*> child_of_3 = {node5, node6};
    Node* node3 = new Node(3, child_of_3);
    Node *node2 = new Node(2), *node4 = new Node(4);
    vector<Node*> child_of_1 = {node3, node2, node4};
    Node *node1 = new Node(1, child_of_1);
    print_vector(ob.preorder(node1));
}

入力

Node *node5 = new Node(5), *node6 = new Node(6);
vector<Node*> child_of_3 = {node5, node6};
Node* node3 = new Node(3, child_of_3);
Node *node2 = new Node(2), *node4 = new Node(4);
vector<Node*> child_of_1 = {node3, node2, node4};
Node *node1 = new Node(1, child_of_1);

出力

[1, 3, 5, 6, 2, 4]

アルゴリズムのポイント

先行順走査では、「まず現在のノードを訪問し、その後に子ノードを左から順に再帰的に訪問する」という規則に従います。二分木の場合とよく似ていますが、N分木では子ノードが複数存在するため、forループですべての子に対して再帰処理を適用する点が特徴的です。

計算量はノード数をNとすると時間計算量はO(N)、空間計算量は再帰の深さ(木の高さ)と結果格納用の配列に依存し、最悪ケースでO(N)となります。