C++의 한 순회에서 이진 트리의 밀도?

이진 트리의 밀도는 크기를 높이로 나누어 계산합니다. 이진 트리 밀도 =크기/높이

먼저 데이터와 왼쪽 및 오른쪽 노드 자식을 포함하는 트리 노드를 나타내는 구조체를 정의하겠습니다. 이것이 생성될 첫 번째 노드이면 루트 노드이고 그렇지 않으면 자식 노드입니다.

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

다음으로 int 값을 취하여 노드의 데이터 멤버에 할당하는 createNode(int 데이터) 함수를 만듭니다. 함수는 생성된 구조체 노드에 대한 포인터를 반환합니다. 또한 새로 생성된 노드의 왼쪽과 오른쪽 자식은 null로 설정됩니다.

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

우리의 treeDensity(Node *root) 함수는 루트 노드를 취하여 그 노드가 null인지 여부를 확인합니다. 그런 다음 크기 변수를 선언하고 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(Node* node, int &size)는 루트 노드와 크기 변수에 대한 참조를 취합니다. 루트 노드가 null이면 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