ความหนาแน่นของต้นไม้แบบทวิภาค (Binary Tree Density) ในหนึ่งครั้งการท่องใน C++

นิยาม

Density = Size / Height โดย Size = จำนวนโหนด, Height = ความสูงของต้นไม้

อัลกอริธึม One Traversal

คำนวณ Size และ Height พร้อมกันในการท่องครั้งเดียว:

• ฟังก์ชัน heightAndSize(node, &size) ส่งคืนความสูง และเพิ่ม size ทีละ 1
• Density = (float)size / height

โปรแกรมตัวอย่าง

#include <iostream>
using namespace std;

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

int heightAndSize(Node* node, int& size) {
    if (!node) return 0;
    int lh = heightAndSize(node->left, size);
    int rh = heightAndSize(node->right, size);
    size++;
    return 1 + max(lh, rh);
}

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

int main() {
    Node* root = new Node(7);
    root->left = new Node(9);
    root->right = new Node(11);
    cout << "Tree density: " << treeDensity(root);
    return 0;
}

ผลลัพธ์

Tree density: 1.5