先週までで、2分探索木の説明を終えたので、今日は演習を行う。

課題テーマ(基本)

2分探索木を使ったプログラムの作成。データ構造は、以下の中から出席番号にて選ぶ。(出席番号%3)

0. 名前と生年月日(年月日は別要素が望ましい)
1. 名前と電話番号
2. 学科・学年・出席番号・名前の名簿

上記のデータ構造にて、データを入力し「保存」、その後「検索」し目的のデータを表示する機能を実装せよ。

定番ではあるが、(a)プログラム説明、(b)プログラムリスト、(c)動作検証、(d)動作考察の観点で評価を行う。

課題テーマ(オプション)

上記の基本テーマは簡単であるため、オプションテーマを以下に示す。基本テーマの代わりにオプションテーマにてレポートを提出せよ。

数値をデータとする2分木を、その構造がイメージできるようにアスキーアート的に、あるいはグラフィック的に表示するプログラムを作成せよ。

(例1)            (例2)　　{[29] 51 [(60) 75 (80)]}
　　51
　／　＼          (例3)          51
29　　　75　                     |
　　　／　＼　　　　　　　+------+-------+
    60      80            |              |
                         29              75
                                         |
                                     +---+---+
                                     |       |
                                    60       80

(さらに…)

2分木へのデータの追記

前回の授業で、2分探索木のデータに対する処理を説明したので、今回は木にデータを追加する処理。

struct Tree {
    int data ;
    struct Tree* left ;
    struct Tree* right ;
} ;
struct Tree* tcons( int x, struct Tree*L, struct Tree*R )
{
    struct Tree* ans ;
    ans = (struct Tree*)malloc( sizeof( struct Tree ) ) ;
    if ( ans != NULL ) {
        ans->data  = x ;
        ans->left  = L ;
        ans->right = R ;
    }
    return ans ;
}
struct Tree* top = NULL ;
void insert( int x )
{
    struct Tree** tail = &top ; // 書換えるべき末端ポインタへのポインタ
    while( (*tail) != NULL ) {
        if ( (*tail)->data == x )
            break ; // 同じデータは重複するので、追加処理は行わない
        else if ( (*tail)->data > x )
            tail = &( (*tail)->left ) ; // 左の枝を降りていく
        else
            tail = &( (*tail)->right ) ; // 右の枝を降りていく
    }
    if ( (*tail) == NULL )
        (*tail) = tcons( x , NULL , NULL ) ;
}

単純リストの時は、2重ポインタの混ざった式の部分的に、型を意識する説明をした。今回は、”tail = &( (*tail)->left )“の赤のカッコが省略されたら、青のカッコが省略されたら、どちらが文法エラーかを「演算子の優先順位」の話を交えながら説明する。 (さらに…)