資料結構
網路
關係型資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究使用 C++ 遍歷 N 叉樹的路徑數
給定一個 N 叉樹，我們的任務是找到遍歷這棵樹的總路徑數，例如：
對於上面的樹，我們的輸出將是 192。
對於這個問題，我們需要了解一些組合學知識。現在在這個問題中，我們只需要檢查每條路徑的所有可能的組合，這將給我們答案。
解決方案方法
在這種方法中，我們只需要執行層序遍歷並檢查每個節點有多少個子節點，然後簡單地將它的階乘乘以答案。
示例
上述方法的 C++ 程式碼
#include<bits/stdc++.h>
using namespace std;
struct Node{ // structure of our node
char key;
vector<Node *> child;
};
Node *createNode(int key){ // function to initialize a new node
Node *temp = new Node;
temp->key = key;
return temp;
}
long long fact(int n){
if(n <= 1)
return 1;
return n * fact(n-1);
}
int main(){
Node *root = createNode('A');
(root->child).push_back(createNode('B'));
(root->child).push_back(createNode('F'));
(root->child).push_back(createNode('D'));
(root->child).push_back(createNode('E'));
(root->child[2]->child).push_back(createNode('K'));
(root->child[1]->child).push_back(createNode('J'));
(root->child[3]->child).push_back(createNode('G'));
(root->child[0]->child).push_back(createNode('C'));
(root->child[2]->child).push_back(createNode('H'));
(root->child[1]->child).push_back(createNode('I'));
(root->child[2]->child[0]->child).push_back(createNode('N'));
(root->child[2]->child[0]->child).push_back(createNode('M'));
(root->child[1]->child[1]->child).push_back(createNode('L'));
queue<Node*> q;
q.push(root);
long long ans = 1;
while(!q.empty()){
auto z = q.front();
q.pop();
ans *= fact(z -> child.size());
cout << z->child.size() << " ";
for(auto x : z -> child)
q.push(x);
}
cout << ans << "\n";
return 0;
}輸出
4 1 2 2 1 0 0 1 2 0 0 0 0 0 192
上述程式碼的解釋
在這種方法中，我們應用 BFS（廣度優先搜尋）或層序遍歷並檢查每個節點有多少個子節點。然後，將該數字的階乘乘以我們的答案。
結論
本教程介紹了多種遍歷 N 叉樹組合學的方法，並透過應用 BFS。我們還學習了這個問題的 C++ 程式以及我們解決的完整方法。
我們可以在其他語言（如 C、Java、Python 等）中編寫相同的程式。我們希望您覺得本教程有所幫助。
更新於： 2021-11-25
167 次瀏覽
廣告