C++で再帰を使わずに二分木のルートからリーフへの経路を出力するプログラム

このチュートリアルでは、与えられた二分木において、ルートノードからすべてのリーフノード(葉ノード)への経路を出力するプログラムを、C++で再帰を使わずに実装する方法を解説します。

例として、次のような二分木を考えてみましょう。

この二分木には、34・55・29という3つのリーフノードが存在します。したがって、ルートノードからリーフノードへの経路は3つあることになります。

アルゴリズムのアプローチ

この問題は、再帰に頼らない反復的なアプローチで解くことができます。手順は以下のとおりです。

1. スタックを用いて、二分木を前順走査(先行順走査)します。
2. 走査の過程で、各ノードの親ノードへのポインタをマップ(std::map)に記録していきます。
3. 走査中にリーフノード(左右どちらの子も持たないノード)を見つけたら、親ポインタをさかのぼることで、ルートノードからの経路を簡単に出力できます。

サンプルコード

#include <bits/stdc++.h>
using namespace std;
struct Node{
    int data;
    struct Node *left, *right;
};
// 新しいノードを作成する
Node* create_node(int data){
    Node* node = new Node;
    node->data = data;
    node->left = node->right = NULL;
    return node;
}
// ルートからリーフへの経路を出力する
void print_cpath(Node* curr, map<Node*, Node*> parent){
    stack<Node*> nodes_stack;
    while (curr){
        nodes_stack.push(curr);
        curr = parent[curr];
    }
    while (!nodes_stack.empty()){
        curr = nodes_stack.top();
        nodes_stack.pop();
        cout << curr->data << " ";
    }
    cout << endl;
}
// 前順走査を実行する
void preorder_traversal(Node* root){
    if (root == NULL)
        return;
    stack<Node*> nodeStack;
    nodeStack.push(root);
    map<Node*, Node*> parent;
    parent[root] = NULL;
    while (!nodeStack.empty()){
        Node* current = nodeStack.top();
        nodeStack.pop();
        if (!(current->left) && !(current->right))
            print_cpath(current, parent);
        if (current->right){
            parent[current->right] = current;
            nodeStack.push(current->right);
        }
        if (current->left){
            parent[current->left] = current;
            nodeStack.push(current->left);
        }
    }
}
int main(){
    Node* root = create_node(101);
    root->left = create_node(82);
    root->right = create_node(23);
    root->left->left = create_node(34);
    root->left->right = create_node(55);
    root->right->left = create_node(29);
    preorder_traversal(root);
    return 0;
}

出力

101 82 34
101 82 55
101 23 29

計算量

時間計算量は、前順走査ですべてのノードを訪問するO(N)に加え、マップへの挿入・参照やリーフごとの経路出力のコストが加わるため、全体としてO(N log N)となります。また、親ポインタを記録するマップと走査用のスタックが必要なため、空間計算量はO(N)です。

再帰を使わないこの手法は、木が非常に深くなる場合にスタックオーバーフローのリスクを避けたい場面で特に有効です。