C++의 이진 트리에서 지정된 노드의 조상 인쇄

이 문제에서는 이진 트리가 주어지며 이진 트리에서 노드의 조상을 인쇄해야 합니다.

이진 트리 모든 노드에 최대 2개의 자식 노드가 있는 특수 트리입니다. 따라서 모든 노드는 리프 노드이거나 하나 또는 두 개의 하위 노드가 있습니다.

예

선조 바이너리 트리의 노드는 주어진 노드의 상위 레벨에 있는 노드입니다.

조상 노드의 예를 들어 보겠습니다 -

이 바이너리 트리에서 값이 3인 노드의 조상은 8,

이 문제를 해결하기 위해 루트 노드에서 대상 노드로 트래버스합니다. 이진 트리에서 단계적으로 아래로. 그리고 경로에서 오는 모든 노드를 인쇄합니다.

예시

#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;
}

출력

Ancestor Nodes are 6 10