C++でN分木（N-Aryツリー）の深さを求める方法

このチュートリアルでは、N分木（N-Aryツリー）の深さを求める方法について解説します。

N分木とは、木を構成する各ノードが持つことのできる子ノードの数がn個以下に制限された木構造のことです。本記事では、このN分木の深さ（根ノードから最も深い葉ノードまでの階層数）を求めるプログラムをC++で実装します。各ノードの子ノードは、vectorを使って格納します。

アルゴリズムの手順

• ダミーデータを使って木を初期化します。

• N分木の深さを求める再帰関数を作成します。

  • 木の最大深度を保持する変数を0で初期化します。

  • 各ノードの子ノードを順番に走査します。

    • 現在の最大深度と、その子ノードを根とする部分木の深度を比較し、大きい方を新しい最大深度として更新します。

    • 最大深度を格納する変数をmaxDepthとすると、maxDepth = max(maxDepth, findDepthOfTree(*child))という再帰呼び出しによって木全体の深さが求まります。

  • 最終的な木の深さはmaxDepth + 1となります（現在のノード自身の階層分を加算）。

• 求めた木の最大深度を出力します。

サンプルコード

それでは、実際のコードを見てみましょう。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    vector<Node *> child;
};
Node *newNode(int data) {
    Node *temp = new Node;
    temp->data = data;
    return temp;
}
int findDepthOfTree(struct Node *node) {
    if (node == NULL) {
        return 0;
    }
    int maxDepth = 0;
    for (vector<Node*>::iterator it = node->child.begin(); it != node->child.end(); it++) {
        maxDepth = max(maxDepth, findDepthOfTree(*it));
    }
    return maxDepth + 1;
}
int main() {
    Node *root = newNode(1);
    root->child.push_back(newNode(2));
    root->child.push_back(newNode(3));
    root->child.push_back(newNode(4));
    root->child[2]->child.push_back(newNode(1));
    root->child[2]->child.push_back(newNode(2));
    root->child[2]->child.push_back(newNode(3));
    root->child[2]->child.push_back(newNode(4));
    cout << findDepthOfTree(root) << endl;
    return 0;
}

実行結果

上記のコードを実行すると、次のような結果が出力されます。

3

まとめ

このチュートリアルでは、vectorを使ってN分木を表現し、再帰関数によって深さを求める方法を紹介しました。このアルゴリズムの計算量は、ノード数をNとするとO(N)であり、すべてのノードを一度ずつ訪問するだけで効率的に深さを求められます。チュートリアルの内容についてご不明な点がありましたら、コメント欄でお気軽にお尋ねください。