数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
JavaScript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会科学
时尚研究
法律研究如何在 C++ 中计算 N 元树的深度？
我们首先定义一个代表树节点的结构，其中包含一个字符键和一个 Node * 向量。
struct Node{
char key;
vector<Node *> children;
};接下来，我们创建 createNode(int key) 函数，它接受一个 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 元树深度的实现 -
#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
更新于： 2021 年 1 月 16 日
211 次浏览
广告