使用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(&#39;A&#39;);
    (root->child).push_back(createNode(&#39;B&#39;));
    (root->child).push_back(createNode(&#39;F&#39;));
    (root->child).push_back(createNode(&#39;D&#39;));
    (root->child).push_back(createNode(&#39;E&#39;));
    (root->child[2]->child).push_back(createNode(&#39;K&#39;));
    (root->child[1]->child).push_back(createNode(&#39;J&#39;));
    (root->child[3]->child).push_back(createNode(&#39;G&#39;));
    (root->child[0]->child).push_back(createNode(&#39;C&#39;));
    (root->child[2]->child).push_back(createNode(&#39;H&#39;));
    (root->child[1]->child).push_back(createNode(&#39;I&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;N&#39;));
    (root->child[2]->child[0]->child).push_back(createNode(&#39;M&#39;));
    (root->child[1]->child[1]->child).push_back(createNode(&#39;L&#39;));
    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;
}

Output

4 1 2 2 1 0 0 1 2 0 0 0 0 0 192

上述程式碼的解釋

在在這種方法中，我們應用BFS（廣度優先搜尋）或層次遍歷，並檢查每個節點的子節點數量。然後，將該數量的階乘乘以我們的答案。

結論

本教學介紹了幾種遍歷N叉樹組合的方法，並應用了BFS。我們也學習了解決這個問題的C 程序和完整的方法。

我們可以用其他語言（如C、Java、Python和其他語言）寫相同的程式。希望你覺得這個教學有幫助。

以上是使用C++找到遍歷N叉樹的方式的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章！