next up previous contents
Next: 27. 関数ポインタ Up: 26. バイナリーツリー Previous: 26. バイナリーツリー

26.1 課題 26

cd c を実行した後で( ~/c に移動した後で )、以下の課題を やってみよ。

課題 26.1
バイナリーツリー I

バイナリーツリーにデータをポインタを使って登録するような 一般的なプログラム btree.c を作成せよ。

但し、バイナリーツリーに登録に必要な値は整数とし、以下のように 登録する際にはデータへのポインタとその値とを引数に与えるように する。

    Btree *addCell( int point, void *data ){

なお、便利なように addCell() 関数は新しいセルのメモリ割り当てから、 ツリーへの登録まで全て行うようにせよ。

課題 26.2
バイナリーツリー II

23.3 の課題を利用し、 バイナリーツリーにファイルから読み込んだ学生のデータを登録するように せよ。但し、成績をキーにして登録せよ。次に、 登録後キーボードから入力された値がツリーにあるか否かを 表示し、ツリーにある場合にはその学生のデータを全て表示するように せよ。

作成したプログラムをメイルで creport まで送りなさい。題は、kadai26 とする事。

前回の復習
バイナリーツリー

バイナリーツリーは、以下の構造体でその要素を定義できる。
    struct BTREE {
        struct BTREE *left, *right;
        int point;
    };
    typedef struct BTREE Btree;
つまり、双方向リンクドリストに似て、2つの自分と同じような要素へのポインタ を持つが、リストと異なるのはそれが言わば木のように2次元的に拡がっていく 点にある。(リストは一次元的なイメージである)

バイナリーツリーに適切にデータが格納されたならば、その探索は比較的に早く 見つけることが出来るが、探索に用いられるキー以外のデータを検索しようと した場合、全てのツリーの探索は少し面倒な処理が必要である。



Noriyo Kanayama