アルゴリズム

C言語による木構造の実装：ノードとポインタを利用した基本操作の解説

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

この記事では、C言語でノードとポインタを活用し、基本的な木構造の構築と操作方法を解説します。

構造体によるノードの定義や動的なメモリ管理を利用し、木の生成や探索、挿入などの基本操作を具体例とともに紹介します。

目次から探す

ノードの定義と生成
- 構造体によるノード定義
- ノード生成関数と動的メモリ管理
木構造の構築
木構造の走査方法
ポインタ操作とエラー処理
- ポインタの基本操作と利用方法
- nullポインタの扱いとエラーチェック
まとめ

ノードの定義と生成

構造体によるノード定義

二分木の各ノードは、データと左右の子ノードへのポインタを持つ構造体として定義されます。

以下のサンプルコードでは、Node という名前の構造体を定義し、整数型のデータと左右の子ノードへのポインタをメンバとして持たせています。

#include <stdio.h>
#include <stdlib.h>
// 二分木の各ノードを表す構造体
typedef struct Node {
    int data;               // ノードのデータ
    struct Node *left;      // 左の子ノードへのポインタ
    struct Node *right;     // 右の子ノードへのポインタ
} Node;
int main(void) {
    // ノードが正常に定義されているか確認するためのサンプル
    Node node;
    node.data = 10;
    node.left = NULL;
    node.right = NULL;
    printf("Node data: %d\n", node.data);
    return 0;
}

Node data: 10

ノード生成関数と動的メモリ管理

動的メモリ割り当てを利用してノードを生成する方法は、木構造の実装では非常に重要です。

下記のサンプルコードでは、createNode関数で必要なメモリを確保し、ノードに初期値を設定しています。

メモリ確保に失敗した場合はエラーメッセージを表示してプログラムを終了します。

#include <stdio.h>
#include <stdlib.h>
// 二分木のノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// 新しいノードを生成する関数
Node* createNode(int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}
int main(void) {
    // 動的にノードを生成して値を設定
    Node *root = createNode(20);
    printf("Created node with data: %d\n", root->data);
    free(root); // メモリの解放
    return 0;
}

Created node with data: 20

木構造の構築

木構造設計の基本

木構造を設計する際は、各ノード間の関係性を明確にします。

二分木の場合、各ノードは左右の子ノードへのポインタを保持するため、再帰的な構造で実装することが一般的です。

これにより、挿入や走査などの基本操作がシンプルに実装できます。

ノードの挿入処理

新しいノードを既存の木構造に挿入する方法には、再帰的な方法と非再帰的(反復的)な方法があります。

ここではその両方の実装例を示します。

再帰的挿入アルゴリズム

再帰を利用すると、コードがシンプルに記述できるため、左右の枝に対して同様の操作を行う場合に適しています。

以下は、値を比較しながら適切な位置にノードを挿入するサンプルコードです。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
// 再帰的にノードを挿入する関数
Node* insertRecursive(Node* root, int value) {
    if(root == NULL) {
        return createNode(value);
    }
    if(value < root->data) {
        root->left = insertRecursive(root->left, value);
    } else {
        root->right = insertRecursive(root->right, value);
    }
    return root;
}
int main(void) {
    Node* root = NULL;
    // 値を順次挿入
    root = insertRecursive(root, 50);
    root = insertRecursive(root, 30);
    root = insertRecursive(root, 70);
    root = insertRecursive(root, 20);
    root = insertRecursive(root, 40);
    root = insertRecursive(root, 60);
    root = insertRecursive(root, 80);
    printf("Nodes inserted recursively.\n");
    // 木のメモリ解放は後述の関数を利用できます
    return 0;
}

Nodes inserted recursively.

非再帰的挿入方法

反復処理を利用した挿入方法では、再帰呼び出しによるオーバーヘッドを回避できます。

