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