【C++】再帰とスタックを使わずに二分木を後順走査（ポストオーダー）する方法

この記事では、二分木を扱うアルゴリズムの問題を解説します。与えられた二分木に対して、再帰もスタックも使用せずに後順走査（ポストオーダートラバーサル）の結果を出力することが課題です。

二分木とは

二分木（バイナリツリー）とは、各ノードが最大2つの子ノードを持つことができる特殊な木構造のデータ構造です。

後順走査（ポストオーダートラバーサル）とは

後順走査は木構造の走査手法の一つで、まず左部分木を走査し、次に右部分木を走査し、最後に根（ルート）ノードを訪問します。

上図の木を後順走査した結果は次のとおりです。8 4 2 7 9 6

解法1：ハッシュテーブルを利用した深さ優先探索

再帰とスタックを使わずに木を走査するには、深さ優先探索（DFS）に基づく手法を採用し、訪問済みノードの情報をハッシュテーブル（unordered_set）に保存します。

アルゴリズムの流れ

1. 現在ノードに未訪問の左の子が存在する場合は、左の子へ移動します。
2. 左の子が存在しない、または訪問済みの場合は、未訪問の右の子へ移動します。
3. どちらの子も訪問済み（または存在しない）場合は、そのノードの値を出力し、訪問済みとして記録してからルートに戻ります。
4. ルート自体が訪問済みになった時点で、走査を終了します。

実装例

この解法の実装プログラムを以下に示します。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
};
void postOrderTraversal(struct Node* head) {
    struct Node* temp = head;
    unordered_set<Node*> visited;
    while (temp && visited.find(temp) == visited.end()) {
        if (temp->left &&
            visited.find(temp->left) == visited.end())
            temp = temp->left;
        else if (temp->right &&
            visited.find(temp->right) == visited.end())
            temp = temp->right;
        else {
            cout<<temp->data<<"\t";
            visited.insert(temp);
            temp = head;
        }
    }
}
struct Node* insertNode(int data){
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return (node);
}
int main(){
    struct Node* root = insertNode(6);
    root->left = insertNode(2);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->right = insertNode(4);
    root->right->left = insertNode(7);
    root->right->left->left = insertNode(13);
    cout<<"Post Order Traversal of the binary tree :\n";
    postOrderTraversal(root);
    return 0;
}

出力結果

Post Order Traversal of the binary tree :
8     4     2     13     7     9     6

解法2：unordered_mapによる親ノード追跡（改良版）

解法1では、訪問済みノードを保存するためにハッシュテーブルを使用し、ノードを出力するたびにルートへ巻き戻す必要がありました。この部分はさらに改良できます。

より効率的なアプローチとして、unordered_mapを使用する方法があります。各ノードとその親ノードの対応関係をマップに記録することで、出力後に直接親ノードへ戻ることができ、ルートへのトラックバックによるオーバーヘッドを削減できます。これにより、システムへの負荷を軽減し、アルゴリズム全体の効率が向上します。

実装例

改良版の実装プログラムを以下に示します。

#include <bits/stdc++.h>
using namespace std;
struct Node {
    int data;
    struct Node *left, *right;
    bool visited;
};
void postOrderTraversal(Node* root) {
    Node* n = root;
    unordered_map<Node*, Node*> postorder;
    postorder.insert(pair<Node*, Node*>(root, nullptr));
    while (n) {
        if (n->left && postorder.find(n->left) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->left, n));
            n = n->left;
        }
        else if (n->right && postorder.find(n->right) == postorder.end()) {
            postorder.insert(pair<Node*, Node*>(n->right, n));
            n = n->right;
        }
        else {
            cout<<n->data<<"\t";
            n = (postorder.find(n))->second;
        }
    }
}
struct Node* insertNode(int data) {
    struct Node* node = new Node;
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    node->visited = false;
    return (node);
}
int main() {
    struct Node* root = insertNode(6);
    root->left = insertNode(2);
    root->right = insertNode(9);
    root->left->left = insertNode(8);
    root->left->right = insertNode(4);
    root->right->left = insertNode(7);
    root->right->left->left = insertNode(13);
    cout<<"Post Order Traversal of the binary tree :\n";
    postOrderTraversal(root);
    return 0;
}

出力結果

Post Order Traversal of the binary tree :
8     4     2     13     7     9     6