Presentation is loading. Please wait.

Presentation is loading. Please wait.

データ構造と アルゴリズム第5回 知能情報学メジャー 和田俊和.

Similar presentations


Presentation on theme: "データ構造と アルゴリズム第5回 知能情報学メジャー 和田俊和."— Presentation transcript:

1 データ構造と アルゴリズム第5回 知能情報学メジャー 和田俊和

2 第2章 基本的なデータ構造 2.1 配列 2.2 リンク配置 2.3 連結リスト 2.4 スタック 2.5 キュー 2.6 木構造

3 2.6木構造 データ間の階層構造,親子関係,包含関係を表 現するのに適したデータ構造

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

5 2.6.1木構造に用いられる用語 根 葉 葉 葉 葉 葉 葉 葉は「終端節点」とも呼ばれる 葉を除いた節点を「非終端節点」と呼ばれる

6 木の括弧表現 括弧 図式表現 (A(B(E)(F))(C)(D(G(I)(J))(H))) 根 度数=3 節 度数=2 葉 高さ=4 1 2
度数=3 度数=2 1 2 高さ=4 3

7 2.6.1木構造に用いられる用語

8 2.6.2 2分木(順序木の一種) 全ての節点がたかだかk個の子を持つような木 を𝑘分木と呼ぶ. 特に𝑘=2の2分木は多くの用途がある.
2.6.2 2分木(順序木の一種) 全ての節点がたかだかk個の子を持つような木 を𝑘分木と呼ぶ. 特に𝑘=2の2分木は多くの用途がある. 論理構造としての木は,親子間には順序関係が あるが,兄弟間には順序は存在しない. しかし,2分木の場合は兄弟間でも順序があり, 子の節を「左の子」「右の子」,部分木を「左 部分木」「右部分木」のように区別して扱う. 子の節の順序を決めない木構造を2進木と呼ぶ.

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

10 完全2分木 最大レベルを除いたどのレベルも節点が詰まっ ており,かつ,最大レベルでも節点が左詰に なっているものを(広義の)完全2分木と呼ぶ. 狭義の完全2分木は最大レベルの節も詰まって いる.

11 完全2分木 高さℎの完全2分木の総節点数𝑛は, 𝑛= 𝑖=0 ℎ 2 𝑖 = 2 ℎ+1 −1=𝑂( 2 ℎ )
𝑛= 𝑖=0 ℎ 2 𝑖 = 2 ℎ+1 −1=𝑂( 2 ℎ ) 逆に,総節点数から高さを求めれば ℎ=𝑂( log 𝑛 ) 根から葉に至る 経路の長さに依 存するアルゴリ ズムの時間計算 量は𝑂( log 𝑛 )

12 2.6.3 2分木の実現 リンク配置による2分木の実現

13 2.6.3 2分木の実現 配列による完全2分木の実現

14 2.6.4 木の走査 深さ優先探索(縦型探索)と幅優先探索(横型探索)

15 2.6.4 木の走査 深さ優先探索(縦型探索)の場合,同じ頂点を3回通る. このうちのどのタイミングで節点データを処理する か? (先行順)
2.6.4 木の走査 深さ優先探索(縦型探索)の場合,同じ頂点を3回通る. このうちのどのタイミングで節点データを処理する か? (先行順) (後行順) (中間順)

16 2.6.4 木の走査 行きがけ順 C-A-I-K-J-D-F-H-L-B-E-G 通りがけ順 K-I-J-A-F-D-H-C-E-B-L-G
2.6.4 木の走査 行きがけ順 C-A-I-K-J-D-F-H-L-B-E-G 通りがけ順 K-I-J-A-F-D-H-C-E-B-L-G 帰りがけ順 K-J-I-F-H-D-A-E-B-G-L-C

17 木の走査は再帰(recursion)で行う

