C言語で二分木の左側ビュー（Left View）を出力する方法を解説

この記事では、与えられた二分木（バイナリツリー）の左側ビュー（Left View）、すなわち木を左側から見たときに見えるノードを出力する方法を解説します。ユーザーがデータを挿入して二分木を構築し、その後、完成した木の左側ビューを表示するという流れです。

二分木の各ノードが持てる子は最大2つなので、プログラムは各ノードに紐づく左ポインタを優先的にたどる必要があります。

左ポインタがNULLでなければ、その先に子ノード（データ）が存在します。各レベルで最初に到達した最左ノードを出力対象とし、それを画面に表示します。

例

入力：1 0 3 2 4
出力：1 0 2

図のオレンジ色のノードが、二分木の左側ビューに相当します。

この図では、データ1を持つノードがルートノードなので最初に出力されます。次に左の子へ移動して0を出力し、続いて右側のノード3へ移動して、その左の子である2を出力します。

この問題は、ノードのレベル（深さ）を記録しながら再帰的に木を走査するアプローチで解けます。各レベルで最初に訪れたノードだけを出力することで、左側ビューが得られます。

アルゴリズム

START
    Step 1 -> ノード用の構造体を作成
        int型の data を宣言
        ノード型ポインタ *left, *right を宣言
    Step 2 -> ノード挿入用関数を作成（引数：new_data）
        mallocでノード型の一時変数 temp を確保
        temp->data = new_data を設定
        temp->left = temp->right = NULL を設定
        temp を返す
    Step 3 -> 関数 void left_view(struct node* root, int level, int* highest_level) を宣言
        root が NULL なら
            終了
        *highest_level < level なら
            root->data を出力
            *highest_level = level を設定
        left_view(root->left, level + 1, highest_level) を再帰呼び出し
        left_view(root->right, level + 1, highest_level) を再帰呼び出し
    Step 4 -> 関数 void left(struct node* root) を宣言
        int highest_level = 0 を設定
        left_view(root, 1, &highest_level) を呼び出す
    Step 5 -> main() 内で
        struct node* root = New(1) としてルートノードを作成
        left(root) を呼び出す
STOP

C言語での実装例

#include <stdio.h>
#include <stdlib.h>
// ノードの構造体を定義
struct node {
    int data;
    struct node *left, *right; // ノードに接続された子ノードを指すポインタ
};
struct node* New(int new_data) {
    struct node* temp = (struct node*)malloc(sizeof(struct node));
    // ポインタに動的にメモリを割り当てる
    temp->data = new_data;
    temp->left = temp->right = NULL;
    return temp;
}
void left_view(struct node* root, int level, int* highest_level) {
    if (root == NULL) // ノードが存在しない＝データがない場合
    return;
    // 木にルートノードしかない場合は、ルートノードをそのまま返す
    if (*highest_level < level) {
        printf("%d\t", root->data);
        *highest_level = level;
    }
    // 再帰呼び出し
    left_view(root->left, level + 1, highest_level);
    left_view(root->right, level + 1, highest_level);
}
void left(struct node* root) {
    int highest_level = 0;
    left_view(root, 1, &highest_level);
}
int main() {
    printf("left view of a binary tree is : ");
    struct node* root = New(1);
    root->left = New(0);
    root->right = New(3);
    root->right->left = New(2);
    root->right->right = New(4);
    left(root);
    return 0;
}

実行結果

上記のプログラムを実行すると、次の出力が得られます。

left view of a binary tree is : 1 0 2

動作のポイント

このアルゴリズムの鍵は highest_level 変数です。まだ出力していないレベルに初めて到達したときだけノードの値を表示し、そのレベル番号を記録します。左の子を先に再帰呼び出しするため、各レベルで最も左側のノードが最初に検出され、結果として左側ビューが得られます。計算量は全ノードを一度ずつ訪問するため O(n)、必要なメモリは再帰の深さに依存し、最悪ケースで O(n) となります。