Binary Treein C++에서 주어진 노드의 사촌 인쇄

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

예

이 문제에서 이진 트리가 주어지고 트리의 노드가 있고 노드의 사촌 노드를 찾아야 합니다. 이진 트리에 대해 형제 노드가 인쇄되지 않습니다.

예를 들어 보겠습니다.

위의 이진 트리에서 사촌 노드는 5입니다.

개념을 더 명확하게 하기 위해 사촌 노드를 설명하겠습니다. 이진 트리에서 두 노드는 이진 트리에서 동일한 수준(깊이)에 있지만 동일한 부모 노드가 없는 경우 사촌 노드라고 합니다.

이제 이 문제에 대한 솔루션을 만들어 보겠습니다.

여기서 우리는 노드의 동일한 수준에 있는 모든 노드, 즉 루트 노드에서 동일한 거리에 있는 모든 노드를 인쇄해야 합니다. 그러나 노드 자체와 부모가 동일한 노드를 제거해야 합니다. 이를 위해 먼저 노드의 레벨을 찾은 다음 노드 자체와 동일한 부모를 가진 노드를 제외한 모든 노드를 인쇄합니다.

예

이제 이 논리를 기반으로 프로그램을 작성해 보겠습니다. -

#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