C++를 사용하여 이진 트리의 루트에서 지정된 노드까지의 경로를 인쇄하는 프로그램

이 튜토리얼에서는 루트에서 주어진 노드까지의 경로를 바이너리 트리로 출력하는 프로그램에 대해 논의할 것입니다.

고유한 노드가 있는 주어진 이진 트리의 경우 이진 트리의 루트 노드에서 특정 노드에 도달하기 위해 전체 경로를 인쇄해야 합니다.

이 문제를 해결하기 위해 재귀를 사용할 것입니다. 이진 트리를 탐색하는 동안 찾을 특정 요소를 재귀적으로 검색합니다. 또한 검색할 요소에 도달하는 경로도 함께 저장됩니다.

예

#include <bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node *left, *right;
};
struct Node* create_node(int data){
   struct Node *new_node = new Node;
   new_node->data = data;
   new_node->left = new_node->right = NULL;
   return new_node;
}
//checks if a path from root node to element exists
bool is_path(Node *root, vector<int>& arr, int x){
   if (!root)
      return false;
   arr.push_back(root->data);
   if (root->data == x)
      return true;
   if (is_path(root->left, arr, x) || is_path(root->right, arr, x))
      return true;
   arr.pop_back();
   return false;
}
//printing the path from the root node to the element
void print_path(Node *root, int x){
   vector<int> arr;
   if (is_path(root, arr, x)){
      for (int i=0; i<arr.size()-1; i++)
         cout << arr[i] << " -> ";
         cout << arr[arr.size() - 1];
   }
   else
      cout << "Path doesn't exists" << endl;
}
int main(){
   struct Node *root = create_node(13);
   root->left = create_node(21);
   root->right = create_node(43);
   root->left->left = create_node(34);
   root->left->right = create_node(55);
   root->right->left = create_node(68);
   root->right->right = create_node(79);
   int x = 68;
   print_path(root, x);
   return 0;
}

출력

13 -> 43 -> 68