C++ 프로그래밍에서 이진 트리의 첫 번째 최단 루트에서 리프 경로를 인쇄합니다.

바이너리 트리가 주어지면 프로그램은 주어진 많은 경로 중에서 루트에서 리프까지의 최단 경로를 찾아야 합니다.

우리는 트리를 왼쪽에서 오른쪽으로 순회하므로 루트에서 리프까지의 최단 경로가 여러 개 있는 경우 프로그램은 첫 번째 탐색된 최단 경로를 트리의 왼쪽에 인쇄합니다.

레벨 순서 순회를 사용하여 각 레벨을 순회하는 큐를 사용할 수 있으며, 루트에서 리프까지의 최단 경로가 되기 때문에 레벨 수가 가장 적은 경로가 인쇄됩니다.

위의 트리에서 루트에서 리프까지의 여러 경로는

10 -> 3 (this one is the shortest path amongst all)
10 -> 211 -> 100
10 -> 211 -> 146

예시

Input  : 10 3 211 100 146
Output : 10 3

알고리즘

Step 1 -> create a structure of a node as
   struct node
      struct node *left, *right
      int data
   End
Step 2 -> function to create a node
   node* newnode(int data)
   node *temp = new node
   temp->data = data
   temp->left = temp->right= NULL
   return temp
Step 3 -> create function for calculating path
   void path(int data, unordered_map <int,int> prnt)
      IF prnt[data] = data
         Return
      End
      path(prnt[data], prnt)
      print prnt[data]
step 4 -> function for finding out the left path
   void left(Node* root)
   create STL queue<Node*> que
   que.push(root)
   int leaf = -1
   Node* temp = NULL
   Create STL unordered_map<int, int> prnt
   prnt[root->data] = root->data
   Loop While !que.empty()
      temp = que.front()
      que.pop()
      IF !temp->left && !temp->right
         leaf = temp->data
         break
      End
      Else
         IF temp->left
            que.push(temp->left)
            prnt[temp->left->data] = temp->data
         End
         IF temp->right
            que.push(temp->right)
            prnt[temp->right->data] = temp->data
         End
      End
   End
   path(leaf, prnt)
   print leaf
Step 5 -> In main()
   Create tree using Node* root = newnode(90)
   root->left = newnode(21)
   call left(root)
stop

예시

#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
   struct Node *left,*right;
   int data;
};
//function to create a new node
Node* newnode(int data){
   Node* temp = new Node;
   temp->data = data;
   temp->left = NULL;
   temp->right = NULL;
   return temp;
}
//function to set a path
void path(int data, unordered_map <int,int> prnt) {
   if (prnt[data] == data)
      return;
   path(prnt[data], prnt);
   cout << prnt[data] << " ";
}
//function for a leaf path
void left(Node* root) {
   queue<Node*> que;
   que.push(root);
   int leaf = -1;
   Node* temp = NULL;
   unordered_map<int, int> prnt;
   prnt[root->data] = root->data;
   while (!que.empty()){
      temp = que.front();
      que.pop();
      if (!temp->left && !temp->right{
         leaf = temp->data;
         break;
      } else {
         if (temp->left){
            que.push(temp->left);
            prnt[temp->left->data] = temp->data;
         }
         if (temp->right){
            que.push(temp->right);
            prnt[temp->right->data] = temp->data;
         }
      }
   }
   path(leaf, prnt);
   cout << leaf << " ";
}
int main(){
   Node* root = newnode(90);
   root->left = newnode(21);
   root->right = newnode(32);
   root->left->left = newnode(45);
   root->right->left = newnode(52);
   root->right->right = newnode(27);
   root->left->left->left = newnode(109);
   root->left->left->right = newnode(101);
   root->right->right->left = newnode(78);
   left(root);
   return 0;
}

출력

위의 프로그램을 실행하면 다음 출력이 생성됩니다.

90 32 52