18 C プログラムの例 twada$ ./a.out Preorder: C-A-I-K-J-D-F-H-L-B-E-G-
#include<stdio.h> #include<stdlib.h> int A[]={'C','A','L','I','D','B','G','K','J','F','H','E'}; #define Num 12 #define Left(i) (2*(i)+1) #define Right(i) (2*(i)+2) void Preorder(int i) {         if (i>=Num) return;         printf("%c-",A[i]);         Preorder(Left(i));         Preorder(Right(i)); } void Inorder(int i)         Inorder(Left(i));         Inorder(Right(i)); } void Postorder(int i) {         if (i>=Num) return;         Postorder(Left(i));         Postorder(Right(i));         printf("%c-",A[i]); } int main() printf("Preorder: "); Preorder(0); printf("\n"); printf("Inorder: "); Inorder(0); printf("\n"); printf("Postorder: "); Postorder(0); printf("\n"); return 0; twada$ ./a.out Preorder: C-A-I-K-J-D-F-H-L-B-E-G- Inorder: K-I-J-A-F-D-H-C-E-B-L-G- Postorder: K-J-I-F-H-D-A-E-B-G-L-C- twada$

19 stackを用いた木の走査(追加説明) } //この方法ではpreorderの出力しかできない //リスト2.12と比較してみて下さい.
stack-depth-first-search(){ push(STACK,root); while(STACKが空でない){ node=pop(STACK);    if (nodeが指す節点の左の子が存在する) push(STACK,nodeが指す節点の左の子へのポインタ); if(nodeが指す節点の右の子が存在する) push(STACK,nodeが指す節点の右の子へのポインタ); } //この方法ではpreorderの出力しかできない

20 C プログラムの例 twada$ ./a.out DepthFirst: C-A-I-K-J-D-F-H-L-B-E-G-
#include<stdio.h> #include<stdlib.h> int A[]={'C','A','L','I','D','B','G','K','J','F','H','E'}; #define Num 12 #define Left(i) (2*(i)+1) #define Right(i) (2*(i)+2) #define Siz 10 int Stack[Siz]; int top=0; void push(int c) {略 } int pop() void DepthFirst(int i) {   int c;   push(i);     while(top>0){           c=pop();           printf("%c-",A[c]);           if (Right(c)<Num) push(Right(c));           if (Left(c)<Num) push(Left(c));     } } int main() {   printf(”DepthFirst: "); DepthFirst(0); printf("\n");         return 0; twada$ ./a.out DepthFirst: C-A-I-K-J-D-F-H-L-B-E-G- twada$

21 2.6.4 木の走査 幅優先探索(横型探索)の場合,各節点は1回しか通 らない. 右の木のラベル出力例
2.6.4 木の走査 幅優先探索(横型探索)の場合,各節点は1回しか通 らない. 右の木のラベル出力例 C-A-L-I-D-B-G-K-J-F-H-E

22 2.6.4 木の走査 幅優先探索(横型探索)の場合,各頂点は1回しか通 らない.

23 twada$ ./a.out C プログラムの例 twada$ void BreadthFirst(int i) { int c;
#include<stdio.h> #include<stdlib.h> int A[]={'C','A','L','I','D','B','G','K','J','F','H','E'}; #define Num 12 #define Left(i) (2*(i)+1) #define Right(i) (2*(i)+2) #define Siz 20 int RingBuf[Siz]; int front=0; int rear=0; void enqueue(int c) {略 } int dequeue() void BreadthFirst(int i) {    int c;      enqueue(i);      while(front!=rear){          c=dequeue();          printf("%c-",A[c]);       if (Left(c)<Num) enqueue(Left(c));   if (Right(c)<Num) enqueue(Right(c));      } } int main() {   printf(”BreadthFirst: "); BreadthFirst(0); printf("\n");         return 0; twada$ ./a.out BreadthFirst: C-A-L-I-D-B-G-K-J-F-H-E- twada$

24 2.6.5 一般の木の実現 子を繋ぐ連結リストを用いる方法

25 2.6.5 一般の木の実現 等価な2分木に変換する方法

26 演習問題 設問1 2.(3)  (4)     (5)   (6) 設問6 行きがけ順 通りがけ順 帰りがけ順


Download ppt "データ構造と アルゴリズム第5回 知能情報学メジャー 和田俊和."

Similar presentations


Ads by Google