C++를 사용하여 이진 트리에서 가장 긴 잎사귀 경로를 인쇄하는 프로그램

이 튜토리얼에서는 주어진 바이너리 트리의 리프 노드에서 다른 리프 노드까지 존재하는 가장 긴 경로를 인쇄하는 프로그램에 대해 논의할 것입니다.

즉, Binary 트리의 지름에 나타나는 모든 노드를 인쇄해야 합니다. 여기에서 특정 이진 트리의 지름(또는 너비)은 한 끝 노드에서 다른 끝 노드까지 가장 긴 경로의 노드 수로 정의됩니다.

이를 해결하기 위해 높이 함수를 사용하여 이진 트리의 지름을 계산합니다. 그런 다음 이진 트리의 왼쪽 부분과 오른쪽 부분에서 가장 긴 경로를 찾습니다. 그런 다음 마지막으로 지름의 노드를 인쇄하기 위해 왼쪽 부분 노드, 루트 노드, 오른쪽 부분 노드를 인쇄합니다.

예시

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   Node *left, *right;
};
struct Node* create_node(int data){
   struct Node* node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
int tree_height(Node* root, int& ans, Node*(&k), int& lh, int& rh, int& f){
   if (root == NULL)
      return 0;
   int left_tree_height = tree_height(root->left, ans, k, lh, rh, f);
   int right_tree_height = tree_height(root->right, ans, k, lh, rh, f);
   if (ans < 1 + left_tree_height + right_tree_height){
      ans = 1 + left_tree_height + right_tree_height;
      k = root;
      lh = left_tree_height;
      rh = right_tree_height;
   }
   return 1 + max(left_tree_height, right_tree_height);
}
void print_roottonode(int ints[], int len, int f){
   int i;
   if (f == 0){
      for (i = len - 1; i >= 0; i--) {
         printf("%d ", ints[i]);
      }
   }
   else if (f == 1) {
      for (i = 0; i < len; i++) {
         printf("%d ", ints[i]);
      }
   }
}
void print_pathr(Node* node, int path[], int pathLen, int max, int& f){
   if (node == NULL)
   return;
   path[pathLen] = node->data;
   pathLen++;
   if (node->left == NULL && node->right == NULL) {
      if (pathLen == max && (f == 0 || f == 1)) {
         print_roottonode(path, pathLen, f);
         f = 2;
      }
   }
   else {
      print_pathr(node->left, path, pathLen, max, f);
      print_pathr(node->right, path, pathLen, max, f);
   }
}
void calc_diameter(Node* root){
   if (root == NULL)
      return;
   int ans = INT_MIN, lh = 0, rh = 0;
   int f = 0;
   Node* k;
   int tree_height_of_tree = tree_height(root, ans, k, lh, rh, f);
   int lPath[100], pathlen = 0;
   print_pathr(k->left, lPath, pathlen, lh, f);
   printf("%d ", k->data);
   int rPath[100];
   f = 1;
   print_pathr(k->right, rPath, pathlen, rh, f);
}
int main(){
   struct Node* root = create_node(12);
   root->left = create_node(22);
   root->right = create_node(33);
   root->left->left = create_node(45);
   root->left->right = create_node(57);
   root->left->right->left = create_node(26);
   root->left->right->right = create_node(76);
   root->left->left->right = create_node(84);
   root->left->left->right->left = create_node(97);
   calc_diameter(root);
   return 0;
}

출력

97 84 45 22 57 26