implementation of tree

出席の確認はOpenLMS の 3 限のコマを用いて行う． 3限の授業時間中に出席登録を完了せよ．

レポート提出確認

この授業のトップページからレポートのページに移動し，レポートの提出状況を常に確認せよ．

講義

6.4

6.4.2 行きがけ順のなぞり

p.96 List6.1 の関数 preorder, inorder, postorder は典型的な再帰関数である．動作を理解するには

部分木についてはすでに説明したので，再帰関数について説明する．

関数内で自分と同じ関数を呼び出すことを再帰呼出しという．再帰関数を理解するには関数定義から以下の3つのポイントを確認することが重要である．

特に上記3.のポイントは，今自分が作っている最中のプログラムをあたかも既に完成しているように考えて使うので直感に反するところが初学者がつまずき易い点である．また，自分で再帰関数をプログラミングするときはどんな入力に対しても再帰呼出しを繰り返して最終的には 1. で用意した直接処理ルーチンにたどりつくことを確認しなければならない．

上記チェックポイントに沿って p.96 List6.1 の preorder をホワイトボードを使って説明する．

6.4.3, 6.4.4

練習8.1

p.96 List6.1 の inorder のソースを読み，授業で行った preorder の説明と同様の考察を自分で行い．出力結果を予想せよ．

前回課題「二分木のなぞり」のプログラムで自分の考察が正しかったかを確認せよ． postorder についても同様の考察を行え．

練習8.2

木の節のラベルを整数値をとるように変更し，引数が指す節を根とする木のラベルの合計を返す関数 sum をp.96 List6.1 の postorder を参考に作成したものが以下のプログラムである．動作を確認し，動作原理を理解せよ．

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


/* 節の定義 */
struct node {
    struct node *left;      /* 左の子 */
    struct node *right;     /* 右の子 */
    int  value;         /* この節の値 */
};

/*  二分木を帰りがけ順でなぞる */
void postorder(struct node *p)
{
    if (p == NULL)     /* 木が空なら何もしない */
        return;
    postorder(p->left);
    postorder(p->right);
    printf("%d\n", p->value);
}

/*  二分木の合計を帰りがけ順で求める */
int sum(struct node *p)
{
    int sumofleft, sumofright, sumofp;
    if (p == NULL)     /* 木が空なら合計0を返す */
        return 0;
    sumofleft = sum(p->left);
    sumofright = sum(p->right);
    sumofp = sumofleft + sumofright + p->value;
    return sumofp;
}

int main(void)
{
    struct node *rootp, *ap, *bp, *cp, *dp;
    int s;

    if ((ap = malloc(sizeof(struct node))) == NULL) /* 節 a 作成 */
        exit(1);
    if ((bp = malloc(sizeof(struct node))) == NULL) /* 節 b 作成 */
        exit(1);
    if ((cp = malloc(sizeof(struct node))) == NULL) /* 節 c 作成 */
        exit(1);
    if ((dp = malloc(sizeof(struct node))) == NULL) /* 節 d 作成 */
        exit(1);
    ap->value = 1;                            /* 節 a の値を設定 */
    bp->value = 2;                            /* 節 b の値を設定 */
    cp->value = 3;                            /* 節 c の値を設定 */
    dp->value = 4;                            /* 節 d の値を設定 */
    ap->left = bp;                      /* a の左の子に b を登録 */
    ap->right = dp;                     /* a の右の子に d を登録 */
    bp->left = cp;                      /* b の左の子に c を登録 */
    bp->right = NULL;                   /* b の右は NULL         */
    cp->left = NULL;                    /* c の左は NULL         */
    cp->right = NULL;                   /* c の右は NULL         */
    dp->left = NULL;                    /* d の左は NULL         */
    dp->right = NULL;                   /* d の右は NULL         */
    rootp = ap;        /* 根を指すためのポインタ rootp に a を登録 */

    printf("postorder\n");
    postorder(rootp);
    s = sum(rootp);
    printf("sum:%d\n", s);
}

6.5 数式の木

＋や× などの二項演算子（演算の対象が2個の演算）を使った式の構造は二分木で表すことができる． p.99 Fig6.7 が式 (a+b)×(c-d) を表す二分木である．

のタイミングでラベルを出力するとそれぞれのなぞりの順序で節のラベルが出力される．これは 6.4 節で述べた再帰的ななぞりのアルゴリズムを再帰を用いずに記述したものに相当する．

式の木に対して行きがけ順で節を表示すると前置記法，帰りがけ順で表示すると後置記法が得られる．いずれも括弧を使わずに計算順序が一意に定義できる（式の木が一意に決まる）ことが特徴である．後置記法は逆ポーランド記法とも呼ばれ， 4.4.2節で述べたようにスタックで簡単に実現できる．

6.6 木の実現

ここでは節が持つ子の数が制限されない一般的な木の実現方法を説明する．

二分木では子の数が高々2なので left, right という 2個のポインタを格納するメンバを作っておけば十分であったが，一般の木では何個格納する必要があるかが事前にわからない．子へのポインタを連結リストを用いて表現することでこの問題を解決できる．これが p.102 Fig6.8 の実装（木の表現その1）である．

木の表現その1

とし，子へのポインタのリストは連結リストで実現する．子をもたない接点の child メンバには NULL を格納する．

この実現では節のデータ構造と，子のポインタのリストのためのデータ構造を別々に構築する必要がある．節のデータ構造同士は直接繋がっていないことに注意せよ．

木の表現その2

p.103 Fig6.8（前のページの図と図番号が同じなのでおそらくFig6.9 の間違い）は一般の木の別の実現方法である．p.102 の木と同じ木を表現していることに注意せよ．p.103 の図(e)の二分木を表現しているのではない．データ構造のもつメンバがの数がたまたま二分木と同じになっている．

各節に自分の次の兄弟へのポインタを格納するメンバを増設し，兄弟を兄から順に直接たどれるようにする，という発想で作られているのが（その2）である．この方法では用意する構造体は 1種類で済む．子からは直接兄弟を横にたどれるので，親に格納するのは長男へのポインタだけでよい．長男以外の子へのアクセスするは一旦長男にアクセスし，長男から順に sibling メンバのポインタをたどることで行う．

つまり，同じ親の子供同士をあらかじめ長男から順に連結リストでたどれるようにしておき，親には長男へのポインタだけを持たせる方法である．

説明した木の実現方法では節の親や兄を知る方法がないという欠点がある．双方向リストで行ったようにポインタを増設して解決することもできるが，木を利用したアルゴリズムは根から葉まで一方通行でたどって処理を完結させることが多いので親や兄へ戻る能力は必要ないことがほとんどである．

7 探索とは？

7.1 探索という操作

表はレコードの集まりであり，レコードはフィールドの集まり．フィールドのうち，検索に用いることができるものをキーと言う．例えば以下の表8.1では，

（データ構造とアルゴリズム，山本）というまとまりがレコードで，その中の「データ構造とアルゴリズム」や「山本」がそれぞれフィールドである．ここで科目名が「データ構造とアルゴリズム」であるレコードを検索する，ということは科目名をキーとすることを意味する．

科目名	担当者
プログラミング	森田
情報通信学基礎	福原
データサイエンスと数理	大竹
AI プログラミング	藤野
データ構造とアルゴリズム	山本

挿入，探索，削除が定義された抽象データ型を辞書という．

7.2 線形探索法と二分探索法

線形探索法と二分探索法の計算量の比較が p.107 Table7.1 である．二分探索法は線形探索法と比較して挿入が遅く，探索が速いことがわかる．

Implementation of tree 木の実現

出席登録