資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟
心理
社會學
時尚
法律C++ 中 n 元樹中每個結點的子樹中葉結點的數量
在本教程中，我們將編寫一個程式，找到 n 元樹中每個結點的葉結點數量。
給定一個 n 元樹，我們必須找到每個子樹的葉結點數量。我們來看一個例子。
輸入
N = 8 tree = [[2, 3], [], [4, 5, 6], [7, 8], [], [], [], []]
輸出
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
演算法
用你喜歡的樹初始化 n 元樹。
使用 DFS 遍歷這棵樹。
維護一個數組來儲存每個結點葉結點數量的計數。
在對 DFS 進行遞迴呼叫後增加葉結點的計數。
打印出具有葉結點數量的所有結點。
實現
以下是上述演算法在 C++ 中的實現
#include <bits/stdc++.h>
using namespace std;
void insertNode(int x, int y, vector<int> tree[]) {
tree[x].push_back(y);
}
void DFS(int node, int leaf[], int visited[], vector<int> tree[]) {
leaf[node] = 0;
visited[node] = 1;
for (auto it : tree[node]) {
if (!visited[it]) {
DFS(it, leaf, visited, tree);
leaf[node] += leaf[it];
}
}
if (!tree[node].size()) {
leaf[node] = 1;
}
}
int main() {
int N = 8;
vector<int> tree[N + 1];
insertNode(1, 2, tree);
insertNode(1, 3, tree);
insertNode(3, 4, tree);
insertNode(3, 5, tree);
insertNode(3, 6, tree);
insertNode(4, 7, tree);
insertNode(4, 8, tree);
int leaf[N + 1];
int visited[N + 1];
for (int i = 0; i <= N; i++) {
visited[i] = 0;
}
DFS(1, leaf, visited, tree);
for (int i = 1; i <= N; i++) {
cout << i << "->" << leaf[i] << endl;
}
return 0;
}輸出
如果你執行上述程式碼，那麼你將得到以下結果。
1->5 2->1 3->4 4->2 5->1 6->1 7->1 8->1
更新日期：2021-10-26
365 次瀏覽
廣告