データ構造と アルゴリズム 第七回 知能情報学部 新田直也.

Presentation on theme: "データ構造と アルゴリズム 第七回 知能情報学部 新田直也."— Presentation transcript:

1 データ構造と アルゴリズム 第七回 知能情報学部 新田直也

2 二分木 二分木： すべての節点が子をたかだか2つしか持たない順序木． (a + b) * c + (d / -e) + 子が2個 * /
子が1個 a b e 子が0個

3 二分木の表現(1) 例によってWebで．．．

4 二分木の表現(2) struct node { char value; struct node *left;
struct node *right; } ラベル 1ノードに相当 (構造体) 左の子のアドレス 右の子のアドレス

5 二分木の巡回法 木の巡回（traverse）：各節を1回づつ全節を調べる． 深さ優先探索法と幅優先探索法に分類される． + + * / *
c d - + c d - a b e a b e 深さ優先探索 幅優先探索

6 深さ優先探索の種類 行きがけ順，帰りがけ順，通りがけ順の3通り． 行きがけ順：根→(左部分木)→(右部分木） （一回目）
行きがけ順：根→(左部分木)→(右部分木）　（一回目） 帰りがけ順：(左部分木)→(右部分木)→根　（三回目） 通りがけ順：(左部分木)→根→(右部分木）　（二回目） + * / + c d - a b e

7 行きがけ順 行きがけ順： 根 → (左部分木) → (右部分木） →処理順は +*+abc/d-e + / * + c d - a b e
(1) + (2) (2) (3) (2-1) / * (2-2) (2-2) (2-2-1) + (2-3) c d - (2-2-2) (2-2-3) a b e →処理順は +*+abc/d-e

8 帰りがけ順 帰りがけ順： (左部分木) → (右部分木） → 根 →処理順は ab+c*de-/+ + / * + c d - a b e
(3) + (1) (1) (2) (1-3) / * (1-1) (1-1) (1-1-3) + (1-2) c d - (1-1-1) (1-1-2) a b e →処理順は ab+c*de-/+

9 通りがけ順 通りがけ順： (左部分木) → 根→ (右部分木） →処理順は a+b*c+d/e- + / * + c d - a b e
(2) + (1) (1) (3) (1-2) / * (1-1) (1-1) (1-1-2) + (1-3) c d - (1-1-1) (1-1-3) a b e →処理順は a+b*c+d/e-

10 アルゴリズムの記述 手続き的に行きがけ順を記述すると… 木の根をnとおく スタックを空にする ノードnを調べる yes nが葉か？ yes
スタックが 空か？ no no nの右の子を スタックに積む スタックから ノードを取り出し nとおく nの左の子をnとおく End

11 再帰アルゴリズムによる記述 再帰アルゴリズムだとシンプルに記述できる． void traverse(struct node *n) {
if (n->left != NULL) traverse(n->left); if (n->right != NULL) traverse(n->right); return; }

12 再帰アルゴリズムの動作 + + / * * + + c c d - a a b b e
void traverse(struct node *n) { [n に対して処理] if (n->left != NULL) traverse(n->left); if (n->right != NULL) traverse(n->right); return; } + + void traverse(struct node *n) { [n に対して処理] if (n->left != NULL) traverse(n->left); if (n->right != NULL) traverse(n->right); return; } / * * void traverse(struct node *n) { [n に対して処理] if (n->left != NULL) traverse(n->left); if (n->right != NULL) traverse(n->right); return; } + + c c d - a a b b e void traverse(struct node *n) { [n に対して処理] if (n->left != NULL) traverse(n->left); if (n->right != NULL) traverse(n->right); return; }

13 順序木の表現(1)

14 順序木の表現(2) struct node { char value; struct node *sibling;
struct node *chlid; } ラベル 1ノードに相当 (構造体) 兄弟のアドレス 子供のアドレス

15 順序木と二分木 順序木を二分木とみなすことができる． f f g g f h a f a b a h a b b a h b h b b a