ในบทช่วยสอนนี้ เราจะเรียนรู้วิธีค้นหาความหนาแน่นของต้นไม้ไบนารีในการข้ามผ่านครั้งเดียว
ความหนาแน่นของต้นไม้ไบนารีนั้นได้มาจากการหารขนาดของต้นไม้ด้วยความสูงของต้นไม้
ขนาดของไบนารีทรีคือจำนวนโหนดทั้งหมดที่มีอยู่ในทรีไบนารีที่กำหนด
ความสูงของไบนารีทรีคือความลึกสูงสุดของโหนดลีฟจากโหนดรูท
มาดูขั้นตอนการแก้ปัญหากัน
-
เริ่มต้นข้อมูลจำลองไบนารีทรี
-
หาขนาดและความสูงของต้นไม้
-
นับความสูงของต้นไม้ซ้ำๆ
-
คืนค่าความสูงของทรีโหนดทางซ้าย หากมากกว่าความสูงของทรีโหนดทางขวา มิฉะนั้นจะคืนค่าความสูงของทรีโหนดทางขวาโดยเพิ่มลงใน 1 ทั้งสอง
-
เพิ่มขนาดของโหนด
-
-
คำนวณความหนาแน่นของต้นไม้โดยใช้สูตร $$size\:of\:Tree\:/\:height\:of\:Tree$$.
-
พิมพ์ความหนาแน่นของต้นไม้
ตัวอย่าง
มาดูโค้ดกันเลย
#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
บทสรุป
หากคุณมีข้อสงสัยใดๆ ในบทแนะนำ โปรดระบุในส่วนความคิดเห็น
