C++를 사용하여 N-진 트리를 탐색하는 방법의 수 찾기-C++-php.cn

N-ary 트리가 주어지면 우리의 임무는 트리를 탐색하는 총 방법 수를 찾는 것입니다. 예: −

C++를 사용하여 N-진 트리를 탐색하는 방법의 수 찾기

위 트리의 경우 출력은 192입니다.

이 문제를 풀려면 조합론에 대한 지식이 필요합니다. 이제 이 문제에서 우리는 각 경로의 가능한 모든 조합을 확인하면 되며 이것이 답을 줄 것입니다.

해를 찾는 방법

이 방법에서는 레벨 순회를 수행하고 각 노드의 자식 수를 확인한 다음 답에 계승 곱하면 됩니다.

Example

위 메서드의 C++ 코드

#include using namespace std; struct Node{ // structure of our node char key; vector 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 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; }

로그인 후 복사