【C言語】第8章第6回：ツリー構造と基本操作

2025年1月15日 a-mun

ツリー構造は、階層的にデータを管理する効率的なデータ構造です。本記事では、二分探索木（Binary Search Tree, BST）を例に挙げて、基本的な操作と実装方法を学びます。

Table of Contents

0. 記事の概要

この記事を読むメリット

データ管理の効率化：ツリー構造を利用して高速な検索と整理が可能になります。
応用力の向上：グラフアルゴリズムや高度なデータ構造への理解が深まります。
基礎的な技術の習得：二分探索木の基本操作を学べます。

この記事で学べること

ツリー構造の概念と特性
二分探索木の基本操作（挿入、削除、探索）
応用例：ツリーを用いたデータ管理

活用のイメージ

ツリー構造は、検索エンジンの索引作成、ファイルシステムのディレクトリ管理、ヒープソートやデータベースの設計に応用されます。

1. ツリー構造の基本

1.1 ツリー構造とは？

ツリー構造は、ルート（root）から始まり、各ノードが0個以上の子ノード（child）を持つ階層的なデータ構造です。

例：

ルートノード：データ構造の最上位
子ノード：ルートノードまたは他のノードから派生
葉ノード（リーフノード）：子を持たないノード

1.2 二分探索木（Binary Search Tree, BST）

二分探索木は、各ノードが最大2つの子を持つツリーで、左の子は親ノードより小さい値を、右の子は親ノードより大きい値を持つという特徴があります。

2. 二分探索木の実装

2.1 ノードの定義

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

// ノードの定義
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// ノードを作成
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

2.2 ノードの挿入

// ノードを挿入
Node* insert(Node* root, int data) {
    if (root == NULL) {
        return createNode(data);
    }
    if (data < root->data) {
        root->left = insert(root->left, data);
    } else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

2.3 ノードの探索

// ノードを探索
Node* search(Node* root, int key) {
    if (root == NULL || root->data == key) {
        return root;
    }
    if (key < root->data) {
        return search(root->left, key);
    }
    return search(root->right, key);
}

2.4 ノードの削除

// ノードを削除
Node* deleteNode(Node* root, int key) {
    if (root == NULL) {
        return root;
    }
    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    } else if (key > root->data) {
        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 = root->right;
        while (temp && temp->left != NULL) {
            temp = temp->left;
        }
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }
    return root;
}

2.5 ツリーの表示（中間順巡回）

// 中間順巡回
void inorder(Node* root) {
    if (root != NULL) {
        inorder(root->left);
        printf("%d ", root->data);
        inorder(root->right);
    }
}

int main() {
    Node* root = NULL;

    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("Inorder traversal: ");
    inorder(root);

    root = deleteNode(root, 50);
    printf("\nAfter deletion: ");
    inorder(root);

    return 0;
}

動作解説

ノードの作成：新しいノードを動的に確保し、データを格納します。
挿入操作：ツリーの規則に従ってノードを適切な位置に追加します。
探索操作：特定の値を持つノードを見つけます。
削除操作：特定のノードを削除し、ツリー構造を維持します。
表示操作：中間順巡回でツリーを表示します。

3. 練習問題

以下の課題に挑戦して、ツリー構造の理解を深めましょう。

ツリーの高さを計算する関数を作成してください。
ツリーを前順巡回（Preorder）で表示する関数を実装してください。
ツリーの全ノード数をカウントする関数を作成してください。

4. 練習問題の解答と解説

問1の解答

// ツリーの高さを計算
int height(Node* root) {
    if (root == NULL) {
        return 0;
    }
    int leftHeight = height(root->left);
    int rightHeight = height(root->right);
    return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}

int main() {
    Node* root = NULL;

    root = insert(root, 50);
    insert(root, 30);
    insert(root, 70);
    insert(root, 20);
    insert(root, 40);
    insert(root, 60);
    insert(root, 80);

    printf("Height of the tree: %d\n", height(root));

    return 0;
}

このプログラムでは、再帰を使用してツリーの高さを計算します。

5. まとめ

本記事では、ツリー構造の基本と二分探索木の基本操作を学びました。次回は、さらに高度なツリー操作とその応用について学びます。