アルゴリズム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の実行例
授業で配布するプリントを参照して下さい。


アルゴリズム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
授業で配布するプリントを参照して下さい。
RunCalcTree.javaの実行例
$BH$7$F2<$5$$!#(B
RunCalcTree02.txt
授業で配布するプリントを参照して下さい。

課題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の実行例
授業で配布するプリントを参照して下さい。

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

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

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

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