C++で二分木の上面図（トップビュー）のノードを出力するプログラム

二分木の上面図（トップビュー）とは

このチュートリアルでは、与えられた二分木の上面図に現れるすべてのノードを出力するC++プログラムについて解説します。

二分木において、あるノードが上面図に表示されるのは、そのノードが属する「水平距離」において最初に現れるノードである場合です。水平距離は次のように定義されます。

• ノード x の左の子ノードの水平距離：x − 1
• ノード x の右の子ノードの水平距離：x + 1

言い換えれば、木を真上から見下ろしたときに視界に入るノードだけが上面図に現れることになります。

アルゴリズムの考え方

この問題を解くには、レベル順走査（幅優先探索）を利用します。レベル順にノードを処理することで、同じ水平距離に属するノードの中でも、より上のレベルにあるノード（＝上面から見えるノード）を先に取得できます。さらに、マップ（連想配列）を使って、各水平距離のノードがすでに記録済みかどうかを判定し、上面図に表示すべきノードだけを抽出します。

処理の流れ

1. ルートノードの水平距離を 0 に設定し、キューに追加します。
2. キューの先頭からノードを取り出し、その水平距離がマップに未登録であれば、ノードの値をマップに記録します。
3. 左の子ノードには「親の水平距離 − 1」、右の子ノードには「親の水平距離 + 1」を設定してキューに追加します。
4. キューが空になるまで 2〜3 を繰り返します。
5. 最後に、マップを水平距離の昇順で走査して値を出力します。

C++での実装例

#include <iostream>
#include <queue>
#include <map>
using namespace std;

struct Node {
    Node* left;
    Node* right;
    int h_dist;   // 水平距離
    int data;
};

Node* create_node(int key) {
    Node* node = new Node();
    node->left = node->right = NULL;
    node->data = key;
    return node;
}

void print_topview(Node* root) {
    if (root == NULL)
        return;
    queue<Node*> q;
    map<int, int> m;   // 水平距離 → ノードの値
    int h_dist = 0;
    root->h_dist = h_dist;
    q.push(root);
    cout << "指定された二分木の上面図:" << endl;
    while (!q.empty()) {
        Node* cur = q.front();
        q.pop();
        h_dist = cur->h_dist;
        // その水平距離で最初に現れたノードだけを記録
        if (m.count(h_dist) == 0)
            m[h_dist] = cur->data;
        if (cur->left) {
            cur->left->h_dist = h_dist - 1;
            q.push(cur->left);
        }
        if (cur->right) {
            cur->right->h_dist = h_dist + 1;
            q.push(cur->right);
        }
    }
    // 水平距離の昇順（左から右）に出力
    for (auto i = m.begin(); i != m.end(); i++) {
        cout << i->second << " ";
    }
}

int main() {
    Node* root = create_node(11);
    root->left = create_node(23);
    root->right = create_node(35);
    root->left->right = create_node(47);
    root->left->right->right = create_node(59);
    root->left->right->right->right = create_node(68);
    print_topview(root);
    return 0;
}

実行結果

指定された二分木の上面図:
23 11 35 68

コードの解説

この例では、次のような二分木を構築しています。

        11
       /  \
     23    35
       \
        47
          \
           59
             \
              68

各ノードの水平距離は、11 が 0、23 が −1、35 が +1、47 が 0、59 が +1、68 が +2 となります。レベル順走査では、各水平距離について最初に到達したノードだけをマップに記録するため、最終的に出力されるのは 23（−1）、11（0）、35（+1）、68（+2） の 4 つのノードです。std::map はキー（水平距離）で自動的にソートされるため、結果は左から右の順に表示されます。

計算量

• 時間計算量： O(n log n) ― 各ノードを 1 回ずつ訪問し（O(n)）、マップへの挿入・検索に O(log n) かかるためです。std::unordered_map を使えば O(n) まで改善できます。
• 空間計算量： O(n) ― キューとマップが最大で全ノード分のデータを保持するためです。

まとめ

二分木の上面図を求める問題は、レベル順走査とマップ（ハッシュ）を組み合わせることで効率的に解くことができます。この考え方は、下面図（ボトムビュー）や側面図を求める問題にもそのまま応用できるので、ぜひマスターしておきましょう。