データ構造とプログラミング技 法 （第３回） ー木構造ー. 木構造 （１） 根（ root ）と呼ばれる節 R が、 1 つだけ含まれ る。 R … TmTm T1T1 木構造： 1 個以上の節の有限集合 T であり、 次の二つの条件を満足するもの （２） 根以外の節は、 m （≧ 0 ）個の互いに素な部.

Presentation on theme: "データ構造とプログラミング技 法 （第３回） ー木構造ー. 木構造 （１） 根（ root ）と呼ばれる節 R が、 1 つだけ含まれ る。 R … TmTm T1T1 木構造： 1 個以上の節の有限集合 T であり、 次の二つの条件を満足するもの （２） 根以外の節は、 m （≧ 0 ）個の互いに素な部."— Presentation transcript:

1 データ構造とプログラミング技 法 （第３回） ー木構造ー

2 木構造 （１） 根（ root ）と呼ばれる節 R が、 1 つだけ含まれ る。 R … TmTm T1T1 木構造： 1 個以上の節の有限集合 T であり、 次の二つの条件を満足するもの （２） 根以外の節は、 m （≧ 0 ）個の互いに素な部 分集合 T 1, …,T m に分割され、各 T i （ 1 ≦ i ≦ m ）は 再び木になっている。 R … TmTm T1T1

3 木構造 R1R1 … T 1,n T 1,1 … TmTm T1T1 R RmRm … T m,k T m,1 部分木

4 木構造によって表現できる関係の例 包含関係 n 項関係 部分‐全体関係 その他 マザーボード コンピュータ キーボード CPU ディスプレー A B C DE D A B E C 本体 メモリ入出力ボード１ a*(b+c) c * + b a

5 木の表現 括弧 （ A （ B （ E ）（ F ））（ C ）（ D （ G （ I ） （ J ））（ H ））） 図式表現 度数＝ 3 度数＝ 2 高さ＝４ 根 節 節 節葉葉 葉 葉葉 葉

6 同レベルの部分木の順序： 順序木、有向木 順序木：兄弟間に順序が存在する。 例： D>C>B ， H>G ， E>F ， I>J

7 森：木の順序集合

8 二分木 (binary tree) R1R1 T 1,2 T 1,1 T1T1 R T2T2 R2R2 T 2,2 T 2,1 左部分木右部分木 ＊空集合： φ も二分木

9 問題 4.6 有向木と見なせば、 同じ。順序木と見な せば異なる。 これらは、二進木と見なせば、 同じである。 φ φ これらは、二分木

10 完全二分木 ２ 3 －１＝ ４ ２ 4 －１＝ 8 2 2-1 = 2 1-1 = 2 3-1 = 2 4-1 =

11 完全二分木：節に対する番号付け m 2m2m+1 m m/2 ∟ ∟ 子の番号 親の番号

12 二分木の表現 リンク配置： 順配置（完全二分木）： X[1] X[2] X[3] X[4] X[5] X[6] X[7] X[8] X[9]

13 二分木の走査 縦型探索 – 先順 ( 前順,preorder) – 中順 (inorder) – 後順 (postorder) 走査：探索によって、節のデータを処理する（訪問する）こと。

14 二分木の走査

15 ポーランド記法 先順：＊ a+bc 前置 記法 中順： a ＊ b+c 中置 記法 後順： abc+ ＊ 後置 記法 （（逆）ポーランド 記法）

16 ポーランド記法の計算は スタックを用いれば簡単 ＊ a ＋ bc a ＋ b c bc ＋ ＊ a ＊ (bc) ＋

17 N 分木・森の二分木への変換

18 木のリンク配置による表現

19 ゲーム木

20 演習問題 2-(3-1-1)-1 という数式の構文木を求め， ポーランド記法を求め，スタックを用 いて計算して結果が 0 になることを確認 してください．