C言語で高さを計算せずに完全二分木の中間レベルを出力する方法

このプログラムは、二分木の中間レベルに存在するノードを出力するものです。例えば、二分木が4つのレベルを持つ場合、2番目のレベルのノードを出力します。ここでのポイントは、木の高さ（深さ）を事前に計算することなく中間レベルを求めるという点です。

完全二分木とは？

完全二分木（Perfect Binary Tree）とは、すべての内部ノードが必ず2つの子ノードを持ち、すべての葉ノードが同じレベル（深さ）に位置する木のことです。

上図の場合：

• 内部ノードである21と32は、どちらも子ノードを持っています。
• 葉ノードである41、59、33、70は、すべて同じレベルに配置されています。

この2つの性質を満たしているため、これは完全二分木であると言えます。

入力と出力の例

入力 : 12 21 32 41 59 33 70
出力 : 21 32

アルゴリズムの考え方

ここで使用するアプローチは、連結リストの中間要素を見つける手法と似ています。再帰呼び出しを行いながら、ノードの左ポインタと右ポインタがNULLかどうかをチェックすることで、高さを明示的に計算せずに中間レベルを特定します。

具体的には、2つのポインタを使い、一方は1ステップずつ進み、もう一方は2ステップずつ進めることで、速い方のポインタが葉に到達した時点で、遅い方のポインタが中間レベルに位置する仕組みを利用しています。

アルゴリズムの手順

START
    Step 1 -> 構造体としてノード変数を作成
        int型のkeyを宣言
        node型のポインタ *left, *right を宣言
    Step 2 -> 値を引数としてノードを挿入する関数を作成
        mallocを使用してnode型の一時変数tempを宣言
        temp->data = value を設定
        temp->left = temp->right = NULL を設定
        return temp
    Step 3 -> 関数 void middle(struct Node* a, struct Node* b) を宣言
        IF a = NULL || b = NULL の場合
            Return
        IF ((b->left == NULL) && (b->right == NULL)) の場合
            a->key を出力
            Return
        End
        middle(a->left, b->left->left) を呼び出し
        middle(a->right, b->left->left) を呼び出し
    Step 4 -> 関数 void mid_level(struct Node* node) を宣言
        middle(node, node) を呼び出し
    Step 5 -> main() 内で
        挿入したい値を渡して New を呼び出す（例：struct Node* n1 = New(13);）
        mid_level(n1) を呼び出し
STOP

C言語による実装コード

以下のコードは、上記アルゴリズムのC言語実装例です。

#include <stdio.h>
#include<stdlib.h>
struct Node {
    int key;
    struct Node* left, *right;
};
struct Node* New(int value) {
    struct Node* temp = (struct Node*)malloc(sizeof(struct Node));
    temp->key = value;
    temp->left = temp->right = NULL;
    return (temp);
}
void middle(struct Node* a, struct Node* b) {
    if (a == NULL || b == NULL)
        return;
    if ((b->left == NULL) && (b->right == NULL)) {
        printf("%d ",a->key);
        return;
    }
    middle(a->left, b->left->left);
    middle(a->right, b->left->left);
}
void mid_level(struct Node* node) {
    middle(node, node);
}
int main() {
    printf("middle level nodes are : ");
    struct Node* n1 = New(13);
    struct Node* n2 = New(21);
    struct Node* n3 = New(44);
    struct Node* n4 = New(98);
    struct Node* n5 = New(57);
    struct Node* n6 = New(61);
    struct Node* n7 = New(70);
    n2->left = n4;
    n2->right = n5;
    n3->left = n6;
    n3->right = n7;
    n1->left = n2;
    n1->right = n3;
    mid_level(n1);
}

実行結果

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

middle level nodes are : 21 44

このように、木の高さを別途計算することなく、再帰的なポインタ操作だけで中間レベルのノード値「21」と「44」を効率的に出力できることが確認できます。