給定一個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和其他語言)寫相同的程式。希望你覺得這個教學有幫助。
以上是使用C++找到遍歷N叉樹的方式的數量的詳細內容。更多資訊請關注PHP中文網其他相關文章!