【C++】二分木のルートからリーフへの全経路を相対位置付きで出力する方法

問題の概要

この記事では、二分木が与えられたときに、ルート（根）からリーフ（葉）までのすべての経路を出力する方法を解説します。出力の際には、アンダースコア「_」を用いて各ノードの相対的な水平位置を視覚的に表現します。

まず、具体例を見ながら内容を理解していきましょう。

入力：

出力：

_ _ 3
_ 9
1
_3
9
_7
3
_ 4
_ _ 2
3
9 4
1 7 6 2
3
_ 4
6

解決のアプローチ：垂直順序の活用

この問題を解く鍵となるのは、木の要素の垂直順序（vertical order）という概念です。

上図のように、ルートの水平距離を0とし、左の子へ移動するたびに-1、右の子へ移動するたびに+1として水平距離を計算します。この水平距離の差分に応じてアンダースコアの数を決めることで、ノードの相対位置を表現した経路を出力できます。

アルゴリズム

ステップ1: 二分木を先行順巡回（preorder traversal）で走査します。走査中に、移動方向に基づいて各ノードの水平距離を計算します。ルートの水平距離は0とし、上記の図のように処理します。
ステップ2: リーフノードに到達した時点で、そこまでの経路をアンダースコア「_」付きで出力します。

C++による実装例

#include<bits/stdc++.h>
using namespace std;
#define MAX_PATH_SIZE 1000
struct Node{
    char data;
    Node *left, *right;
};
Node * newNode(char data){
    struct Node *temp = new Node;
    temp->data = data;
    temp->left = temp->right = NULL;
    return temp;
}
struct PATH{
    int horizontalDistance;
    char key;
};
void printPath(vector < PATH > path, int size){
    int minimumhorizontalDistance = INT_MAX;
    PATH p;
    for (int it=0; it<size; it++){
        p = path[it];
        minimumhorizontalDistance = min(minimumhorizontalDistance, p.horizontalDistance);
    }
    for (int it=0; it < size; it++){
        p = path[it];
        int noOfUnderScores = abs(p.horizontalDistance -minimumhorizontalDistance);
        for (int i = 0; i < noOfUnderScores; i++) cout<<"_ ";
            cout<<p.key<<endl;
    }
    cout<<"\nNext Path\n";
}
void printAllRtLPaths(Node *root, vector < PATH > &AllPath, int horizontalDistance, int order ){
    if(root == NULL)
        return;
    if (root->left == NULL && root->right == NULL){
        AllPath[order] = (PATH { horizontalDistance, root->data });
        printPath(AllPath, order+1);
        return;
    }
    AllPath[order] = (PATH { horizontalDistance, root->data });
    printAllRtLPaths(root->left, AllPath, horizontalDistance-1, order+1);
    printAllRtLPaths(root->right, AllPath, horizontalDistance+1, order+1);
}
void printRootToLeafPath(Node *root){
    if (root == NULL)
        return;
    vector<PATH> Allpaths(MAX_PATH_SIZE);
    printAllRtLPaths(root, Allpaths, 0, 0);
}
int main(){
    Node *root = newNode('3');
    root->left = newNode('9');
    root->right = newNode('4');
    root->left->left = newNode('1');
    root->left->right = newNode('7');
    root->right->left = newNode('6');
    root->right->right = newNode('2');
    printRootToLeafPath(root);
    return 0;
}

実行結果

_ _ 3
_ 9
1
Next Path
_ 3
9
_ 7
Next Path
3
_ 4
6
Next Path
3
_ 4
_ _ 2

出力の読み方

このプログラムは、リーフノードに到達するたびに経路を出力し、「Next Path」で区切ります。各行の先頭にあるアンダースコアの数は、そのノードが経路内で最も左にあるノードからどれだけ右に離れているかを表しています。例えば最初の経路「3 → 9 → 1」では、ノード1が最も左（水平距離-2）に位置するため、ノード3には2つ、ノード9には1つのアンダースコアが付きます。

計算量について

木の走査は各ノードを一度ずつ訪問するため、時間計算量はO(n)です。ただし、リーフに到達するたびに経路全体を出力するため、出力にかかるコストは木の高さhに対してO(h)となり、全体としてはO(n・h)となります。

まとめ

本記事では、二分木のルートからリーフへのすべての経路を、アンダースコアで相対位置を示しながら出力するC++プログラムを紹介しました。先行順巡回と水平距離の計算を組み合わせることで、ノードの空間的な配置を反映した直感的な出力を実現できます。二分木の走査アルゴリズムの理解を深める良い練習問題なので、ぜひ自分でも実装してみてください。