In tổ tiên của một nút nhất định trong Cây nhị phân trong C ++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân và chúng ta phải in tổ tiên của nó của một nút trong cây nhị phân.

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ụ,

Tổ tiên của một nút trong cây nhị phân là một nút ở cấp trên của nút đã cho.

Hãy lấy một ví dụ về nút tổ tiên -

Tổ tiên của một nút có giá trị 3 trong cây nhị phân này là 8,

Để giải quyết vấn đề này, chúng ta sẽ đi ngang từ nút gốc đến nút đích. Từng bước đi xuống trong cây nhị phân. Và trong đường dẫn in tất cả các nút đến.

Ví dụ

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
struct node{
   int data;
   struct node* left;
   struct node* right;
};
bool AncestorsNodes(struct node *root, int target){
   if (root == NULL)
      return false;
   if (root->data == target)
      return true;
   if ( AncestorsNodes(root->left, target) || AncestorsNodes(root->right, target) ){
      cout << root->data << " ";
      return true;
   }
   return false;
}
struct node* insertNode(int data){
   struct node* node = (struct node*) malloc(sizeof(struct node));
   node->data = data;
   node->left = NULL;
   node->right = NULL;
   return(node);
}
int main(){
   struct node *root = insertNode(10);
   root->left = insertNode(6);
   root->right = insertNode(13);
   root->left->left = insertNode(3);
   root->left->right = insertNode(8);
   root->right->left = insertNode(12);
   cout<<"Ancestor Nodes are " ;
   AncestorsNodes(root, 8);
   getchar();
   return 0;
}

Đầu ra

Ancestor Nodes are 6 10