【C++】二分木の中順走査（Inorder Traversal）を再帰的に実装する方法

木の走査（Tree Traversal）は、グラフ走査の一種であり、木に含まれるすべてのノードをそれぞれ一度だけ訪問（チェックまたは出力）する操作です。二分探索木における中順走査（Inorder Traversal、通りがけ順とも呼ばれます）では、「左の子 → 根 → 右の子」の順序で各ノードを訪問します。

二分木の中順走査の具体例を見てみましょう。次のような二分木が与えられたとします。

この二分木に対する中順走査の結果は次のとおりです。

中順走査の結果：1 4 5 6 8

それでは、中順走査を再帰的に実行する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 inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(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<<"In-Order traversal of the Binary Search Tree is: ";
    inorder(root);
    return 0;
}

実行結果

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

コードの解説

1. ノードを表す構造体「node」

上記のプログラムでは、構造体 node が木のノードを定義しています。この構造体は、自分自身と同じ型（struct node 型）へのポインタを持つ自己参照構造体であり、左右の子ノードを指すために使われます。構造体の定義は以下のとおりです。

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

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

関数 createNode() は新しいノード temp を生成し、malloc を使ってメモリを確保します。引数で渡された値 val を temp の 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. 中順走査を行う関数「inorder()」

関数 inorder() は、二分木の根（ルート）を引数として受け取り、木の要素を中順の順序で出力します。この関数は再帰関数として実装されており、まず左部分木を走査し、次に現在のノードの値を出力し、最後に右部分木を走査します。コードは以下のとおりです。

void inorder(struct node *root) {
    if (root != NULL) {
        inorder(root->left);
        cout<<root->data<<" ";
        inorder(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);

最後に、木の根ノードを引数として関数 inorder() を呼び出すことで、木のすべての値が中順の順序で表示されます。該当するコードは以下のとおりです。

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