C++中N-Ary树的深度？

• Z时代
• 2024-01-10
• 分类：综合

让我们首先定义表示包含字符键和 Node * 向量的树节点的结构。

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

接下来我们创建我们的createNode(int key)函数，它接受一个 int 键值并将其分配给节点的键成员。该函数返回指向创建的结构节点的指针。

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

以上是 C++中N-Ary树的深度？ 的全部内容， 来源链接： utcz.com/z/317486.html