データ構造とアルゴリズムI実習(第二回)

以下の課題を解け．
C言語によるプログラミング，コンパイルおよび実行は paiza.ioにアクセスすれば，すべてWeb上で行うことができる．
必要に応じて講義資料を参考にすること．講義資料はここにある．課題の提出期限および提出方法は以下の通りとする．

提出期限： 7月7日(月)23:59

提出方法：課題4は必ず提出すること．課題5の提出は任意である．いずれの課題もソースコードと実行結果をMyKONANに提出すること．

課題4(必須課題):

以下のCプログラムの search 関数の中身を埋めて二分探索木の探索アルゴリズムの実装を完成させよ．
実装が完了したら，探索のテストを行ってみよ．
ただし，また，このプログラムの入力の形式は以下の通りである．

n
key₁
…
key_n

ここで，nは検索を行う回数とし，key_iをキーとする．（合わせてn+1行になる．）
実行に際して，複数のキーで探索し，正しく検索されるかを確かめること．

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

struct BinarySearchTree {
   int key;
   int value;
   struct BinarySearchTree *left;
   struct BinarySearchTree *right;
};

int search(struct BinarySearchTree *r, int key) {
    [ここに二分探索木の探索アルゴリズムを書け]
}

int main() {
    int n, m, i, key, value;
    struct BinarySearchTree n2, n4, n6, n8, n10, n12, n14;

    /* 二分探索木の初期化 */
    n8.key = 8;
    n8.value = 64;
    n8.left = &n4;
    n8.right = &n12;

    n4.key = 4;
    n4.value = 16;
    n4.left = &n2;
    n4.right = &n6;

    n2.key = 2;
    n2.value = 4;
    n2.left = NULL;
    n2.right = NULL;

    n6.key = 6;
    n6.value = 36;
    n6.left = NULL;
    n6.right = NULL;

    n12.key = 12;
    n12.value = 144;
    n12.left = &n10;
    n12.right = &n14;

    n10.key = 10;
    n10.value = 100;
    n10.left = NULL;
    n10.right = NULL;

    n14.key = 14;
    n14.value = 196;
    n14.left = NULL;
    n14.right = NULL;

    /* 二分探索木の探索 */
    scanf("%d", &n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        printf("キー(%d)を探索．\n", key);
        value = search(&n8, key);
        if (value == -1) {
            printf("キー(%d)を持つレコードは登録されていません．\n", key);
        } else {
            printf("キー(%d)の値は%dです．\n", key, value);
        }
    }
}

課題5(発展課題):

課題4のプログラムでは最初からいくつかのレコードが登録されていた．
課題5では，課題4のプログラムを以下のように書き換えて，任意のレコードが登録できるようにしたい．
まず，regist 関数の中身を埋めて二分探索木の登録アルゴリズムの実装を完成させよ．
次に，以下の main 関数を用いて任意の数のレコードを登録できるようにせよ．
実装が完了したら，登録と探索のテストを行ってみよ．
ただし，このプログラムの入力の形式は以下の通りである．

n
key₁
value₁
…
key_n
value_n
m
key₁
…
key_m

ここで，nは登録するレコード数，mは検索を行う回数とし，key_iをキー，value_iをデータ（値）とする．（合わせて2+2n+m行になる．）
実行に際して，複数のキーと値を登録した表をさまざまなキーで探索し，入力したキーに対応する値が正しく検索されるかを確かめること．

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

struct BinarySearchTree {
   int key;
   int value;
   struct BinarySearchTree *left;
   struct BinarySearchTree *right;
};

int search(struct BinarySearchTree *r, int key) {
    [課題4と同じ]
}

struct BinarySearchTree *regist(struct BinarySearchTree *r, int key, int value) {
    struct BinarySearchTree *p;
    if (r == NULL) {
        /* 初回登録の場合 */
        r = malloc(sizeof(struct BinarySearchTree));
        r->key = key;
        r->value = value;
        r->left = NULL;
        r->right = NULL;
        return r;
    }
    [ここに二分探索木の登録アルゴリズムを書け]
}

int main() {
    int n, m, i, key, value;
    struct BinarySearchTree *root = NULL;

    /* 二分探索木への登録 */
    scanf("%d", &n);
    printf("レコード数(%d)\n", n);
    for (i = 0; i < n; i++) {
        scanf("%d", &key);
        scanf("%d", &value);
        printf("キー(%d), データ(%d)を登録\n", key, value);
        if (root == NULL) {
            /* 初回登録の場合 */
            root = regist(root, key, value);
        } else {
            /* 二回目以降の登録の場合 */
            regist(root, key, value);
        }
    }

    /* 二分探索木の探索 */
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        scanf("%d", &key);
        printf("キー(%d)を探索．\n", key);
        value = search(root, key);
        if (value == -1) {
            printf("キー(%d)を持つレコードは登録されていません．\n", key);
        } else {
            printf("キー(%d)の値は%dです．\n", key, value);
        }
    }
}