Độ sâu của cây N-ary (N-ary Tree Depth) trong C++

Giới thiệu

Cây N-ary (N-ary tree) là cây mà mỗi node có tối đa N node con. Tính độ sâu (chiều cao) của cây N-ary.

Cấu trúc dữ liệu

Sử dụng vector<Node*> để lưu danh sách các node con (thay vì left/right cố định).

Mã nguồn hoàn chỉnh

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

struct Node {
    int data;
    vector children;
};

Node* newNode(int data) {
    Node* temp = new Node;
    temp->data = data;
    return temp;
}

int findDepthOfTree(Node* node) {
    if (node == NULL) return 0;
    
    int maxDepth = 0;
    for (Node* child : node->children) {
        maxDepth = max(maxDepth, findDepthOfTree(child));
    }
    
    return maxDepth + 1;
}

int main() {
    // Tạo cây:
    //       1
    //    /  |  \
    //   2   3   4
    //          / | | \
    //         1  2 3  4
    
    Node* root = newNode(1);
    root->children.push_back(newNode(2));
    root->children.push_back(newNode(3));
    root->children.push_back(newNode(4));
    
    root->children[2]->children.push_back(newNode(1));
    root->children[2]->children.push_back(newNode(2));
    root->children[2]->children.push_back(newNode(3));
    root->children[2]->children.push_back(newNode(4));
    
    cout << "Do sau cua cay N-ary: " << findDepthOfTree(root) << endl;
    return 0;
}

Kết quả chạy chương trình

Do sau cua cay N-ary: 3

Minh họa cây

Cấp 1: 1
Cấp 2: 2, 3, 4
Cấp 3: 1, 2, 3, 4 (con của node 4)
Độ sâu = 3

Phân tích độ phức tạp

• Thời gian: O(N) - N là tổng số node, thăm mỗi node 1 lần
• Không gian: O(H) - H là chiều cao cây (stack đệ quy)

Phiên bản lặp (BFS)

int findDepthBFS(Node* root) {
    if (!root) return 0;
    
    queue q;
    q.push(root);
    int depth = 0;
    
    while (!q.empty()) {
        int level_size = q.size();
        depth++;
        for (int i = 0; i < level_size; i++) {
            Node* node = q.front(); q.pop();
            for (Node* child : node->children) {
                q.push(child);
            }
        }
    }
    return depth;
}

So sánh Binary Tree vs N-ary Tree

Ứng dụng

• Cây thư mục (file system)
• Cây quyết định, cây trò chơi
• Trie (cây tiền tố) - N = 26 (chữ cái) hoặc 256 (ASCII)
• Cây tổ chức, cây gia phả

Kết luận

Độ sâu cây N-ary tính bằng đệ quy đơn giản: max độ sâu các con + 1. Vector children cho phép số con biến đổi linh hoạt.