C ++のN-Aryツリーの深さ？

まず、文字キーとノード*のベクトルを含むツリーノードを表す構造体を定義しましょう。

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

次に、intキー値を取得してノードのキーメンバーに割り当てるcreateNode（int key）関数を作成します。この関数は、作成された構造体ノードへのポインタを返します。

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

私たちのdepthOfTree（struct Node * root）関数は、ルートノードをパラメーターとして受け取ります。ルートがNULLの場合、深さは0として返されます。

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

次に、maxDepth変数を定義し、その値を0に割り当てます。次に、ツリーのすべての子を反復処理し、再帰ごとにmaxDepthをインクリメントします。基本条件が満たされ、再帰が終了したら、maxDepthを返します。

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

例

次の実装を見て、N-Aryツリーの深さを見つけましょう-

#include <iostream>
#include <vector>
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 = 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;
}

出力

上記のコードは次の出力を生成します-

The depth of the n-ary tree is 2