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

課題3解答例(必須課題):

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

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

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

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

int search(struct BinarySearchTree *r, int key) {
    while (r != NULL) {
        if (r->key == key) return r->data;
        else if (r->key > key) r = r->left;
        else r = r->right;
    }
    return -1;
}

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

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

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

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

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

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

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

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

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

課題4解答例(発展課題):

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

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

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

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

int search(struct BinarySearchTree *r, int key) {
    while (r != NULL) {
        if (r->key == key) return r->data;
        else if (r->key > key) r = r->left;
        else r = r->right;
    }
    return -1;
}

struct BinarySearchTree *regist(struct BinarySearchTree *r, int key, int data) {
    struct BinarySearchTree *p;
    if (r == NULL) {
        /* 初回登録の場合 */
        r = malloc(sizeof(struct BinarySearchTree));
        r->key = key;
        r->data = data;
        r->left = NULL;
        r->right = NULL;
        return r;
    }
    for (;;) {
        if (r->key == key) {
            r->data = data;
            return r;
        } else if (r->key > key) {
            if (r->left == NULL) {
                p = malloc(sizeof(struct BinarySearchTree));
                r->left = p;
                break;
            }
            r = r->left;
        } else {
            if (r->right == NULL) {
                p = malloc(sizeof(struct BinarySearchTree));
                r->right = p;
                break;
            }
            r = r->right;
        }
    }
    p->key = key;
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    return p;
}

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

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

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