今回の 1 限目別教室にて中間試験を行いますので教室に注意して下さい． （教室は目次ページに戻って確認してください）
2 コマ目は通常の教室で受講して下さい．
第8回は 4 限の時間内に出席登録を行え． この場合もOpen LMS の 3 限のコマに登録する．
この授業のトップページから レポートのページに移動し， レポートの提出状況を常に確認せよ．
木構造とは，図書館の本の分類方式 のように大分類から小分類へと階層的にデータを分類するときに使われる．
大量のデータを高速に検索する場合に極めて有効で， ほとんどのオペレーティングシステムのファイル管理に使われている．
節とそれを結ぶ辺で表現されたものを一般にグラフといい， 木はグラフの中の特殊なものである． 木の厳密な定義は p.90 の最後のものである． 再帰的な定義なので直感的には理解しにくいが， 木構造の重要な性質は，根以外の節について， 親は一意に決まるが子は複数持てる，ということである．
この性質から， 例えば全ての節に子を 2 個ずつ与えていくと，木の高さが $h$ のときの 要素数は $2^{h + 1} - 1$ となる．これを逆に要素数を 中心に考えると要素数が $n$ のときの木の高さはおおよそ $\log n$ に比例することが わかる． 木を利用したアルゴリズムの多くは根から葉まで木をたどることで処理を行うので 要素数 $n$ のデータを $\log n$ で処理する高速なアルゴリズムを作成することができるため， 木構造は大量のデータを保存，検索する場合によく用いられる．
6.1 節に書かれている各種用語の定義を理解せよ．
兄弟に順序をつけて区別する木を順序木という．データ構造に 木が使われる場合，ほとんど順序木が使われる．
二分木の厳密な定義は p.92 にある通り， 直感的には子の数が 2 以下に制限された順序木と理解すればよい． 最大 2 個の子の順序を区別すれば良いので，左の子，右の子と 呼んで区別する．p.93 Fig.6.5 (a) と (b) は異なる木であることに注意せよ．
二分木に限らず，部分木という概念がアルゴリズムを設計する 場合においても極めて重要である．
二分木の場合は子が左か右だけなので それぞれを根としてみた部分木をそれぞれ左部分木，右部分木という． 二分木を利用したアルゴリズムでは「〜の作業を左部分木，右部分木 に対して行う」というように，部分木単位で設計することが多い．
二分木はどの節点も子として右の子か左の子しかもたないので， それぞれのためのポインタを用意すればデータ構造を実現できる． p.92 から p.93 にかけて書かれている struct node の定義は 二分木を実装するデータ構造で，木構造の中で最も基本的なものである． left メンバ，right メンバには対応する節のデータへのポインタ （アドレス）が格納される．対応する子がない場合，NULL が格納される．
p.94 Fig.6.6 の (a) が二分木の例を図で表したもので，(b) がそれを前述の データ構造で実装したものである．
リストは先頭からたどる場合，いつでも「次の要素」は一意に決まるので （抽象データ型としての線形リストの定義から）全ての要素をたどるのは簡単である． 木の場合は，根からアクセスを始めたと考えると，子が複数あるために間違いなく すべての要素を残さず一度だけアクセスする方法は自明ではない．
木の再帰的な構造とプログラム言語のもつ再帰的関数の記述力を使った 代表的な木のなぞり方として，行きがけ順（preorder），通りがけ順（inorder） 帰りがけ順（postorder）がある．再帰的な定義が p.95 に示されている． C 言語など多くの言語では再帰的な関数の定義 （関数定義内で自分自身の関数名を呼び出す）が可能なので この定義の通りにコーディングできる．
第 7 回課題「二分木のなぞり」 を提出せよ．