C++で完全二分木のルートから全ノードへの経路を出力する方法

はじめに

本記事では、二分木のルートノードから、木に存在する他のすべてのノードへの経路を出力するC++プログラムについて詳しく解説します。

問題の概要

このプログラムでは、整数Nが与えられ、二分木には1からNまでの要素が含まれているものとします。ノード1が二分木のルートノードです。したがって、私たちのタスクは、ルートノードから二分木内の他の各ノードまでの、考えられるすべての経路を出力することです。

解法のアプローチ

この問題を解く鍵となるのは、完全二分木の性質です。ノードiに対して、その左の子ノードは「2 * i」、右の子ノードは「2 * i + 1」として計算できます。この性質を利用し、バックトラッキング（バックトラック法）によって各ノードへの経路をvectorに格納しながら再帰的に探索を進め、すべての可能な経路を出力します。

サンプルコード

#include <iostream>
#include <vector>
using namespace std;
// ルートノードから全ての可能な経路を計算する
void calc_allpath(vector<int> paths, int nth_node, int kth_node){
    if (kth_node > nth_node)
        return;
    paths.push_back(kth_node);
    for (int i = 0; i < paths.size(); i++)
        cout << paths[i] << " ";
    cout << endl;
    calc_allpath(paths, nth_node, kth_node * 2);
    calc_allpath(paths, nth_node, kth_node * 2 + 1);
}
// ルートノードから全ての可能な経路を出力する
void print_allpath(int nth_node){
    vector<int> paths;
    calc_allpath(paths, nth_node, 1);
}
int main(){
    int nth_node = 9;
    print_allpath(nth_node);
    return 0;
}

出力結果

1
1 2
1 2 4
1 2 4 8
1 2 4 9
1 2 5
1 3
1 3 6
1 3 7

コードの解説

calc_allpath関数は、現在のノード番号がNを超えた時点で再帰を終了します。まず現在のノードを経路のvectorに追加し、その時点までの経路を出力します。その後、左の子ノード（kth_node * 2）と右の子ノード（kth_node * 2 + 1）に対して再帰的に同じ処理を繰り返します。

print_allpath関数は、空のvectorを用意してルートノード（ノード1）から探索を開始するためのラッパー関数です。main関数ではノード数を9として呼び出し、ルートから各ノードへの9つの経路が出力されます。

まとめ

完全二分木では、ノード番号の算術的な性質（左の子は2*i、右の子は2*i+1）を利用することで、木を実際に構築せずに経路の探索が可能です。バックトラッキングと組み合わせることで、シンプルかつ効率的にすべてのルートからの経路を出力できます。計算量はノード数をNとするとO(N log N)程度に収まり、実用的な実装となっています。