หาความหนาแน่นของ Binary Tree ในการเดินทางครั้งเดียวใน C++

บทนำ

ความหนาแน่นของ Binary Tree (Tree Density) = ขนาดต้นไม้ (จำนวนโหนด) / ความสูงของต้นไม้

ขั้นตอนการแก้ปัญหา

1. สร้าง Binary Tree
2. เขียนฟังก์ชัน Recursive หาความสูงและนับจำนวนโหนดพร้อมกัน (Single Traversal)
3. คืนค่าความสูง และอัปเดตตัวนับโหนดผ่าน reference parameter
4. คำนวณ Density = size / height

ตัวอย่างโค้ด

#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;
}

int findHeightAndSizeOfTree(Node* node, int &size) {
    if (node == NULL) {
        return 0;
    }
    int leftTreeCount = findHeightAndSizeOfTree(node->left, size);
    int rightTreeCount = findHeightAndSizeOfTree(node->right, size);
    size++;
    return (leftTreeCount > rightTreeCount) ? leftTreeCount + 1 : rightTreeCount + 1;
}

float treeDensity(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int treeSize = 0;
    int treeHeight = findHeightAndSizeOfTree(root, treeSize);
    return (float)treeSize / treeHeight;
}

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 << treeDensity(root) << endl;
    return 0;
}

ผลลัพธ์

2.33333

คำอธิบาย

ต้นไม้เต็ม 7 โหนด ความสูง 3 → Density = 7/3 ≈ 2.333

สรุป

Single Traversal คำนวณ size และ height พร้อมกัน ประหยัดเวลาเป็น O(n) แทนที่จะแยกเป็น 2 รอบ