下記のサンプルコードは、while ループを使用して新しいノードの挿入位置を探索し、挿入を行う方法を示しています。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
// 非再帰的にノードを挿入する関数
Node* insertIterative(Node* root, int value) {
    Node* newNode = createNode(value);
    if(root == NULL) {
        return newNode;
    }
    Node* current = root;
    Node* parent = NULL;
    while(current != NULL) {
        parent = current;
        if(value < current->data)
            current = current->left;
        else
            current = current->right;
    }
    if(value < parent->data)
        parent->left = newNode;
    else
        parent->right = newNode;
    return root;
}
int main(void) {
    Node* root = NULL;
    // 値を非再帰的に挿入
    root = insertIterative(root, 50);
    root = insertIterative(root, 30);
    root = insertIterative(root, 70);
    root = insertIterative(root, 20);
    root = insertIterative(root, 40);
    root = insertIterative(root, 60);
    root = insertIterative(root, 80);
    printf("Nodes inserted iteratively.\n");
    // 木のメモリ解放は後述の関数を利用できます
    return 0;
}

Nodes inserted iteratively.

ノードの削除とメモリ解放

不要となったノードを適切に削除し、動的に確保したメモリを解放することは、メモリリーク防止のために非常に重要です。

特に木構造の場合、後順走査を利用して子ノードから順に解放する方法が有効です。

再帰的削除アルゴリズム

後順走査により、左右の子ノードを先に解放してから根ノードを解放するアルゴリズムを実装します。

以下のサンプルコードでは、freeTree関数を利用して木全体のメモリ解放を行っています。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// ノード生成関数(他のセクションでも利用)
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
// 木全体のメモリを再帰的に解放する関数
void freeTree(Node* root) {
    if(root == NULL) {
        return;
    }
    freeTree(root->left);
    freeTree(root->right);
    // ノード解放前に必要であればログ出力も可能
    // printf("Freeing node with data: %d\n", root->data);
    free(root);
}
int main(void) {
    // サンプルとして簡単な木を作成
    Node* root = (Node*)malloc(sizeof(Node));
    if(root == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    root->data = 100;
    root->left = createNode(50);
    root->right = createNode(150);
    // 木全体のメモリ解放
    freeTree(root);
    printf("Tree memory freed.\n");
    return 0;
}

Tree memory freed.

木構造の走査方法

前順走査 (Preorder Traversal)

前順走査では、まずルートノードを訪問し、その後左の部分木、最後に右の部分木の順で走査を行います。

再帰的に実装することで、シンプルなコードとなります。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// 前順走査 (Preorder Traversal) を行う関数
void preorderTraversal(Node* root) {
    if(root == NULL) return;
    printf("%d ", root->data);
    preorderTraversal(root->left);
    preorderTraversal(root->right);
}
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
int main(void) {
    // サンプル木の作成
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Preorder Traversal: ");
    preorderTraversal(root);
    printf("\n");
    return 0;
}

Preorder Traversal: 1 2 4 5 3

中順走査 (Inorder Traversal)

中順走査では、左の部分木、ルートノード、右の部分木の順で走査を行います。

特に二分探索木の場合、昇順にデータを取得できる特徴があります。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// 中順走査 (Inorder Traversal) を行う関数
void inorderTraversal(Node* root) {
    if(root == NULL) return;
    inorderTraversal(root->left);
    printf("%d ", root->data);
    inorderTraversal(root->right);
}
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
int main(void) {
    // サンプル木の作成
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Inorder Traversal: ");
    inorderTraversal(root);
    printf("\n");
    return 0;
}

Inorder Traversal: 4 2 5 1 3

後順走査 (Postorder Traversal)

後順走査は、左の部分木、右の部分木、最後にルートノードの順で走査を行います。

ノードの削除処理など、子ノードから先に処理を行う場合に有用です。

#include <stdio.h>
#include <stdlib.h>
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// 後順走査 (Postorder Traversal) を行う関数
void postorderTraversal(Node* root) {
    if(root == NULL) return;
    postorderTraversal(root->left);
    postorderTraversal(root->right);
    printf("%d ", root->data);
}
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
int main(void) {
    // サンプル木の作成
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Postorder Traversal: ");
    postorderTraversal(root);
    printf("\n");
    return 0;
}

Postorder Traversal: 4 5 2 3 1

幅優先探索 (Level Order Traversal)

幅優先探索では、根ノードから各レベルごとにノードを訪問していきます。

キューを利用して実装することで、レベル順にノードを処理することが可能です。

下記のサンプルコードは、配列を用いた簡単なキュー実装を含んでいます。

#include <stdio.h>
#include <stdlib.h>
#define MAX_QUEUE_SIZE 100
// ノード定義
typedef struct Node {
    int data;
    struct Node *left;
    struct Node *right;
} Node;
// キュー構造体の定義
typedef struct {
    Node* data[MAX_QUEUE_SIZE];
    int front;
    int rear;
} Queue;
// キューの初期化
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}
// キューが空か判定
int isEmpty(Queue* q) {
    return q->front == q->rear;
}
// キューにノードを追加
void enqueue(Queue* q, Node* node) {
    if(q->rear == MAX_QUEUE_SIZE) {
        printf("Queue is full\n");
        exit(EXIT_FAILURE);
    }
    q->data[q->rear++] = node;
}
// キューからノードを取り出す
Node* dequeue(Queue* q) {
    if(isEmpty(q)) {
        return NULL;
    }
    return q->data[q->front++];
}
// 幅優先探索 (Level Order Traversal) を行う関数
void levelOrderTraversal(Node* root) {
    if(root == NULL) return;
    Queue q;
    initQueue(&q);
    enqueue(&q, root);
    while(!isEmpty(&q)) {
        Node* current = dequeue(&q);
        printf("%d ", current->data);
        if(current->left != NULL)
            enqueue(&q, current->left);
        if(current->right != NULL)
            enqueue(&q, current->right);
    }
}
// ノード生成関数
Node* createNode(int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if(newNode == NULL) {
        printf("Memory allocation failed\n");
        exit(EXIT_FAILURE);
    }
    newNode->data = value;
    newNode->left = newNode->right = NULL;
    return newNode;
}
int main(void) {
    // サンプル木の作成
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);
    printf("Level Order Traversal: ");
    levelOrderTraversal(root);
    printf("\n");
    return 0;
}

