Binary TreeinC++で特定のノードのいとこを出力します

二分木 は、すべてのノードに最大2つの子ノードがある特別なツリーです。したがって、すべてのノードはリーフノードであるか、1つまたは2つの子ノードを持っています。

例

この問題では、二分木が与えられ、その木のノードがあり、そのノードのいとこノードを見つける必要があります。二分木には兄弟ノードは出力されません。

例を見てみましょう

上記の二分木では、いとこノードは5です。

概念をより明確にするために、いとこノードについて説明しましょう。二分木では、2つのノードが二分木の同じレベル（深さ）にあるが、同じ親ノードを持たない場合、2つのノードはいとこノードであると言われます。

それでは、この問題の解決策を作成しましょう。

ここでは、ノードの同じレベルにあるすべてのノード、つまりルートノードから同じ距離にあるすべてのノードを印刷する必要があります。ただし、ノード自体と同じ親を持つノードを削除する必要があります。このために、最初にノードのレベルを見つけてから、ノード自体と同じ親を持つノードを除くすべてのノードを出力します。

例

それでは、このロジックに基づいてプログラムを作成しましょう-

#include <bits/stdc++.h>
using namespace std;
struct Node{
   int data;
   Node *left, *right;
};
Node *newNode(int item){
   Node *temp = new Node;
   temp->data = item;
   temp->left = temp->right = NULL;
   return temp;
}
int levelOfNode(Node *root, Node *node, int level){
   if (root == NULL)
      return 0;
   if (root == node)
      return level;
   int downlevel = levelOfNode(root->left,
   node, level + 1);
   if (downlevel != 0)
      return downlevel;
   return levelOfNode(root->right, node, level + 1);
}
void printCousin(Node* root, Node *node, int level){
   if (root == NULL || level < 2)
      return;
   if (level == 2){
      if (root->left == node || root->right == node)
         return;
      if (root->left)
         cout << root->left->data << " ";
      if (root->right)
         cout << root->right->data;
   }
   else if (level > 2){
      printCousin(root->left, node, level - 1);
      printCousin(root->right, node, level - 1);
   }
}
void cousinNode(Node *root, Node *node){
   int level = levelOfNode(root, node, 1);
   printCousin(root, node, level);
}
int main(){
   Node *root = newNode(11);
   root->left = newNode(15);
   root->right = newNode(4);
   root->left->left = newNode(3);
   root->left->right = newNode(7);
   root->left->right->right = newNode(9);
   root->right->left = newNode(17);
   root->right->right = newNode(8);
   root->right->left->right = newNode(5);
   cout<<”The cousin nodes are : \t”
   cousinNode(root, root->right->right);
   return 0;
}

出力

The cousin nodes are : 3 7