C++で二分木の後順（ポストオーダー）走査を非再帰的に実装する方法

二分木を後順（ポストオーダー）で走査する場合、まず左の部分木を訪問し、次に右の部分木、最後に根（ルート）を訪問します。この記事では、再帰を使わずに後順走査を実現するC++プログラムを紹介します。ここではスタックを利用して実装します。

アルゴリズム

後順走査の手順：

開始
    関数 postorder_traversal(struct node *t, struct tree **top) を宣言
        もし t == NULL ならば
            「空の木です」と表示して return
    「Postorder Data Using Stack :」と表示
    ノードを挿入するために push(t, top) を呼び出す
    tree 構造体へのポインタ store を宣言し、NULL で初期化
    t != NULL の間、以下を繰り返す
        store = *top
        もし store->v == 0 ならば
            もし t->r != NULL ならば
                (store->v)++
                push(t->r, top)
            もし t->l != NULL ならば
                (store->v)++
                push(t->l, top)
            もし store->v == 0 ならば（葉ノードの場合）
                ノードの値を出力
                t = NULL
                pop(top)
        それ以外ならば
            ノードの値を出力
            t = NULL
            pop(top)
        もし *top != NULL ならば
            t = (*top)->link
終了

サンプルコード

以下が実際のC++コードです。スタックの各要素には、木のノードへのポインタ（link）と訪問状態を記録するカウンタ（v）を持たせています。

#include<iostream>
#include<stdlib.h>
using namespace std;
struct node {
    int d;
    struct node *l,*r;
};
struct tree {
    int v;
    struct node*link;
    struct tree*n;
};
struct node*create_node(int);
struct node*create_node(int value) {
    struct node*new_node=(struct node*)malloc(sizeof(struct node));
    if(new_node!=NULL) {
        new_node->d=value;
        new_node->l=new_node->r=NULL;
        return new_node;
    } else {
        printf("\n Memory overflow.");
        return NULL;
    }
}
void push(struct node*,struct tree*);
void push(struct node*node,struct tree**top) {
    struct tree*new_node=(struct tree*)malloc(sizeof(struct tree));
    if(new_node!=NULL) {
        new_node->link=node;
        new_node->n=*top;
        new_node->v=0;
        *top=new_node;
    } else {
        cout<<"\n Memory overflow.";
        return ;
    }
}
void pop(struct tree**);
void pop(struct tree**top) {
    if(*top!=NULL) {
        struct tree*remove=*top;
        *top=(*top)->n;
        remove->link=NULL;
        remove->n=NULL;
        remove=NULL;
    }
}
void postorder_traversal(struct node*,struct tree**);
void postorder_traversal(struct node*t,struct tree**top) {
    if(t==NULL) {
        cout<<"\n Empty Tree";
        return;
    }
    cout<<"\n Postorder Data Using Stack :";
    push(t,top);
    struct tree*store=NULL;
    while(t!=NULL) {
        store=*top;
        if(store->v==0) {
            if(t->r!=NULL) {
                (store->v)++;
                push(t->r,top);
            }
            if(t->l!=NULL) {
                (store->v)++;
                push(t->l,top);
            }
            if(store->v==0) {
                cout<<t->d;
                t=NULL;
                pop(top);
            }
        }
        else {
            cout<<t->d;
            t=NULL;
            pop(top);
        }
        if(*top!=NULL)
            t=(*top)->link;
    }
}
int main(){
    struct node*root=NULL;
    struct tree*top=NULL;
    root = create_node(20);
    root->l = create_node(10);
    root->r = create_node(30);
    root->r->r = create_node(7);
    root->l->l = create_node(25);
    root->l->r = create_node(35);
    root->l->r->r = create_node(40);
    root->l->l->r = create_node(26);
    postorder_traversal(root,&top);
    return 0;
}

プログラムのポイント

• スタック構造体： 各要素は木のノードへのポインタ（link）、訪問カウンタ（v）、次のスタック要素へのポインタ（n）を持ちます。
• push関数： 新しいノードをスタックの先頭に追加します。訪問カウンタ v は 0 で初期化されます。
• pop関数： スタックの先頭要素を取り除き、メモリ上の参照を解放します。
• 後順走査の仕組み： ノードをスタックに積む際、先に右の子、次に左の子を積むため、取り出される順序は「左 → 右 → 根」となります。子を持たない葉ノードや、両方の子の処理が完了したノード（v > 0）は、その時点で値が出力されます。

実行結果

Postorder Data Using Stack :26 25 40 35 10 7 30 20