ความหนาแน่นของ Binary Tree ใน One Traversal ใน C ++?

ความหนาแน่นของต้นไม้ไบนารีคำนวณโดยการหารขนาดของต้นไม้ด้วยความสูง ความหนาแน่นของต้นไม้ไบนารี =ขนาด/ความสูง

ให้เรากำหนดโครงสร้างที่จะเป็นตัวแทนของโหนดต้นไม้ที่มีข้อมูลและโหนดลูกของโหนดซ้ายและขวา หากนี่เป็นโหนดแรกที่สร้างขึ้น แสดงว่าเป็นโหนดรูท มิฉะนั้นจะเป็นโหนดย่อย

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

ต่อไป เราสร้างฟังก์ชัน createNode(int data) ที่ใช้ค่า int และกำหนดให้กับสมาชิกข้อมูลของโหนด ฟังก์ชันจะส่งกลับตัวชี้ไปยังโหนดโครงสร้างที่สร้างขึ้น นอกจากนี้ ลูกซ้ายและขวาของโหนดที่สร้างขึ้นใหม่จะถูกตั้งค่าเป็นโมฆะ

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

ฟังก์ชัน treeDensity(Node *root) ของเรารับโหนดรูทและตรวจสอบว่าเป็นโมฆะหรือไม่ จากนั้นจะประกาศตัวแปรขนาดและตั้งค่าเป็น 0 ค่าส่งคืนของฟังก์ชัน heightAndSize(root, size) ถูกกำหนดให้กับตัวแปรความสูง การแบ่งส่วนลอยที่ทำระหว่างความสูงและขนาดจะถูกส่งคืน

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

ถัดไป heightAndSize(โหนดโหนด*, int &ขนาด) นำโหนดรูทและการอ้างอิงไปยังตัวแปรขนาด หากโหนดรูทเป็นโมฆะ ระบบจะส่งคืน 0 ความสูงของแผนผังย่อยแต่ละรายการจะคำนวณแบบเรียกซ้ำ และขนาดจะเพิ่มขึ้นในการเรียกซ้ำแต่ละครั้ง จากนั้นเราจะคืนค่าแผนผังย่อยด้านซ้ายหรือด้านขวาที่ใหญ่กว่า

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

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อค้นหาความหนาแน่นของต้นไม้ไบนารีในการข้ามผ่านครั้งเดียว -

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

ผลลัพธ์

รหัสข้างต้นจะสร้างผลลัพธ์ต่อไปนี้ -

The density of the above given binary tree is 1.5