首頁 >後端開發 >C++ >使用C++找到遍歷N叉樹的方式的數量

使用C++找到遍歷N叉樹的方式的數量

王林
王林轉載
2023-09-04 17:01:17900瀏覽

給定一個N叉樹,我們的任務是找到遍歷這棵樹的總方式數,例如−

使用C++找到遍歷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中文網其他相關文章!

陳述:
本文轉載於:tutorialspoint.com。如有侵權,請聯絡admin@php.cn刪除