Tìm số anh chị em của nút cho trước trong cây N-ary bằng C++

Cho cây N-ary (mỗi nút có nhiều con), tìm số anh chị em của nút có giá trị key. Anh chị em là các nút cùng cha. Nếu không tìm thấy nút, trả về -1.

Phương pháp

Duyệt cây theo chiều rộng (BFS) dùng queue. Với mỗi nút cha, kiểm tra các con. Nếu tìm thấy con có giá trị key, số anh chị em = số con của cha - 1.

Mã nguồn C++

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

class Node {
public:
    int key;
    vector<Node*> child;
    Node(int data) { key = data; }
};

int main() {
    // Xây dựng cây
    Node* Base = new Node(50);
    (Base->child).push_back(new Node(2));
    (Base->child).push_back(new Node(30));
    (Base->child).push_back(new Node(14));
    (Base->child).push_back(new Node(60));
    (Base->child[0]->child).push_back(new Node(15));
    (Base->child[0]->child).push_back(new Node(25));
    (Base->child[0]->child[1]->child).push_back(new Node(70));
    (Base->child[0]->child[1]->child).push_back(new Node(100));
    (Base->child[1]->child).push_back(new Node(6));
    (Base->child[1]->child).push_back(new Node(1));
    (Base->child[2]->child).push_back(new Node(7));
    (Base->child[2]->child[0]->child).push_back(new Node(17));
    (Base->child[2]->child[0]->child).push_back(new Node(99));
    (Base->child[2]->child[0]->child).push_back(new Node(27));
    (Base->child[3]->child).push_back(new Node(16));

    int x = 30;
    queue<Node*> q;
    q.push(Base);
    bool flag = 0;
    int answer = -1;

    if (Base->key != x) {
        while (!q.empty()) {
            auto parent = q.front();
            q.pop();
            for (int i = 0; i < parent->child.size(); i++) {
                if (parent->child[i]->key == x) {
                    answer = parent->child.size() - 1;
                    flag = 1;
                    break;
                }
                q.push(parent->child[i]);
            }
            if (flag) break;
        }
        cout << answer << "\n";
    } else {
        cout << "0\n";
    }
    return 0;
}

Kết quả

3

Giải thích

Queue lưu các nút chưa duyệt. Khi tìm thấy nút con có giá trị x, gán answer = số con của cha - 1, dừng tìm kiếm. Nếu nút gốc là x, không có anh chị em → trả về 0. Nếu không tìm thấy, answer giữ nguyên -1.

Kết luận

Bài viết giải quyết bài toán tìm số anh chị em của nút trong cây N-ary bằng BFS. Độ phức tạp O(N). Mã nguồn C++ đầy đủ, có thể chuyển sang các ngôn ngữ khác.