二分探索木の実装と操作方法

まず、二分探索木のノードを表す構造体を定義します。

struct Node {
    int data;
    struct Node* left;
    struct Node* right;
};

次に、挿入操作を実装します。新しいノードを挿入するために、再帰的なアプローチを使用します。

struct Node* insert(struct Node* root, int data) {
    if (root == NULL) {
        // 新しいノードを作成し、データを設定します
        struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
        newNode->data = data;
        newNode->left = NULL;
        newNode->right = NULL;
        return newNode;
    }
// データが現在のノードのデータより小さい場合、左のサブツリーに挿入します
    if (data < root->data) {
        root->left = insert(root->left, data);
    }
// データが現在のノードのデータより大きい場合、右のサブツリーに挿入します
    else if (data > root->data) {
        root->right = insert(root->right, data);
    }
    return root;
}

次に、削除操作を実装します。削除するノードの場合分けが必要です。以下に、削除操作の一般的なアルゴリズムの例を示します。

struct Node* delete(struct Node* root, int data) {
    if (root == NULL) {
        return root;
    }
    if (data < root->data) {
        root->left = delete(root->left, data);
    } else if (data > root->data) {
        root->right = delete(root->right, data);
    } else {
        // 削除するノードが見つかった場合
        // 子がいない場合または片方の子しか持たない場合
        if (root->left == NULL) {
            struct Node* temp = root->right;
            free(root);
            return temp;
        } else if (root->right == NULL) {
            struct Node* temp = root->left;
            free(root);
            return temp;
        }
// 両方の子を持つ場合、右部分木の最小値を使用して置き換える
        struct Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = delete(root->right, temp->data);
    }
    return root;
}

最後に、探索操作を実装します。再帰的なアプローチを使用して、指定されたデータを持つノードを見つけます。

struct Node* search(struct Node* root, int data) {
    if (root == NULL || root->data == data) {
        return root;
    }
    if (data < root->data) {
        return search(root->left, data);
    } else {
        return search(root->right, data);
    }
}

上記の関数を使用して、二分探索木を操作することができます。挿入、削除、探索操作を適切な引数とともに呼び出すことで、データを管理できます。

例えば、以下のようなメイン関数を作成してみましょう。

int main() {
    struct Node* root = NULL;
    root = insert(root, 50);
    root = insert(root, 30);
    root = insert(root, 20);
    root= insert(root, 40);
    root = insert(root, 70);
    root = insert(root, 60);
    root = insert(root, 80);
    printf("二分探索木の中序順での表示: ");
    inorderTraversal(root);
    printf("\n");
    printf("探索結果: ");
    struct Node* result = search(root, 40);
    if (result != NULL) {
        printf("データ %d が見つかりました\n", result->data);
    } else {
        printf("データが見つかりませんでした\n");
    }
    root = delete(root, 30);
    printf("削除後の二分探索木の中序順での表示: ");
    inorderTraversal(root);
    printf("\n");
    return 0;
}

この例では、いくつかのデータを二分探索木に挿入し、中序順で表示しています。また、指定したデータを探索し、削除後の木を再度表示しています。

これで、二分探索木の実装と操作方法についてのブログ投稿が完成しました。