C言語で指定したレベルのリーフノード（葉ノード）を出力する方法

この記事では、二分木（バイナリツリー）において、ユーザーが指定したレベル k にあるリーフノード（葉ノード）を出力する方法を解説します。

リーフノードとは、左ポインタと右ポインタがどちらも NULL になっている終端ノードのことです。つまり、そのノードには子ノードが存在せず、親ノードとしての役割を持たないノードを指します。

例

入力 : 11 22 33 66 44 88 77
出力 : 88 77

ここで k は、出力対象となる木のレベルを表しています。

基本的なアプローチは、すべてのノードを走査しながら、そのノードが子へのポインタを持っているかどうかを確認することです。左・右のいずれか一方、あるいは両方にポインタが存在すれば、そのノードはリーフノードではありません。

各ノードは再帰的に走査します。レベルごとに処理を進めていき、目的のレベルに到達した時点で、そのノードがリーフノードかどうかを判定して出力します。

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

アルゴリズム

START
    Step 1 -> 構造体型のノード変数を作成
        int data を宣言
        ノード型のポインタ *left, *right を宣言
    Step 2 -> new_data を引数にとるノード作成用関数を作成
        malloc を使ってノード型の一時変数 temp を確保
        temp->data = new_data を設定
        temp->left = temp->right = NULL を設定
        return temp
    Step 3 -> void leaf(struct node* root, int level) 関数を宣言
        IF root == NULL
            処理を終了
        End
        IF level == 1
            IF root->left == NULL && root->right == NULL
                root->data を出力
            End
        End
        ELSE IF level > 1
            leaf(root->left, level - 1) を呼び出し
            leaf(root->right, level - 1) を呼び出し
        End
    Step 4 -> main() 内での処理
        level = 4 を設定
        struct node* root = New(11) のように値を渡してノードを生成
        leaf(root, level) を呼び出し
STOP

C言語での実装例

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

// ノードの構造体定義
struct node {
    struct node* left;
    struct node* right;
    int data;
};

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

// リーフノードを見つけて出力する関数
void leaf(struct node* root, int level) {
    if (root == NULL)
        return;
    if (level == 1) {
        if (root->left == NULL && root->right == NULL)
            printf("%d\n", root->data);
    } else if (level > 1) {
        leaf(root->left, level - 1);
        leaf(root->right, level - 1);
    }
}

int main() {
    printf("leaf nodes are: ");
    struct node* root = New(11);
    root->left = New(22);
    root->right = New(33);
    root->left->left = New(66);
    root->right->right = New(44);
    root->left->left->left = New(88);
    root->left->left->right = New(77);
    int level = 4;
    leaf(root, level);
    return 0;
}

実行結果

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

leaf nodes are: 88 77

このように、レベル4に存在するノードのうち、子を持たない「88」と「77」だけが出力されていることがわかります。同じレベルでも子ノードを持つノード（例：66 や 44）はリーフノードではないため、出力から除外されます。