พิมพ์พาธระหว่างสองโหนดใดๆ ใน Binary Tree ในการเขียนโปรแกรม C++

เราได้รับไบนารีทรีของโหนดที่แตกต่างกัน และสองโหนดของไบนารีทรีที่มีพาธในแผนผังไบนารีที่เราต้องการพิมพ์

ตัวอย่าง − เราต้องการพิมพ์เส้นทางระหว่างโหนด 140 ถึง 211 ดังนั้นผลลัพธ์ของมันควรจะเป็น −

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

แนวคิดคือการค้นหาเส้นทางจากโหนดรูทไปยังโหนดทั้งสองและจัดเก็บไว้ในเวกเตอร์หรืออาร์เรย์ที่แยกจากกัน 2 รายการคือ path1 และ path2

ตอนนี้มีสองกรณีที่แตกต่างกัน -

• หากทั้งสองโหนดอยู่ในทรีย่อยที่แตกต่างกันของโหนดรูท − เมื่อโหนดทั้งสองอยู่ในทรีย่อยที่ต่างกัน เช่น โหนดหนึ่งอยู่ทางซ้ายและอีกโหนดหนึ่งอยู่ทางขวา ในกรณีนี้ เป็นที่ชัดเจนว่าโหนดรูทจะอยู่ระหว่างเส้นทางจากโหนด1 ไปยังโหนด2 ดังนั้น ให้พิมพ์ path1 ในลำดับย้อนกลับ แล้วตามด้วย path2

• หากโหนดอยู่ในทรีย่อยเดียวกัน − เมื่อโหนดทั้งสองอยู่ในทรีย่อยเดียวกันที่สามารถอยู่ในทรีย่อยด้านซ้ายหรือในทรีย่อยด้านขวา ในกรณีนี้คุณต้องสังเกตเส้นทางจากรูทไปยังโหนดทั้งสองจะมีจุดตัดกันก่อนที่เส้นทางจะพบได้ทั่วไปสำหรับทั้งสองโหนดจากโหนดรูท เราต้องหาจุดตัดและจุดพิมพ์จากจุดนั้นเหมือนกรณีด้านบน

อัลกอริทึม

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