C++를 사용하여 이진 트리의 첫 번째 최단 루트에서 리프 경로를 인쇄하는 프로그램

이 튜토리얼에서는 이진 트리에서 첫 번째로 짧은 루트에서 리프 경로를 인쇄하는 프로그램에 대해 논의할 것입니다.

여기에서 고유한 값을 가진 이진 트리가 주어지고 주어진 이진 트리에서 루트 노드에서 리프 노드까지의 최단 경로를 찾아야 합니다.

이를 해결하기 위해 큐를 사용하여 이진 트리에서 수준 순서 탐색을 수행하고 최단 경로에 노드를 저장할 수 있습니다. 이를 위해 최종 레벨의 가장 왼쪽 노드에 도달하면 대기열에서 값을 검색하고 최단 경로를 인쇄합니다.

예시

#include <bits/stdc++.h>
using namespace std;
struct Node{
   struct Node* left;
   struct Node* right;
   int data;
};
struct Node* create_node(int data){
   struct Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
void print_spath(int Data, unordered_map<int, int> parent){
   if (parent[Data] == Data)
      return;
   print_spath(parent[Data], parent);
   cout << parent[Data] << " ";
}
void leftmost_path(struct Node* root){
   queue<struct Node*> q;
   q.push(root);
   int LeafData = -1;
   struct Node* temp = NULL;
   unordered_map<int, int> parent;
   parent[root->data] = root->data;
   while (!q.empty()){
      temp = q.front();
      q.pop();
      if (!temp->left && !temp->right){
         LeafData = temp->data;
      break;
      }
      else{
         if (temp->left){
            q.push(temp->left);
            parent[temp->left->data] = temp->data;
         }
         if (temp->right) {
            q.push(temp->right);
            parent[temp->right->data] = temp->data;
         }
      }
   }
   print_spath(LeafData, parent);
   cout << LeafData << " ";
}
int main(){
   struct Node* root = create_node(21);
   root->left = create_node(24);
   root->right = create_node(35);
   root->left->left = create_node(44);
   root->right->left = create_node(53);
   root->right->right = create_node(71);
   root->left->left->left = create_node(110);
   root->left->left->right = create_node(91);
   root->right->right->left = create_node(85);
   leftmost_path(root);
   return 0;
}

출력

21 35 53