データ構造解説：二分探索木の先行順（プレオーダー）トラバーサルを再帰で実装する方法

この記事では、二分探索木（Binary Search Tree）における先行順トラバーサル（プレオーダー走査）の手法を、再帰を用いた実装とともに詳しく解説します。先行順トラバーサルは、木構造の各ノードを「根 → 左部分木 → 右部分木」の順に訪問する走査方法です。

対象となる二分探索木

まず、次のような二分探索木を例として考えます。

この木に対して先行順トラバーサルを実行すると、ノードは以下の順序で訪問されます。

走査順序：10, 5, 8, 16, 15, 20, 23

この順序になる理由は、まず根（10）を出力し、次に左部分木（5 → 8）を処理し、その後に右部分木（16 → 15 → 20 → 23）を再帰的に処理していくためです。

アルゴリズム

先行順トラバーサルの基本的なアルゴリズムは次のように表せます。

preorderTraverse(root):
Begin
    if root is not empty, then
        print the value of root
        preorderTraversal(left of root)
        preorderTraversal(right of root)
    end if
End

手順を日本語で整理すると以下の通りです。

• 現在のノード（根）が存在するか確認する
• 存在する場合、まずそのノードの値を出力する
• 続いて左の子ノードに対して同じ処理を再帰的に実行する
• 最後に右の子ノードに対して同じ処理を再帰的に実行する

C++による実装例

それでは、上記のアルゴリズムをC++で実際に実装してみましょう。ノードの挿入機能も含めた完全なサンプルコードです。

#include<iostream>
using namespace std;
class node{
    public:
        int h_left, h_right, bf, value;
        node *left, *right;
};
class tree{
    private:
        node *get_node(int key);
    public:
        node *root;
        tree(){
            root = NULL; //最初は根をNULLに設定
        }
        void preorder_traversal(node *r);
        node *insert_node(node *root, int key);
};
node *tree::get_node(int key){
    node *new_node;
    new_node = new node; //新しいノードを動的に生成
    new_node->h_left = 0; new_node->h_right = 0;
    new_node->bf = 0;
    new_node->value = key; //渡されたキーの値を保存
    new_node->left = NULL; new_node->right = NULL;
    return new_node;
}
void tree::preorder_traversal(node *r){
    if(r != NULL){ //ノードが存在する場合、根→左→右の順で訪問
        cout << r->value << " ";
        preorder_traversal(r->left);
        preorder_traversal(r->right);
    }
}
node *tree::insert_node(node *root, int key){
    if(root == NULL){
        return (get_node(key)); //木が空の場合、新ノードを根とする
    }
    if(key < root->value){ //キーが根の値より小さければ左へ
        root->left = insert_node(root->left, key);
    }else if(key > root->value){ //キーが根の値より大きければ右へ
        root->right = insert_node(root->right, key);
    }
    return root; //キーが既に存在する場合は挿入しない
}
main(){
    node *root;
    tree my_tree;
    //木にいくつかのキーを挿入する
    my_tree.root = my_tree.insert_node(my_tree.root, 10);
    my_tree.root = my_tree.insert_node(my_tree.root, 5);
    my_tree.root = my_tree.insert_node(my_tree.root, 16);
    my_tree.root = my_tree.insert_node(my_tree.root, 20);
    my_tree.root = my_tree.insert_node(my_tree.root, 15);
    my_tree.root = my_tree.insert_node(my_tree.root, 8);
    my_tree.root = my_tree.insert_node(my_tree.root, 23);
    cout << "Pre-Order Traversal: ";
    my_tree.preorder_traversal(my_tree.root);
}

コードのポイント

• get_node関数： 新しいノードを動的に確保し、初期化して返します。
• insert_node関数： 二分探索木の性質（左の子は親より小さく、右の子は親より大きい）に従ってノードを挿入します。重複するキーは挿入されません。
• preorder_traversal関数： 再帰呼び出しにより、「値の出力 → 左部分木 → 右部分木」の順に処理を行います。

実行結果

上記のプログラムをコンパイルして実行すると、次の出力が得られます。

Pre-Order Traversal: 10 5 8 16 15 20 23

期待どおり、木の図と同じ走査順序でノードの値が出力されていることが確認できます。先行順トラバーサルは、木の構造を複製したり、式木（expression tree）から前置記法（ポーランド記法）の式を生成したりする場面などで活用される重要な走査手法です。