고유한 노드의 이진 트리와 이진 트리의 경로를 인쇄하려는 이진 트리의 두 노드가 제공됩니다.
예를 들어 − 노드 140에서 211 사이의 경로를 인쇄하고 싶으므로 출력은 다음과 같아야 합니다. -
Output: 140->3->10->211
아이디어는 루트 노드에서 두 노드로 가는 경로를 찾아 두 개의 개별 벡터 또는 배열(path1 및 path2)에 저장하는 것입니다.
이제 두 가지 다른 경우가 발생합니다 -
- 두 노드가 루트 노드의 다른 하위 트리에 있는 경우 - 두 노드가 하나는 왼쪽에 다른 하나는 오른쪽에 있는 것처럼 서로 다른 하위 트리에 있는 경우. 이 경우 루트 노드가 node1에서 node2로의 경로 사이에 있음이 분명합니다. 따라서 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