アルゴリズムa 第9回

木構造

特徴

• 節 ... 節点、ノード (node)、頂点(vertex) などと言うこともある
• 枝 (branch) ... 辺 (edge) ということもある。
• 一番上のノードが 根 (root)
• ノードはたかだか１つの親ノード (parent node) しか持てない。
• グラフ(graph) との違いに注意すること。
グラフ理論 (graph theory)で扱うグラフとは、いくつかの「ノード」と それらを結ぶ「辺」からできたもののことで、「親ノードがたかだか１個」 などという制約はない。
• 子を持たないノード ... 葉 (leaf)、終端節 (terminal node), 外部節 (external node)
• 子を持つノード ... 非終端ノード (non-terminal node), 枝節 (branch node), 内部節 (internal node)
• レベル (level) ... 木を(根を上にみて)ルートから下へとたどった時の距離
• 部分木 (subtree) ... あるノードの子を根とする木
• 先祖(ancestor) ... 木を(根を上にみて)上へとたどったノード
• 子孫(descendant) ... 木を(根を上にみて)下へとたどったノード
• 兄弟 (sibling) ... 同じ親ノードを持つノード
• 空の木 (null tree) ... ノードを全く持たない木

定義

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

順序木と無順序木

• 同じ親を持つノードに順序を付ける →順序木 (ordered tree)
• 順序をつけない → 無順序木 (unordered tree)、有向木 (oriented tree)

二分木 (binary tree)

1. 空の木は二分木である
2. 次のいずれかの条件を満たすノードのみからなる木は、二分木である。
   • 子を持たない
   • 左の子のみを持つ
   • 右の子のみを持つ
   • 左右２個の子を持つ

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

    a   
   / \  
  b   c 

    a
   / \
  c   b

「木1」と「木2」は異なる木であることに注意すること。 (順序木なので「左右がひっくり返ったノード」は別のノードとみなすから。)

BinaryTreeNode.java

木のなぞり

• 行きがけ順 ... ノード→左部分木→右部分木
• 通りがけ順 ... 左部分木→ノード→右部分木
• 帰りがけ順 ... 左部分木→右部分木→ノード

TraverseBinaryTree.java

$ javac TraverseBinaryTree.java 
$ java TraverseBinaryTree 
[a, [b, [c, null, null], null], [d, null, null]]
行きがけ順
節aに立ち寄りました
節bに立ち寄りました
節cに立ち寄りました
節dに立ち寄りました
通りがけ順
節cに立ち寄りました
節bに立ち寄りました
節aに立ち寄りました
節dに立ち寄りました
帰りがけ順
節cに立ち寄りました
節bに立ち寄りました
節dに立ち寄りました
節aに立ち寄りました
$ 

アルゴリズムa 演習

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

課題9a

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

ShowBinaryTree.java

課題9b

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

CalcNode.java

RunCalcTree.java

3 2 + 3 8 - *
a 1 + b 2 * c d / e f * / + -
dy sy - dx sx - / x sx - * sy +

$ 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 )

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

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

1. 「コンピュータ」という単語を登録する。
2. ユーザに物の名前を思い浮かべてもらう。
3. x = rootノードとする
4. xに対して
• もしノードxがLeafノードならば、x.labelを答として表示し
• ユーザからの答が"y"ならば手順2へ
• ユーザからの答が"n"ならば、「正解」と「正解と x.label を分離する質問」を入力してもらい、木を変更してから手順2へ
• もしノードが非終端ノードならば、ノードのデータを質問としてユーザに表示し、
• ユーザからの答が"y"ならば x = x.left として手順4へ
• ユーザからの答が"n"ならば x = x.right として手順4へ

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 (オプション課題)

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

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

• 起動時に "knowledge.saved" というファイルから木を読み込む
• 木に変更があった場合には木の内容を "knowledge.saved" というファイルに保存する