データ構造入門：二分探索木の後順トラバーサル（ポストオーダー走査）を徹底解説

この記事では、二分探索木（Binary Search Tree）における後順トラバーサル（ポストオーダー走査）の手法を、再帰的なアプローチを中心に詳しく解説します。

後順トラバーサルは、「左の子ノード → 右の子ノード → 親ノード」の順でノードを訪問する木の走査方法です。ノードの削除処理や、子ノードを先に評価してから親を処理したいケースなどで広く活用されます。

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

この木を後順で走査した場合の訪問順序は以下の通りです。

8, 5, 15, 23, 20, 16, 10

最も深い位置にある左側のノードから順に処理され、最後に根（ルート）である10が出力される点に注目してください。

後順トラバーサルのアルゴリズム

後順トラバーサルは再帰を使うことで非常にシンプルに表現できます。基本的な流れは次の擬似コードの通りです。

postorderTraverse(root):
    root が空でない場合：
        左の子ノードに対して postorderTraverse を呼び出す
        右の子ノードに対して postorderTraverse を呼び出す
        root の値を出力する

つまり「左部分木をすべて処理 → 右部分木をすべて処理 → 自分自身の値を出力」という順序を、再帰的に繰り返していくのがポイントです。

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 postorder_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::postorder_traversal(node *r){
    if(r != NULL){ // ノードが存在する場合は「左 → 右 → 現在のノード」の順に訪問
        postorder_traversal(r->left);
        postorder_traversal(r->right);
        cout << r->value << " ";
    }
}
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 << "Post-Order Traversal: ";
    my_tree.postorder_traversal(my_tree.root);
}

このプログラムでは、最初にキー10をルートとして挿入し、その後5、16、20、15、8、23の順にノードを追加しています。各キーは二分探索木のルール（左の子は親より小さく、右の子は親より大きい）に従って自動的に適切な位置へ配置されます。

出力結果

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

出力を見ると、葉に近いノードから順に表示され、最後にルートの10が出力されていることが確認できます。これは後順トラバーサルの「子を先に、親を後に」という特性を正しく表しています。

なお、このアルゴリズムはすべてのノードを一度ずつ訪問するため、計算量はO(n)（nはノード数）となります。木の形状によらず安定した性能が得られる点も、この手法の魅力の一つです。