【C++】二分木の中間順走査でN番目のノードを検索する方法

この記事では、二分木（バイナリツリー）と整数Nが与えられたときに、二分木を中間順走査（inorder traversal）した際のN番目のノードを見つける方法を解説します。

二分木とは、各ノードが最大2つまでの子ノードを持つことができる特殊な木構造データです。

走査（トラバーサル）とは、木構造に含まれるすべてのノードを訪問する処理のことで、訪問時に各ノードの値を出力することもできます。

それでは、具体的な例を使ってこの問題を理解していきましょう。

入力例

N = 6

出力例

3

説明

木の中間順走査の結果：4, 2, 5, 1, 6, 3, 7

上記の走査結果において6番目に訪問されるノードは「3」であるため、出力は3となります。

解決アプローチ

この問題を解く鍵となるのは、再帰呼び出しを利用した二分木の中間順走査です。各再帰呼び出しでは、まず左部分木に対してfindInOrderTraversalRec()を呼び出し、次にルートノードを訪問した後、右部分木に対して同じ関数を呼び出します。

この走査の過程で訪問したノードの数をカウントしていき、カウントがNに一致したタイミングでそのノードの値を出力すれば、N番目のノードを特定できます。

ソリューションの動作を示すプログラム：

サンプルコード

#include <iostream>
using namespace std;
struct Node {
    int data;
    Node *left, *right;
};
struct Node* createNode(int item){
    Node* temp = new Node;
    temp->data = item;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}
void findInOrderTraversalRec(struct Node* node, int N){
    static int count = 0;
    if (node == NULL)
        return;
    if (count <= N) {
        findInOrderTraversalRec(node->left, N);
        count++;
        if (count == N)
            cout<<node->data;
        findInOrderTraversalRec(node->right, N);
    }
}
int main() {
    struct Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    root->right->left = createNode(6);
    root->right->right = createNode(7);
    int N = 6;
    cout<<N<<"番目のノード（中間順走査）は ";
    findInOrderTraversalRec(root, N);
    return 0;
}

出力

6番目のノード（中間順走査）は 3