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

Mật độ cây nhị phân = Số lượng nút (Size) / Chiều cao (Height).

Thường tính Size và Height riêng biệt (2 lần duyệt). Có thể tính **cùng lúc trong 1 lần duyệt Post-order** để đạt O(N) thời gian, O(H) stack.

Thuật toán Single Pass

Hàm heightAndSize(node, &size) trả về chiều cao, cập nhật biến size tham chiếu.

• Nếu node null: trả về 0.
• Đệ quy trái, phải.
• size++ (đếm nút hiện tại).
• Trả về max(leftH, rightH) + 1.

Chương trình C++

#include <iostream>
#include <algorithm>
using namespace std;

struct Node {
    int data;
    Node *left, *right;
    Node(int val) : data(val), left(nullptr), right(nullptr) {}
};

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

float treeDensity(Node* root) {
    if (!root) return 0.0f;
    int size = 0;
    int height = heightAndSize(root, size);
    return static_cast<float>(size) / height;
}

int main() {
    Node* root = new Node(7);
    root->left = new Node(9);
    root->right = new Node(11);
    //    7
    //   / \
    //  9  11
    // Size = 3, Height = 2. Density = 1.5
    
    cout << "Mật độ cây nhị phân: " << treeDensity(root) << endl;
    return 0;
}

Đầu ra

Mật độ cây nhị phân: 1.5