In các nút chung trên đường dẫn từ gốc (hoặc tổ tiên chung) trong C ++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân và hai nút của cây nhị phân được xác định. Và chúng ta phải in tất cả các tổ tiên chung của nút, tức là các nút chung xuất hiện trong đường dẫn truyền từ gốc đến nút.

Cây nhị phân là một cây đặc biệt mà mỗi nút có tối đa hai nút con. Vì vậy, mọi nút đều là nút lá hoặc có một hoặc hai nút con.

Ví dụ,

Nút tổ tiên là một nút được kết nối với các nút cấp thấp hơn trong một cây.

Nút tổ tiên chung của hai nút là một nút là nút tổ tiên của cả hai nút trong cây.

Ví dụ -

Trong cây nhị phân ở trên, chúng ta phải tìm tổ tiên chung của 0 và 6.

Đầu ra - 3, 2

Bây giờ, dựa trên vấn đề này, hãy tạo một thuật toán để giải quyết vấn đề này,

Thuật toán

Step 1 : Find the lowest common ancestor of the two nodes of the given tree. And print it.
Step 2 : Traverse upward to the root node and print all the nodes that come in the path.

Ví dụ

Bây giờ, hãy tạo một chương trình để minh họa giải pháp của vấn đề này,

#include <iostream>
using namespace std;
struct Node {
   struct Node* left, *right;
   int key;
};
Node* insertNode(int key){
   Node* temp = new Node;
   temp->key = key;
   temp->left = temp->right = NULL;
   return temp;
}
struct Node* LowestCommonAncestors(struct Node* root, int n1, int n2){
   if (root == NULL)
      return NULL;
   if (root->key == n1 || root->key == n2)
      return root;
   Node* left_lca = LowestCommonAncestors(root->left, n1, n2);
   Node* right_lca = LowestCommonAncestors(root->right, n1, n2);
   if (left_lca && right_lca)
      return root;
   return (left_lca != NULL) ? left_lca : right_lca;
}
bool printAncestorNodes(struct Node* root, int target){
   if (root == NULL)
      return false;
   if (root->key == target) {
      cout << root->key << "\t";
      return true;
   }
   if (printAncestorNodes(root->left, target) ||
   printAncestorNodes(root->right, target)) {
      cout << root->key << "\t”;
      return true;
   }
   return false;
}
bool printcommonAncestors(struct Node* root, int first, int second){
   struct Node* LCA = LowestCommonAncestors(root, first, second);
   if (LCA == NULL)
      return false;
   printAncestorNodes(root, LCA->key);
}
int main(){
   Node* root = insertNode(24);
   root->left = insertNode(8);
   root->right = insertNode(69);
   root->left->left = insertNode(12);
   root->left->right = insertNode(41);
   root->right->left = insertNode(50);
   root->right->right = insertNode(3);
   root->left->left->left = insertNode(22);
   root->right->left->left = insertNode(10);
   root->right->left->right = insertNode(6);
   if (printcommonAncestors(root, 6, 3) == false)
      cout << "No Common nodes";
   return 0;
}

Đầu ra

69 24