C言語で二分木の右側ビュー（Right View）を出力する方法

この記事では、与えられた二分木の「右側ビュー（Right View）」――すなわち、木を右側から見たときに見えるノード――を出力するC言語プログラムについて解説します。まずデータを挿入して二分木を構築し、その後、完成した木の右側ビューを画面に表示します。

上の図は、ノード10・42・93・14・35・96・57・88から構成される二分木を表しています。この中で木の右側に位置するノードが選ばれ、画面に表示されます。たとえば、10・93・57・88がこの二分木における最も右側のノードに該当します。

実行例

入力：10 42 93 14 35 96 57 88
出力：10 93 57 88

二分木の各ノードには「left」と「right」という2つのポインタが用意されています。本問題では右側のノードのみを走査すればよいため、ノードの左の子を意識する必要はありません。

右側ビューには、各レベル（階層）の末尾にあたるノード、つまりそのレベルで最も右にあるノードがすべて含まれます。そこで、「右部分木を先に、左部分木を後に」走査する再帰的なアプローチを採用することで、目的のノードを簡単に抽出できます。プログラムは、それまでに到達した最大レベルより深いレベルのノードを見つけるたびに、そのノードを出力します。右部分木から先に探索するため、その時点で訪問したノードは必ずそのレベルの最も右側のノードになるからです。

以下のコードは、このアルゴリズムをC言語で実装したものです。

アルゴリズム

START
    Step 1 -> 構造体型のノード変数を作成
        int data を宣言
        ノード型ポインタ *left, *right を宣言
    Step 2 -> 引数 item を持つノード挿入用関数を作成
        malloc を使ってノード型の一時変数 temp を確保
        temp->data = item を設定
        temp->left = temp->right = NULL を設定
        temp を返す
    Step 3 -> 関数 void right_view(struct node *root, int level, int *end_level) を定義
        IF root == NULL ならば
            Return
        IF *end_level < level ならば
            root->data を出力
            *end_level = level を設定
            right_view(root->right, level+1, end_level) を呼び出す
            right_view(root->left, level+1, end_level) を呼び出す
    Step 4 -> 関数 void right(struct node *root) を定義
        int level = 0 を設定
        right_view(root, 1, &level) を呼び出す
    Step 5 -> main() 内で
        struct node *root = New(10) として木のノード値を設定
        right(root) を呼び出す
STOP

C言語での実装例

#include<stdio.h>
#include<stdlib.h>

/* 二分木のノードを表す構造体 */
struct node {
    int data;
    struct node *left, *right;
};

/* 新しいノードを生成する関数 */
struct node *New(int item) {
    struct node *temp = (struct node *)malloc(sizeof(struct node));
    temp->data = item;
    temp->left = temp->right = NULL;
    return temp;
}

/* 右側ビューを再帰的に出力する関数 */
void right_view(struct node *root, int level, int *end_level) {
    if (root == NULL) return;
    if (*end_level < level) {
        printf("%d\t", root->data);
        *end_level = level;
    }
    right_view(root->right, level+1, end_level);
    right_view(root->left, level+1, end_level);
}

/* 右側ビューの出力を開始する関数 */
void right(struct node *root) {
    int level = 0;
    right_view(root, 1, &level);
}

int main() {
    printf("right view of a binary tree is : ");
    struct node *root = New(10);
    root->left = New(42);
    root->right = New(93);
    root->left->left = New(14);
    root->left->right = New(35);
    root->right->left = New(96);
    root->right->right = New(57);
    root->right->left->right = New(88);
    right(root);
    return 0;
}

出力結果

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

right view of a binary tree is : 10 93 57 88

計算量について

このアルゴリズムは各ノードを一度だけ訪問するため、時間計算量はノード数を n として O(n) となります。また、再帰呼び出しに必要なスタック領域は木の高さ h に比例し、空間計算量は O(h) です。平衡な二分木であれば O(log n)、最悪ケース（線形に偏った木）では O(n) になります。