Implementation of tree
木の実現

出席登録

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

レポート提出確認

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

講義

6.4

6.4.2 行きがけ順のなぞり

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

の両方の理解が必要である.

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

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

  1. 引数のデータが小さいときは再帰呼出しをせず,直接処理する.
  2. 再帰呼出しを行うときは自分が受け取った入力データより 小さいデータを引数として再帰呼出しを行う.
  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);
}

図8.1 sum

6.5 数式の木

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

p.99 Fig6.7 の破線にそって木の周囲を移動し, p.100 の

のタイミングでラベルを出力するとそれぞれのなぞりの 順序で節のラベルが出力される.これは 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では,

表 8.1 科目と担当者の表

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

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

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

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

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

課題

第 8 回課題「二分木の最大値」 を提出せよ.


Updated in November 29, 2022, index.html, Yamamoto Hiroshi