データ構造とアルゴリズム 第6回の2 木 ～ データ構造（3）～

木構造 (tree)

内容 グラフ 木構造 木の定義と用語 根，節点，葉 親子，兄弟，先祖，子孫 経路と経路の長さ 深さと高さ 木の走査 代表的な木構造

v1 v2 グラフ(graph) 節点 辺 (枝) e = (v1, v2) 有限個の節点(node, 頂点, vertex)と，エッジ(edge, 辺, 枝)の集合で構成される V ： 節点の集合 E ： 辺の集合 G ： グラフ v1 節点 辺 (枝) e = (v1, v2) v2

v2 v1 v2 v2 v1 v1 無向グラフと有向グラフ 無向グラフ (undirected graph) 枝に方向を考えないグラフ 無向グラフと有向グラフ　　 無向グラフ (undirected graph) 枝に方向を考えないグラフ (v1, v2) = (v2, v1) 有向グラフ (directed graph, digraph) 枝の方向を考えるグラフ (v1, v2) ≠ (v2, v1) v2 v1 v2 v2 v1 v1 アーク

完全グラフ(complete graph) すべての節点対の間に枝をもつ無向グラフ

部分グラフ(subgraph)　　　 グラフG = (V, E)に対し，V’⊆V， E’⊆Eの作るG’=(V’, E’)がグラフであるとき，G’はGの部分グラフであるという

v4 v2 v6 v1 v3 v7 v5 経路(path) v1から v3への経路は存在する P: v1, v2,v3 経路P: v1, v2,v3,v1は始点と終点が等しく、その他の節点はすべて異なる⇒単純閉路 v1 v2 v3 v4 v5 v6 v7

ケーニヒスベルグの橋 陸地が4つ 橋が7本 同じ橋を2度渡らずに すべての橋を通って もとの場所に戻れるか 節点が4つ 辺が7本 同じ辺を2度通らずに すべての辺を通って もとの節点に戻る経路はあるか

連結グラフ(connected graph) 連結グラフ：任意の2つの節点間に経路が存在する無向グラフ 無向木：閉路を持たない連結無向グラフ

根つき木(rooted tree)　 根とよばれる１つの節点があり、そこから他の任意の節点への経路が存在するとき、　根つき木　(rooted tree)または単に 木 (tree)と呼ぶ

木（Tree） 葉　leaf 根　root

情報科学における木 根(root) 枝(branch) 節点(node) 葉(leaf)

階層構造（hierarchical structure） 木構造は，階層的な関係を表現するのに適している A大学 B学部 C学部 D学科 E学科 F学科 G学科 H学科 Iコース

階層構造の例 (p.39 図2.16) 組織図 系図 階層ディレクトリ etc...

木の再帰的定義 (p.42) 新しい木ができる (1) 単一の節点は，それ自身で一つの木 (1)’ 空集合でも木（空の木（null tree）Λ） (2) (3) すべての木は，(1)をもとに(2)を有限回適用して得られる Ti : 木 ni : 木Tiの根 n : すべてのniの親 新しい木ができる Tiは新しい木の部分木 nは新しい木の根 n T1 n1 T2 n2 Tk nk

問題 a 右図は木といえるか？ ⇒いえない． （木の定義をもとに，各自理由を考えてみること） 右図のような構造をグラフ（graph）という 　（木の定義をもとに，各自理由を考えてみること） 右図のような構造をグラフ（graph）という b c d e f g h

親子関係 a, b, …は各々のnodeの名前 親子関係： a は b, f の親(parent) b, f は a の子(child) a 部分木 （subtree） b f c d e g i h

兄弟 a 同じ親を持つ節点を兄弟（sibling）という b と f は兄弟 ｃ と d と e は兄弟 g と i は兄弟 b f c d h

経路と経路の長さ ｎ1，ｎ2，・・・，ｎk が木の中の節点の列であって，１≦ｉ＜ｋに対してｎi がｎi+1の親になっているとき，この列のことを「節点ｎ1から節点ｎk への経路(path)」という． このとき，経路の長さは k -1 節点自身への経路の長さは０ n1 n2 n3

先祖と子孫 節点ａから節点ｂへの経路があるとき，ａはｂの先祖(ancestor)，ｂはａの子孫(descendant)であるという どの節点も自分自身の先祖であり子孫である 自分自身以外の先祖や子孫を真の先祖，真の子孫という

例1 経路と子孫 a aからhへの経路： a, f, g, h その経路の長さ： 3 ｆの子孫： f, g, h, i ｆの真の子孫： 例1　経路と子孫 a aからhへの経路： a, f, g, h その経路の長さ： 3 ｆの子孫： f, g, h, i ｆの真の子孫： g, h, i b f c d e g i h

例2 先祖 a ｃの先祖 a, b, c ｃの真の先祖 a, b 根（ｒoot） ⇒真の先祖を持たない唯一の節点 葉（leaf） 例2　先祖 a ｃの先祖 　　a, b, c ｃの真の先祖 a, b 根（ｒoot） 　⇒真の先祖を持たない唯一の節点 葉（leaf） 　⇒真の子孫を持たない節点 b f c d e g i h

深さと高さ 節点の高さ（height） ある節点から葉への最長経路長 木の高さ 木の根の高さ 節点の深さ(level, depth) 　　ある節点から葉への最長経路長 木の高さ 　　木の根の高さ 節点の深さ(level, depth) 　　根からある節点までの経路の長さ

例3　深さと高さ a 深さ（レベル）０ 節点b 　　高さ１，深さ１ 節点g 　　高さ１，深さ２ 木の高さ 　　３ b f c d e g i h

順序木と無順序木 順序木（ordered tree）：兄弟間で順序づけを行った木 無順序木(unordered tree)：子の順序を無視した木 a b c 無順序木としてみれば，同じ木 a c b 順序木としてみると，異なる木 左：　bが兄，cが弟 右：　cが兄，bが弟

本日の問題 (問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÷D+E A*B-C A+B+C 式 逆ポーランド記法 ポーランドの首都は？