C++ 프로그램에서 한 번의 순회에서 이진 트리의 밀도

이 튜토리얼에서는 단일 순회에서 이진 트리의 밀도를 찾는 방법을 배울 것입니다.

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

바이너리 트리의 크기는 주어진 바이너리 트리에 존재하는 총 노드 수입니다.

바이너리 트리의 높이는 루트 노드에서 리프 노드의 최대 깊이입니다.

문제를 해결하는 단계를 살펴보겠습니다.

• 바이너리 트리 더미 데이터를 초기화합니다.

• 나무의 크기와 높이를 구하세요.

  • 트리의 높이를 재귀적으로 계산합니다.

  • 오른쪽 노드 트리 높이보다 크면 왼쪽 노드 트리 높이를 반환하고 그렇지 않으면 둘 다에 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

결론

튜토리얼에서 질문이 있는 경우 댓글 섹션에 언급하세요.