Trong hướng dẫn này, chúng ta sẽ tìm hiểu cách tìm mật độ của cây nhị phân trong một đường truyền đơn.
Mật độ của cây nhị phân được tính bằng cách chia kích thước của cây cho chiều cao của cây.
Kích thước của cây nhị phân là tổng số nút có trong cây nhị phân đã cho.
Chiều cao của cây nhị phân là chiều sâu tối đa của nút lá tính từ nút gốc.
Hãy xem các bước để giải quyết vấn đề.
-
Khởi tạo dữ liệu giả cây nhị phân.
-
Tìm kích thước và chiều cao của cây.
-
Đếm đệ quy chiều cao của cây.
-
Trả về chiều cao của cây nút bên trái nếu nó lớn hơn chiều cao của cây nút bên phải, nếu không trả về chiều cao của cây nút bên phải bằng cách thêm vào cả hai 1.
-
Tăng kích thước của nút.
-
-
Tính mật độ của cây bằng công thức $$ size \:of \:Tree \:/ \:height \:of \:Tree $$.
-
In mật độ của cây.
Ví dụ
Hãy xem mã.
#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;
} Đầu ra
Nếu bạn thực hiện chương trình trên, bạn sẽ nhận được kết quả sau.
2.33333
Kết luận
Nếu bạn có bất kỳ câu hỏi nào trong hướng dẫn, hãy đề cập đến chúng trong phần bình luận.