アルゴリズム

C言語で実装する紐付き2分木：ポインタ構造を活用した木データ構造の扱いについて解説

2025-01-17更新日: 2025-01-17

この記事ではC言語を使った紐付き2分木の実装方法を解説します。

ポインタ構造を活用して各ノードの連結や操作を行う手法を、具体的なコード例とともに説明しています。

要素ごとの処理や基本的なアルゴリズムについても触れ、実践に役立つ内容となっています。

目次から探す

紐付き2分木とポインタ構造の基礎

紐付き2分木の概念

紐付き2分木は、各ノードが左の子ノードおよび右の子ノードへのポインタを持つデータ構造です。

各ノードはデータとともに、必要に応じて親ノードへのポインタなどの追加情報を保持することも可能です。

基本的な性質として、各ノードが2つの枝(左と右)を持つため、ツリーの走査アルゴリズムや操作が効率的に実装できます。

ポインタ構造の概要

C言語では、データ構造を動的に扱うためにポインタ構造が頻繁に利用されます。

紐付き2分木では、各ノードが次のノードのアドレスを保持することにより、データの挿入・削除・走査などを動的に行うことが可能です。

動的メモリ割り当て関数であるmallocやfreeを使用することで、メモリの管理が柔軟に行えます。

C言語での実装の特徴

C言語で紐付き2分木を実装する際は、構造体を用いてノードの属性を定義し、ポインタで各ノード間の関係を管理します。

コンパイル環境が整っている場合、標準ライブラリの関数を活用してメモリ管理や文字列操作なども行え、効率的な実装が可能です。

型安全性に注意しながら、必要な検査(例えば、メモリ割り当ての失敗チェック)を行う点も重要です。

紐付き2分木のデータ構造設計

ノード構造体の定義

紐付き2分木の基本となるノードは、データ部分と左・右の子ノードを指すポインタで構成されます。

以下は、C言語での典型的なノード構造体の定義例です。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;                    // ノードのキー値
    struct Node* left;          // 左の子ノードへのポインタ
    struct Node* right;         // 右の子ノードへのポインタ
} Node;
int main(void) {
    // メイン関数内での動作確認用コード
    Node* root = NULL; // 初期状態では木は空
    printf("Node structure defined.\\n");
    return 0;
}

Node structure defined.

各メンバの役割と設計ポイント

key: ノードに格納されるデータであり、検索や並び替えの基準となります。数値の場合はソートや比較が容易です。
leftおよびright: 各々、子ノードのアドレスを格納するポインタです。動的にノードを割り当てる際は必ず初期値をNULLに設定する必要があります。

各メンバは、データの整合性を保つために、NULLチェックや範囲チェックを行うことが推奨されます。

ノードの生成と初期化

新たなノードを作成する場合、動的メモリ割り当てを利用してmallocでメモリを確保し、各ポインタメンバを初期化します。

生成後すぐに各子ポインタをNULLに設定しておくことが、予期せぬポインタ参照エラーを防ぐポイントです。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
// 新しいノードを生成する関数
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\\n");
        exit(EXIT_FAILURE);
    }
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
int main(void) {
    // ノード生成の動作確認
    Node* node = createNode(10);
    printf("Node with key %d created.\\n", node->key);
    // 生成したノードのメモリを解放
    free(node);
    return 0;
}

Node with key 10 created.

メモリ割り当ての注意点

malloc使用後は、返却値がNULLでないか必ずチェックします。

NULLの場合は、メモリ割り当てに失敗したとみなし、適切なエラーメッセージを表示してプログラムを終了するか、エラー処理を実施する必要があります。

また、使用後のメモリ解放freeも適切に行い、メモリリークを防ぐことが求められます。

紐付き2分木の操作実装

挿入処理の実装

紐付き2分木で新しい値を挿入する際は、既存のノードとの大小関係に基づいて新ノードの配置位置を決定します。

探索と同様に、再帰的なアプローチで挿入位置を探索する方法が一般的です。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
// 新しいノードを生成する関数
Node* createNode(int key) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("Memory allocation failed.\\n");
        exit(EXIT_FAILURE);
    }
    newNode->key = key;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
// 二分木にノードを挿入する関数
Node* insertNode(Node* root, int key) {
    if (root == NULL) {
        return createNode(key);
    }
    if (key < root->key) {
        root->left = insertNode(root->left, key);
    } else if (key > root->key) {
        root->right = insertNode(root->right, key);
    }
    // 重複するキーは無視する
    return root;
}
int main(void) {
    Node* root = NULL;
    // 挿入処理のテスト
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    printf("Nodes inserted successfully.\\n");
    // メモリ解放は再帰的な削除関数で行うことが推奨
    return 0;
}

