C++で二分木の先行順走査（プレオーダー）におけるN番目のノードを求める方法

この記事では、二分木と整数 N が与えられたときに、先行順走査（プレオーダートラバーサル）における N 番目のノードを見つける方法を解説します。

まず用語を整理しましょう。二分木とは、各ノードが最大で2つの子ノードを持つことができる特別な木構造のことです。また、走査（トラバーサル）とは、木に含まれるすべてのノードを順番に訪問し、必要に応じてその値を出力する処理のことを指します。先行順走査は「根 → 左部分木 → 右部分木」の順序でノードを訪問する方式です。

具体例で問題を理解しよう

入力

N = 6

以下のような二分木を考えます。

出力

6

解説

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

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

解法のアプローチ

この問題は、再帰呼び出しによる先行順走査を利用することで解決できます。具体的には、次の手順で処理を行います。

1. 現在のノード（根）を訪問し、訪問済みノードのカウントを1つ増やします。
2. カウントが N と一致した時点で、そのノードの値を出力します。
3. 続いて左部分木に対して再帰的に同じ処理を呼び出します。
4. 最後に右部分木に対して同様に再帰呼び出しを行います。

このように走査しながらノード数を数えていくことで、N 番目に訪問されたノードを効率的に特定できます。

C++による実装例

それでは、上記の解法を実際に動作させるプログラムを見てみましょう。

#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;
}

// 先行順走査でN番目のノードを探す再帰関数
void findPreOrderTraversalRec(struct Node* root, int N){
    static int nodeCount = 0;
    if (root == NULL)
        return;
    if (nodeCount <= N) {
        nodeCount++;
        if (nodeCount == N)
            cout << root->data;
        findPreOrderTraversalRec(root->left, N);
        findPreOrderTraversalRec(root->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<<"th node in preorder traversal is ";
    findPreOrderTraversalRec(root, N);
    return 0;
}

実行結果

6th node in preorder traversal is 6

コードのポイント

• static 変数 nodeCount： 再帰呼び出しの間でも値が保持されるため、訪問したノードの総数を正確に追跡できます。
• 早期終了の条件： nodeCount が N を超えたらそれ以上の走査を打ち切ることで、無駄な再帰処理を防いでいます。
• 計算量： 最悪の場合、木全体を走査するため時間計算量は O(N)、再帰のためのスタック領域として空間計算量は O(H)（H は木の高さ）となります。

この手法は、先行順走査の基本的な仕組みを理解するうえで非常に良い練習問題です。ぜひ自分でも別の木構造や異なる N の値で試してみてください。