資料結構
網路
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 次瀏覽
廣告