Nodes inserted successfully.

アルゴリズムの流れと工夫

挿入するキーをルートノードと比較し、小さい場合は左部分木、大きい場合は右部分木へ再帰的に探索する。
挿入位置がNULLになったら、新たなノードを生成し、その箇所に割り当てる。

この流れにより、ツリーの整合性が保たれ、再帰呼び出しによってコードがシンプルになります。

重複値は基本的に無視する設計にしておくと、ツリー構造が安定して動作します。

探索処理の実装

ツリー内の特定のキーを探索する際、再帰的な探索アルゴリズムを用いることで、比較対象を絞った効率的な検索が可能です。

キーが見つかれば該当するノードのポインタを返します。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
// 二分木の探索を行う関数(再帰的アプローチ)
Node* searchNode(Node* root, int key) {
    if (root == NULL || root->key == key) {
        return root;
    }
    if (key < root->key) {
        return searchNode(root->left, key);
    } else {
        return searchNode(root->right, key);
    }
}
int main(void) {
    // テスト用の木を構築
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    Node* found = searchNode(root, 30);
    if (found != NULL) {
        printf("Key %d found.\\n", found->key);
    } else {
        printf("Key not found.\\n");
    }
    return 0;
}

Key 30 found.

再帰的探索の利用方法

再帰函数を利用することで、各ノードに対する比較がシンプルに記述できます。

基本ケースとして、探索対象が見つかった場合や、木の末端NULLに到達した場合に処理を終了する設計になっており、再帰呼び出しが自然な流れを作り出します。

削除処理の実装

ノード削除は、ツリーの構造を維持しながら対象ノードを取り除く処理です。

削除すべきノードが子ノードを持つ場合は、適切な後継ノード(または前任ノード)と入れ替える手法が用いられます。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
// 最小値ノードを取得する補助関数
Node* findMin(Node* root) {
    while (root->left != NULL) {
        root = root->left;
    }
    return root;
}
// ノード削除を行う関数
Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return root;
    }
    if (key < root->key) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->key) {
        root->right = deleteNode(root->right, key);
    } else {
        // ノードが見つかった場合の処理
        if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }
        // 右部分木の最小値ノードを取得して入れ替える
        Node* temp = findMin(root->right);
        root->key = temp->key;
        root->right = deleteNode(root->right, temp->key);
    }
    return root;
}
int main(void) {
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    root = insertNode(root, 20);
    root = deleteNode(root, 30);
    printf("Node deletion completed.\\n");
    return 0;
}

Node deletion completed.

削除時の注意点とメモリ管理

ノード削除では、削除対象ノードが子ノードを持つ場合の再配置や、メモリの適切な解放が重要です。

削除に伴うポインタの更新ミスがあると、ツリーの整合性が崩れ、プログラムの不具合に繋がるため、各ケースに分けた適切な実装が求められます。

木構造の走査と再帰処理の応用

前順走査の実装例

前順走査では、現在のノードを先に処理し、その後左部分木、右部分木の順に走査を行います。

以下はその実装例です。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
void preOrderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    printf("%d ", root->key);  // 現在のノードを表示
    preOrderTraversal(root->left);
    preOrderTraversal(root->right);
}
int main(void) {
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    printf("Pre-order traversal: ");
    preOrderTraversal(root);
    printf("\\n");
    return 0;
}

Pre-order traversal: 50 30 70

中順走査の実装例

中順走査は、左部分木→現在のノード→右部分木の順に走査を行います。

昇順に整列されたノードのキーが出力されるのが特徴です。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
void inOrderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    inOrderTraversal(root->left);
    printf("%d ", root->key);
    inOrderTraversal(root->right);
}
int main(void) {
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    printf("In-order traversal: ");
    inOrderTraversal(root);
    printf("\\n");
    return 0;
}

In-order traversal: 30 50 70

後順走査の実装例

後順走査では、左部分木、右部分木を先に走査し、最後に現在のノードを処理します。

主にメモリ解放などで用いられる手法です。

#include <stdio.h>
#include <stdlib.h>
// Node構造体の定義
typedef struct Node {
    int key;
    struct Node* left;
    struct Node* right;
} Node;
void postOrderTraversal(Node* root) {
    if (root == NULL) {
        return;
    }
    postOrderTraversal(root->left);
    postOrderTraversal(root->right);
    printf("%d ", root->key);
}
int main(void) {
    Node* root = NULL;
    root = insertNode(root, 50);
    root = insertNode(root, 30);
    root = insertNode(root, 70);
    printf("Post-order traversal: ");
    postOrderTraversal(root);
    printf("\\n");
    return 0;
}