C++程序中N叉树的深度

在本教程中，我们将学习如何查找N叉树的深度。

N叉树是一种树，其中树的每个节点最多有N个子节点。

我们必须找到N叉树的深度。我们将使用向量来存储树中每个节点的子节点。

让我们看看解决问题的步骤。

  • 用虚拟数据初始化树。

  • 编写一个递归函数来查找N叉树的深度。

    • 初始化一个变量来存储树的最大深度。

    • 遍历每个节点的子节点。

      • 最大深度是当前最大深度和节点子节点深度的最大值。

      • 如果我们假设最大深度变量为maxDepth，并且maxDepth = max(maxDepth, findDepthOfTree(*children)是查找树深度的递归语句。

    • 树的最终最大深度为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

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

结论

如果您在本教程中有任何疑问，请在评论部分中提出。

更新于: 2021年1月27日

887 次浏览

开启你的职业生涯

通过完成课程获得认证

开始学习
广告