Level Order Traversal: 1 2 3 4 5

ポインタ操作とエラー処理

ポインタの基本操作と利用方法

C言語においてポインタは、メモリ上のアドレスを扱うための重要な要素です。

変数のアドレスを格納し、間接参照を行うことで、動的メモリへのアクセスや効率的なデータ操作が可能となります。

下記のサンプルコードでは、基本的なポインタの宣言や参照方法について紹介します。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    int value = 100;
    int *ptr = &value;  // ポインタの初期化
    printf("Value: %d\n", value);
    printf("Pointer points to address: %p\n", (void*)ptr);
    printf("Value via pointer: %d\n", *ptr);
    return 0;
}

Value: 100
Pointer points to address: 0x7ffeefbff5ac
Value via pointer: 100

アドレスの表示は環境により異なります。

nullポインタの扱いとエラーチェック

動的メモリを扱う際は、malloc などの関数によって返されるポインタが NULL でないかどうかの確認が必須です。

NULL ポインタを参照するとプログラムが異常終了する可能性があるため、エラーチェックを実装するようにしましょう。

以下のサンプルコードは、メモリ割り当て後に NULL チェックを行い、問題がなければデータの操作を続ける例を示しています。

#include <stdio.h>
#include <stdlib.h>
int main(void) {
    // 整数型のメモリを動的に確保
    int *ptr = (int*)malloc(sizeof(int));
    if(ptr == NULL) {
        printf("Memory allocation failed\n");
        return 1;
    }
    *ptr = 200;
    printf("Allocated value: %d\n", *ptr);
    free(ptr);           // メモリ解放
    ptr = NULL;          // 解放後、明示的にNULLをセット
    if(ptr == NULL) {
        printf("Pointer is now null after free.\n");
    }
    return 0;
}

Allocated value: 200
Pointer is now null after free.

まとめ

本記事では、C言語で木構造を実装するための基本を解説しました。

ノードの構造体定義、動的メモリ管理、再帰的・反復的なノード挿入、ノード削除とメモリ解放の手法、前順・中順・後順走査および幅優先探索について、各サンプルコードを交えて説明しています。

また、ポインタの基本操作やnullポインタのエラーチェックについても学ぶことができ、実践的なC言語プログラミングの理解に役立つ内容となっています。