C++のバイナリツリーで特定のノードの祖先を出力します

この問題では、二分木が与えられ、ノードの祖先を二分木に出力する必要があります。

二分木 は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは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