Mật độ của cây nhị phân trong một lần truyền trong C ++?

Mật độ của cây nhị phân được tính bằng cách chia kích thước của nó cho chiều cao của nó. Mật độ cây nhị phân =kích thước / chiều cao.

Đầu tiên chúng ta hãy xác định cấu trúc đại diện cho một nút cây chứa dữ liệu và nút con trái và phải của nó. Nếu đây là nút đầu tiên được tạo thì đó là nút gốc, ngược lại là nút con.

struct Node {
   int data;
   struct Node *leftChild, *rightChild;
};

Tiếp theo, chúng tôi tạo ra hàm createNode (int data) của chúng tôi, nhận một giá trị int và gán nó cho thành viên dữ liệu của nút. Hàm trả về con trỏ tới struct Node đã tạo. Ngoài ra, nút con bên trái và bên phải của nút mới tạo được đặt thành null.

Node* createNode(int data){
   Node* node = new Node;
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}

Hàm treeDensity (Node * root) của chúng ta lấy nút gốc và kiểm tra xem nó có null hay không. Sau đó, nó khai báo biến size và đặt nó thành 0. Giá trị trả về của hàm heightAndSize (root, size) được gán cho biến height. Sau đó, sự phân chia float được thực hiện giữa chiều cao và kích thước sẽ được trả về.

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

Tiếp theo, heightAndSize (Node * node, int &size) lấy nút gốc và tham chiếu đến biến kích thước. Nếu nút gốc là null thì 0 được trả về. Chiều cao của mỗi cây con được tính toán một cách đệ quy và kích thước được tăng lên trên mỗi lần đệ quy. Sau đó, chúng tôi trả về phần lớn hơn của cây con bên trái hoặc bên phải.

int heightAndSize(Node* node, int &size){
   if (node==NULL)
      return 0;
   int left = heightAndSize(node->leftChild, size);
   int right = heightAndSize(node->rightChild, size);
   size++;
   return (left > right) ? ++left : ++right;
}

Ví dụ

Chúng ta hãy xem cách triển khai sau đây để tìm mật độ cây nhị phân trong một lần truyền -

#include<iostream>
using namespace std;
struct Node{
   int data;
   Node *leftChild, *rightChild;
};
Node* createNode(int data){
   Node* node = new Node;
   node->data = data;
   node->leftChild = node->rightChild = NULL;
   return node;
}
int heightAndSize(Node* node, int &size){
   if (node==NULL)
      return 0;
   int left = heightAndSize(node->leftChild, size);
   int right = heightAndSize(node->rightChild, size);
   size++;
   return (left > right) ? ++left : ++right;
}
float treeDensity(Node* root){
   if (root == NULL)
      return 0;
      int size = 0;
      int height = heightAndSize(root, size);
   return (float)size/height;
}
int main(){
   Node* root = createNode(7);
   root->leftChild = createNode(9);
   root->rightChild = createNode(11);
   cout<< "The density of the above given binary tree is "<<treeDensity(root);
   return 0;
}

Đầu ra

Đoạn mã trên sẽ tạo ra kết quả sau -

The density of the above given binary tree is 1.5