データ構造とアルゴリズム第6回の2 木～データ構造（3）～ 1 木構造 (tree) 2 内容    グラフ木構造木の定義と用語       根，節点，葉親子，兄弟，先祖，子孫経路と経路の長さ深さと高さ木の走査代表的な木構造 3 グラフ(graph)     有限個の節点(node, 頂点, vertex)と，エッジ(edge, 辺, 枝) の集合で構成される V ：節点の集合 E ：辺の集合 G ：グラフ節点 v1 辺 (枝) e = (v1, v2) v2 4 無向グラフと有向グラフ無向グラフ (undirected graph) 枝に方向を考えないグラフ (v1, v2) = (v2, v1) 1  有向グラフ (directed graph, digraph) 2 枝の方向を考えるグラフ (v1, v2) ≠ (v2, v1)  v2 v v v1 v2 v1 アーク 5 完全グラフ(complete graph)  すべての節点対の間に枝をもつ無向グラフ 6 部分グラフ(subgraph)  グラフG = (V, E)に対し，V’⊆V， E’⊆Eの作る G’=(V’, E’)がグラフであるとき，G’はGの部分グラフであるという 7 経路(path)     v1から v3への経路は存在する P: v1, v2,v3 v1から v4への経路は存在しない経路P: v1, v2,v3は節点がすべて異なる⇒単純路経路P: v1, v2,v3,v1は始点と終点が等しく、その他の節点はすべて異なる⇒単純閉路 v4 v2 v1 v3 v5 v6 v7 8 ケーニヒスベルグの橋陸地が4つ橋が7本同じ橋を2度渡らずにすべての橋を通ってもとの場所に戻れるか節点が4つ辺が7本同じ辺を2度通らずにすべての辺を通ってもとの節点に戻る経路はあるか 9 連結グラフ(connected graph)   連結グラフ：任意の2つの節点間に経路が存在する無向グラフ無向木：閉路を持たない連結無向グラフ 10 木（Tree）葉 leaf 根 root 12 階層構造（hierarchical structure）  木構造は，階層的な関係を表現するのに適している A大学 C学部 B学部 D学科 E学科 F学科 G学科 H学科 Iコース 14 階層構造の例  組織図  系図  階層ディレクトリ (p.39 図2.16) etc... 15 木の再帰的定義 (p.42) (1) 単一の節点は，それ自身で一つの木 (1)’ 空集合でも木（空の木（null tree）Λ） (2) Ti : 木 n ni : 木Tiの根 n : すべてのniの親 n1 n2 新しい木ができる Tiは新しい木の部分木 nは新しい木の根 T1 T2 (3) すべての木は，(1)をもとに(2)を有限回適用して得られる nk Tk 16 親子関係親子関係：  a は b, f の親(parent)  b, f は a の子(child) c a a, b, …は各々の nodeの名前 b d f e 部分木（subtree） g h i 18 兄弟 a 同じ親を持つ節点を兄弟（sibling）という    b と f は兄弟ｃと d と e は兄弟 g と i は兄弟 c b d f e g h i 19 経路と経路の長さ  ｎ1，ｎ2，・・・，ｎk が木の中の節点の列であって，１≦ｉ＜ｋに対してｎi がｎi+1の親になっているとき，この列のことを「節点ｎ1から節点ｎk への経路 (path)」という．  このとき，経路の長さは k -1  節点自身への経路の長さは０ n1 n2 n3 20 先祖と子孫    節点ａから節点ｂへの経路があるとき，ａはｂの先祖 (ancestor)，ｂはａの子孫(descendant)であるというどの節点も自分自身の先祖であり子孫である自分自身以外の先祖や子孫を真の先祖，真の子孫という 21 例1 経路と子孫 aからhへの経路： a, f, g, h  その経路の長さ： 3  ｆの子孫： f, g, h, i c  ｆの真の子孫： g, h, i a  b d f e g i h 22 例2 先祖 a   ｃの先祖 a, b, c ｃの真の先祖 a, b b c d f e 根（ｒoot） ⇒真の先祖を持たない唯一の節点  葉（leaf） ⇒真の子孫を持たない節点 g i  h 23 深さと高さ  節点の高さ（height）ある節点から葉への最長経路長  木の高さ木の根の高さ  節点の深さ(level, depth) 根からある節点までの経路の長さ 24 例3 深さと高さ  a 節点b 高さ１，深さ１深さ（レベル）０ b  節点g 高さ１，深さ２ c  f d e g i 木の高さ３ h 25 順序木と無順序木   順序木（ordered tree）：兄弟間で順序づけを行った木無順序木(unordered tree)：子の順序を無視した木 a b 無順序木としてみれば，同じ木 c c 順序木としてみると，異なる木左： bが兄，cが弟右： cが兄，bが弟 a b 26 本日の問題 (問1)スタックSとキューQがあるとする。次の手順で操作を行うとき，スタックS及びキューQの中身はどのように変化するか、図を用いて説明せよ. また，ｘに何が代入されるか？ Push(C, S)⇒Push(A, S)⇒Enq (Pop(S), Q)⇒Enq (E，Q)⇒ Push（Deq (Q)，S）⇒Enq (D ,Q) ⇒ x ← Deq (Q) (問2)以下の3つの式を，ポーランド記法および逆ポーランド記法で表現せよ．式ポーランド記法逆ポーランド記法ポーランドの首都は？ A+B+C A*B-C A*B-C÷D+E 27