C++ Số cách duyệt cây N-ary

Cho cây N-ary, tìm tổng số cách duyệt cây này. Ví dụ cây cho ra kết quả 192.

Phương pháp giải

Số cách duyệt = tích giai thừa của số con của mỗi nút. Duyệt BFS (level order), với mỗi nút nhân đáp án với fact(số con).

Ví dụ minh họa

#include <bits/stdc++.h>
using namespace std;

struct Node {
    char key;
    vector<Node*> child;
};

Node* createNode(int key) {
    Node* t = new Node();
    t->key = key;
    return t;
}

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('J');
    root->child[3]->child.push_back('G');
    root->child[0]->child.push_back('C');
    root->child[2]->child.push_back('H');
    root->child[1]->child.push_back('I');
    root->child[2]->child[0]->child.push_back('N');
    root->child[2]->child[0]->child.push_back('M');
    root->child[1]->child[1]->child.push_back('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());
        for (auto x : z->child) q.push(x);
    }
    cout << ans << "\n";
    return 0;
}

Kết quả

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

Giải thích

BFS duyệt cây, tại mỗi nút nhân ans với giai thừa số con. Kết quả 192 cho cây ví dụ.

Kết luận

Đã giải bài toán số cách duyệt cây N-ary bằng tổ hợp và BFS. Code C++ chuyển được sang Java, Python, C. Hy vọng hữu ích.