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

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

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

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

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

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

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

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

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

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

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

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

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

2.6.4　木の走査 深さ優先探索（縦型探索）と幅優先探索（横型探索）

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

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

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

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$

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の出力しかできない

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$

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

2.6.4　木の走査 幅優先探索（横型探索）の場合，各頂点は１回しか通 らない．

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$

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

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

演習問題 設問１ ２．(3)　 (4) 　　　　(5)　　 (6) 設問6 行きがけ順 通りがけ順 帰りがけ順