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

N分木（N-Aryツリー）とは、各ノードが最大N個の子ノードを持つことができる木構造です。この記事では、C++を使ってN分木の深さ（ルートノードから最も深い葉ノードまでの階層数）を再帰的に求める方法を解説します。

ツリーノードを表す構造体の定義

まず、文字型のキーと子ノードへのポインタを格納するvectorを持つ、木のノードを表す構造体を定義します。

struct Node{
    char key;
    vector<Node *> children;
};

ノード生成用の関数を作成する

次に、キー値を受け取って新しいノードを生成するcreateNode()関数を作成します。この関数は、引数で受け取ったキー値をノードのkeyメンバーに代入し、生成したノードへのポインタを返します。

Node *createNode(int key){
    Node *node = new Node;
    node->key = key;
    return node;
}

木の深さを求める関数

depthOfTree()関数は、ルートノードを引数として受け取ります。ルートがNULLの場合は深さとして0を返します。これが再帰の終了条件（ベースケース）となります。

int depthOfTree(struct Node *root){
    if (root==NULL)
        return 0;

続いて、最大深度を記録する変数maxDepthを0で初期化します。その後、すべての子ノードに対して再帰呼び出しを行い、各子の深さに1を加えた値とmaxDepthを比較しながら、より大きい方を保持していきます。すべての再帰が完了した時点でmaxDepthを返せば、木全体の深さが求まります。

int depthOfTree(struct Node *root){
    if (root==NULL)
        return 0;
    int maxDepth = 0;
    for(auto i: root->children){
        maxDepth = max(maxDepth, depthOfTree(i) + 1);
    }
    return maxDepth;
}

なお、子ノードの中で最も深いものを正しく判定するためには、std::max()を使って現在のmaxDepthと各子の深さを比較することが重要です。単純に代入してしまうと、最後に処理した子の深さで上書きされ、正しい結果が得られない場合があります。

実装例

それでは、N分木の深さを求めるプログラム全体を見てみましょう。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Node{
    char key;
    vector<Node *> children;
};

Node *createNode(int key){
    Node *node = new Node;
    node->key = key;
    return node;
}

int depthOfTree(struct Node *root){
    if (root==NULL)
        return 0;
    int maxDepth = 0;
    for(auto i: root->children){
        maxDepth = max(maxDepth, depthOfTree(i) + 1);
    }
    return maxDepth;
}

int main(){
    Node *root = createNode('S');
    (root->children).push_back(createNode('O'));
    (root->children).push_back(createNode('A'));
    (root->children).push_back(createNode('D'));
    (root->children).push_back(createNode('N'));
    (root->children[0]->children).push_back(createNode('L'));
    (root->children[0]->children).push_back(createNode('I'));
    (root->children[2]->children).push_back(createNode('R'));
    (root->children[3]->children).push_back(createNode('C'));
    (root->children[3]->children).push_back(createNode('H'));
    (root->children[3]->children).push_back(createNode('I'));
    cout <<"The depth of the n-ary tree is "<< depthOfTree(root) << endl;
    return 0;
}

このサンプルコードでは、ルート「S」の下に「O」「A」「D」「N」の4つの子ノードを作成し、さらにいくつかの孫ノードを追加しています。この木は「ルート→子→孫」という3階層構造であるため、深さは2となります。

出力結果

上記のコードを実行すると、以下のような出力が得られます。

The depth of the n-ary tree is 2