アルゴリズムA 第9回


木構造

特徴

定義

  1. 1つの節は、それ自体が木である。この木に含まれるただ1つの 節がこの木の根である。
  2. k個の木 T1Tk があり、それぞれの根を n1nk とする。 節nを節 n1nk の 親にすると、節nを根とする新しい木Tが得られる。 このとき、木 T1Tk は、木Tの部分木 (subtree)であるという。 部分木の根 n1nk は、 節nの子であるという

順序木と無順序木

教科書では特に断らない限り、「木」といえば「順序木」を表すことにする、そうだ。

二分木 (binary tree)

  1. 空の木は二分木である
  2. 次のいずれかの条件を満たす節のみからなる木は、二分木である。

すなわち、「たかだか2個の子しか持たない節から構成されている木」が「二分木」。

(a) a      (b) a
   / \        / \
  b   c      c   b
(a)と(b)は異なる木であることに注意すること。 (順序木なので「左右がひっくり返った節」は別の節とみなすから。)

BinaryTreeNode.java
授業で配布するプリントを参照して下さい。

木のなぞり

TraverseBinaryTree.java
授業で配布するプリントを参照して下さい。
TraverseBinaryTree.javaの実行例
sp204: ~/pro 4> javac TraverseBinaryTree.java 
sp204: ~/pro 5> java TraverseBinaryTree 
[a, [b, [c, null, null], null], [d, null, null]]
行きがけ順
節aに立ち寄りました
節bに立ち寄りました
節cに立ち寄りました
節dに立ち寄りました
通りがけ順
節cに立ち寄りました
節bに立ち寄りました
節aに立ち寄りました
節dに立ち寄りました
帰りがけ順
節cに立ち寄りました
節bに立ち寄りました
節dに立ち寄りました
節aに立ち寄りました
sp204: ~/pro 6> 


アルゴリズムa 演習


課題提出〆切は次回の講義の開始時刻です。

課題9a

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai9a
提出ファイルgif形式またはpng形式の図
コメント欄: ShowBinaryTree.javaの出力

以下のプログラムを実行したとき、treeにはどのような木構造が保持されるのか、gif形式またはpng形式の図で表しなさい。 また、以下のプログラムを実行したときの表示結果を答えなさい。

ShowBinaryTree.java
授業で配布するプリントを参照して下さい。

課題9b

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai9b
提出ファイルRunCalcTree.java
コメント欄: RunCalcTree02.txtを入力として与えたときのRunCalcTree.javaの出力

逆ポーランド記法で記述された数式を、infix notationで表示するプログラムを書いた。 欠けている部分のコードを自分で考えて書きなさい。

CalcNode.java
授業で配布するプリントを参照して下さい。
RunCalcTree.java
授業で配布するプリントを参照して下さい。
RunCalcTree01.txt
3 2 + 3 8 - *
a 1 + b 2 * c d / e f * / + -
dy sy - dx sx - / x sx - * sy +
RunCalcTree.javaの実行例
% javac RunCalcTree.java
% java RunCalcTree < RunCalcTree01.txt
( ( 3 + 2 ) * ( 3 - 8 ) )
( ( a + 1 ) - ( ( b * 2 ) + ( ( c / d ) / ( e * f ) ) ) )
( ( ( ( dy - sy ) / ( dx - sx ) ) * ( x - sx ) ) + sy )
RunCalcTree02.txt
4 3 / 12 8 / * 1 3 / 1 5 / - /
1 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 + 10 /
100 0.1 * 80 0.2 * 60 0.4 * 40 0.3 * + + +
100 0.1 * 80 0.2 * + 60 0.4 * + 40 0.3 * +
3 2 + 3 8 - *
a 1 + b 2 * c d / e f * / + -
dy sy - dx sx - / x sx - * sy +

課題9c

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai9c
提出ファイルTreeKnowledge.java
コメント欄:10項目以上登録するように動作させた結果

2分木で知識を表現するプログラム TreeKnowledge.java を作成しなさい。 2分木のLeafノードに物の名前を入れ、非終端ノードに質問を記憶するものとにする。


  1. 「コンピュータ」という単語を登録する。
  2. ユーザに物の名前を思い浮かべてもらう。
  3. x = rootノードとする
  4. xに対して
TreeKnowledge.java
授業で配布するプリントを参照して下さい。
TreeKnowledge.javaの実行例
$ java TreeKnowledge
何かについて思いうかべて下さい。
それは コンピュータ ですね (y/n)? n
正解を教えて下さい
林檎
林檎 ならばYESで コンピュータ についてNOとなる質問を入力して下さい。
それは赤いですか
続けますか (y/n)? y
何かについて思いうかべて下さい。
それは赤いですか (y/n)? n
それは コンピュータ ですね (y/n)? n
正解を教えて下さい
蜜柑
蜜柑 ならばYESで コンピュータ についてNOとなる質問を入力して下さい。
それは黄色いですか
続けますか (y/n)? y
何かについて思いうかべて下さい。
それは赤いですか (y/n)? n
それは黄色いですか (y/n)? n
それは コンピュータ ですね (y/n)? n
正解を教えて下さい
飛行機
飛行機 ならばYESで コンピュータ についてNOとなる質問を入力して下さい。
空を飛びますか
続けますか (y/n)? y
何かについて思いうかべて下さい。
それは赤いですか (y/n)? y
それは 林檎 ですね (y/n)? n
正解を教えて下さい

苺 ならばYESで 林檎 についてNOとなる質問を入力して下さい。
種が表面にありますか
続けますか (y/n)? y
何かについて思いうかべて下さい。
それは赤いですか (y/n)? n
それは黄色いですか (y/n)? y
それは 蜜柑 ですね (y/n)? y
続けますか (y/n)? n

課題9d (オプション課題)

提出先 http://nw.tsuda.ac.jp/class/algoA/local/handin/list.php?id=kadai9d
提出ファイルTreeKnowledgeSerializable.java
コメント欄:起動した直後に過去の知識をロードしたことを示す動作例

これはオプション課題です。できた人だけが提出しなさい。

TreeKnowledge.java と BinaryTreeNode.java に変更を加えて、 得た知識を保存して次回の起動時に読み込むプログラム TreeKnowledgeSerializable.java を作成しなさい。