C++の二分木で特定のノードのいとこノードを出力する方法

二分木（バイナリツリー）とは

二分木とは、各ノードが最大で2つの子ノードを持つ特別な木構造です。つまり、すべてのノードは葉ノードであるか、1つまたは2つの子ノードを持ちます。

例：

問題の概要

この問題では、二分木とその木の中の1つのノードが与えられ、そのノードの「いとこノード（cousin nodes）」を見つけて出力することが求められます。ただし、兄弟ノードは出力の対象外です。

具体例を見てみましょう。

上記の二分木において、対象ノードのいとこノードは5です。

いとこノードとは

概念をより明確にするために、いとこノードについて説明します。二分木において、2つのノードが同じレベル（深さ）に位置し、かつ同じ親ノードを持たない場合、それらのノードは互いにいとこノードと呼ばれます。

解決のアプローチ

この問題を解くには、対象ノードと同じレベル、つまりルートノードから同じ距離にあるすべてのノードを出力します。ただし、対象ノード自身と、対象ノードと同じ親を持つノードは除外する必要があります。

具体的な手順は以下の通りです。

1. 再帰的に木を探索し、対象ノードのレベル（深さ）を求めます。
2. そのレベルに属するすべてのノードを出力します。このとき、対象ノードと同じ親を持つノードは除外します。

サンプルプログラム

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

#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 : ";
    cousinNode(root, root->right->right);
    return 0;
}

出力結果

The cousin nodes are : 3 7

このプログラムでは、ノード8のいとこノードを求めています。ノード8と同じレベル（レベル3）にあり、異なる親を持つノードは3と7であるため、出力は「3 7」となります。