二分木の先行順（プレオーダー）走査を再帰的に実行するC++プログラム

二分木の先行順走査とは

木の走査（トラバーサル）はグラフ走査の一種であり、木に含まれるすべてのノードをそれぞれ一度だけ訪れて処理を行うことを指します。二分探索木における先行順走査（プレオーダー走査）では、「根 → 左部分木 → 右部分木」の順序で各ノードを訪問するのが特徴です。

次のような二分木を例に考えてみましょう。

この二分木に対する先行順走査の結果は 6 4 1 5 8 となります。

ここからは、この先行順走査を再帰的に実行するC++プログラムを紹介します。

C++による実装例

#include<iostream>
using namespace std;
struct node {
    int data;
    struct node *left;
    struct node *right;
};
struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}
void preorder(struct node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preorder(root->left);
        preorder(root->right);
    }
}
struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
    node->left = insertNode(node->left, val);
    else if (val > node->data)
    node->right = insertNode(node->right, val);
    return node;
}
int main() {
    struct node *root = NULL;
    root = insertNode(root, 4);
    insertNode(root, 5);
    insertNode(root, 2);
    insertNode(root, 9);
    insertNode(root, 1);
    insertNode(root, 3);
    cout<<"Pre-Order traversal of the Binary Search Tree is: ";
    preorder(root);
    return 0;
}

実行結果

Pre-Order traversal of the Binary Search Tree is: 4 2 1 3 5 9

コードの解説

1. ノード構造体の定義

構造体 node は木のノードを表します。自分と同じ型へのポインタ（left と right）を持つ自己参照構造体であり、これによって木構造を表現できます。

struct node {
    int data;
    struct node *left;
    struct node *right;
};

2. ノード生成関数 createNode()

createNode() 関数は、malloc を使って新しいノード用のメモリを確保します。引数で渡された値 val を data メンバに格納し、左右の子ポインタには NULL を設定して返します。

struct node *createNode(int val) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = val;
    temp->left = temp->right = NULL;
    return temp;
}

3. 先行順走査関数 preorder()

preorder() 関数は、二分木の根ノードを引数として受け取り、先行順の順序で木の全要素を出力します。まず現在のノードの値を表示し、その後に左部分木、続いて右部分木に対して自分自身を再帰呼び出しすることで、全体を走査します。

void preorder(struct node *root) {
    if (root != NULL) {
        cout<<root->data<<" ";
        preorder(root->left);
        preorder(root->right);
    }
}

4. 挿入関数 insertNode()

insertNode() 関数は、指定した値を二分探索木の適切な位置に挿入します。ノードが NULL の場合は createNode() を呼び出して新しいノードを作成します。そうでなければ、値の大小関係を比較しながら左または右の子をたどり、正しい挿入位置を再帰的に探索します。

struct node* insertNode(struct node* node, int val) {
    if (node == NULL) return createNode(val);
    if (val < node->data)
    node->left = insertNode(node->left, val);
    else if (val > node->data)
    node->right = insertNode(node->right, val);
    return node;
}

5. main() 関数での処理

main() 関数では、まず根ノードを NULL として初期化します。その後、必要な値を持つノードを順番に二分探索木へ挿入していきます。

struct node *root = NULL;
root = insertNode(root, 4);
insertNode(root, 5);
insertNode(root, 2);
insertNode(root, 9);
insertNode(root, 1);
insertNode(root, 3);

最後に、木の根ノードを渡して preorder() 関数を呼び出すことで、木の全要素が先行順で表示されます。

cout<<"Pre-Order traversal of the Binary Search Tree is: ";
preorder(root);

このように、再帰を利用すると二分木の先行順走査を非常にシンプルなコードで実現できます。各関数の役割を理解すれば、他の走査方式（中間順・後行順）にも容易に応用できるでしょう。