C++プログラミングのバイナリツリー内の任意の2つのノード間のパスを出力します。

個別のノードのバイナリツリーと、バイナリツリー内のパスを出力するバイナリツリーの2つのノードが与えられます。

例 −ノード140から211の間のパスを出力して、その出力が次のようになるようにします-

Output: 140->3->10->211

アイデアは、ルートノードから2つのノードへのパスを見つけて、それらを2つの別々のベクトルまたは配列（path1とpath2など）に格納することです。

ここで、2つの異なるケースが発生します-

• 2つのノードがルートノードの異なるサブツリーにある場合 − 2つのノードが、1つが左に、もう1つが右のように異なるサブツリーにある場合。この場合、ルートノードがnode1からnode2へのパスの間にあることは明らかです。したがって、path1を逆の順序で印刷してから、path2を印刷します。

• ノードが同じサブツリーにある場合 −両方のノードが同じサブツリーにあり、左側のサブツリーまたは右側のサブツリーのいずれかにある場合。この場合、ルートから2つのノードへのパスに交点があり、その前にルートノードからの2つのノードの両方にパスが共通であることに注意する必要があります。上記の場合のように、交点を見つけてその点からノードを印刷する必要があります。

アルゴリズム

START
STEP 1-> DEFINE A struct Node
   WITH int data AND Node *left, *right;
STEP 2-> DEFINE A TREE STRUCTURE struct Node* tree(int data)FUNCTION bool path(Node* root, vector& arr, int x)
STEP 1-> IF root IS NULL
   RETURN false
   END IF
STEP 2-> arr.push_back(root->data)
   IF root->data == x THEN
      RETURN true
   END IF
STEP 3-> IF path(root->left, arr, x) || path(root->right, arr, x) THEN,
   RETURN true
STEP 4-> arr.pop_back()
   return false
END FUNCTION
FUNCTION void printPath(Node* root, int n1, int n2)
STEP 1-> DEFINE A vector<int> path1
STEP 2-> DEFINE A vector<int> path2
STEP 3-> CALL FUNCTION path(root, path1, n1)
STEP 4-> CALL FUNCTION path(root, path2, n2)
STEP 5-> DEFINE AND SET intersection = -1, i = 0, j = 0
STEP 6-> LOOP WHILE i != path1.size() || j != path2.size()
   IF i == j && path1[i] == path2[j]
      INCREMENT i BY 1
      INCREMENT j BY 1
   ELSE
      SET intersection = j - 1
      BREAK;
   END IF
END WHILE
STEP 7-> LOOP FOR i = path1.size() – 1 AND i > intersection AND i--PRINT path1[i]
   END FOR
STEP 8-> LOOP FOR i = intersection AND i < path2.size() AND i++
   PRINT path2[i]
END FOR

例

#include <bits/stdc++.h>
using namespace std;
// structure of a node of binary tree
struct Node {
   int data;
   Node *left, *right;
};
struct Node* tree(int data){
   struct Node* newNode = new Node;
   newNode->data = data;
   newNode->left = newNode->right = NULL;
   return newNode;
}
bool path(Node* root, vector<int>& arr, int x){
   if (!root)
      return false;
   // push the node's value in 'arr'
   arr.push_back(root->data);
   // if it is the required node
   // return true
   if (root->data == x)
      return true;
   if (path(root->left, arr, x) || path(root->right, arr, x))
      return true;
   arr.pop_back();
   return false;
}
// Function to print the path between
// any two nodes in a binary tree
void printPath(Node* root, int n1, int n2){
   // vector to store the path
   vector<int> path1;
   vector<int> path2;
   path(root, path1, n1);
   path(root, path2, n2);
   int intersection = -1;
   int i = 0, j = 0;
   while (i != path1.size() || j != path2.size()) {
      if (i == j && path1[i] == path2[j]) {
         i++;
         j++;
      } else {
         intersection = j - 1;
         break;
      }
   }
   // Print the required path
   for (int i = path1.size() - 1; i > intersection; i--)
      cout << path1[i] << " ";
   for (int i = intersection; i < path2.size(); i++)
      cout << path2[i] << " ";
}
int main(){
   // binary tree formation
   struct Node* root = tree(1);
   root->left = tree(2);
   root->left->left = tree(4);
   root->left->left->left = tree(6);
   root->left->right = tree(5);
   root->left->right->left = tree(7);
   root->left->right->right = tree(8);
   root->right = tree(3);
   root->right->left = tree(9);
   root->right->right = tree(10);
   int node1 = 5;
   int node2 = 9;
   printPath(root, node1, node2);
   return 0;
}

出力

このプログラムは出力を出力します-

5 2 1 3 9