Mật độ cây nhị phân (Density of Binary Tree) trong một lần duyệt C++

Giới thiệu

Mật độ cây nhị phân = Số lượng node / Chiều cao cây. Tính cả hai trong một lần duyệt (single traversal) để tối ưu.

Công thức

Density = Size / Height

• Size = tổng số node
• Height = độ sâu lớn nhất (số node trên đường dài nhất từ gốc đến lá)

Ví dụ

Cây đầy đủ 3 cấp (7 node):

      1
    /   \
   2     3
  / \   / \
 4   5 6   7

Size = 7, Height = 3 → Density = 7/3 ≈ 2.333

Mã nguồn hoàn chỉnh

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

struct Node {
    int data;
    Node *left, *right;
};

Node* newNode(int data) {
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}

// Trả về chiều cao, cập nhật size qua tham chiếu
int findHeightAndSize(Node* node, int &size) {
    if (node == NULL) return 0;
    
    int left_h = findHeightAndSize(node->left, size);
    int right_h = findHeightAndSize(node->right, size);
    
    size++;
    return max(left_h, right_h) + 1;
}

float treeDensity(Node* root) {
    if (root == NULL) return 0;
    
    int size = 0;
    int height = findHeightAndSize(root, size);
    
    return (float)size / height;
}

int main() {
    Node* root = newNode(1);
    root->left = newNode(2);
    root->right = newNode(3);
    root->left->left = newNode(4);
    root->left->right = newNode(5);
    root->right->left = newNode(6);
    root->right->right = newNode(7);
    
    cout << fixed << setprecision(5) << treeDensity(root) << endl;
    return 0;
}

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

2.33333

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

• Thời gian: O(n) - duyệt mỗi node 1 lần
• Không gian: O(h) - stack đệ quy

So sánh: Hai lần duyệt vs Một lần duyệt

Cả hai cùng O(n) nhưng single traversal nhanh gấp ~2 lần thực tế do giảm overhead gọi hàm và duyệt bộ nhớ.

Mở rộng: Các chỉ số cây khác

struct TreeInfo {
    int size = 0;
    int height = 0;
    int leaf_count = 0;
    int internal_count = 0;
    int sum_values = 0;
};

TreeInfo analyzeTree(Node* root) {
    if (!root) return {};
    
    TreeInfo left = analyzeTree(root->left);
    TreeInfo right = analyzeTree(root->right);
    
    TreeInfo cur;
    cur.size = 1 + left.size + right.size;
    cur.height = 1 + max(left.height, right.height);
    cur.sum_values = root->data + left.sum_values + right.sum_values;
    
    if (!root->left && !root->right) {
        cur.leaf_count = 1;
    } else {
        cur.internal_count = 1;
        cur.leaf_count = left.leaf_count + right.leaf_count;
        cur.internal_count += left.internal_count + right.internal_count;
    }
    return cur;
}

Kết luận

Kết hợp tính size và height trong một lần duyệt post-order là kỹ thuật tối ưu phổ biến cho các bài toán thống kê cây.