Download presentation
Presentation is loading. Please wait.
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 行きがけ順 通りがけ順 帰りがけ順
Similar presentations
© 2024 slidesplayer.net Inc.
All rights reserved.