与えられた二分木の後順（ポストオーダー）再帰走査を実行するC++プログラム

木構造の走査（トラバーサル）はグラフ走査の一種であり、木の中の各ノードを正確に一度だけ訪問して確認・出力する操作を指します。二分探索木の後順走査（ポストオーダー走査）では、木の各ノードを「左 → 右 → 根」の順序で訪問します。

二分木の後順走査の例を以下に示します。

次のような二分木が与えられたとします。

この場合、後順走査の結果は次のようになります。

後順走査の出力：1 5 4 8 6

後順再帰走査を行う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 postorder(struct node *root) {
    if (root != NULL) {
        postorder(root->left);
        postorder(root->right);
        cout<<root->data<<" ";
    }
}
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<<"Post-Order traversal of the Binary Search Tree is: ";
    postorder(root);
    return 0;
}

実行結果

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

プログラムの解説

1. 構造体nodeによるノードの定義

上記のプログラムでは、構造体nodeが木の各ノードを作成します。この構造体は、自分自身と同じstruct node型へのポインタ（left・right）を含んでいるため、自己参照構造体と呼ばれます。定義は以下の通りです。

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

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

createNode()関数は新しいノードtempを作成し、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. postorder()関数 ― 後順走査の本体

postorder()関数は二分木の根ノードを引数として受け取り、木の全要素を後順で出力する再帰関数です。処理の流れは「左の子を再帰的に走査 → 右の子を再帰的に走査 → 自分自身（根）の値を出力」という順序になっており、これが「左・右・根」の後順走査の定義に対応しています。

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

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);

最後に、木の根ノードを引数としてpostorder()関数を呼び出すことで、木全体の値が後順で画面に表示されます。

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