データ構造と アルゴリズム 第七回 知能情報学部 新田直也
二分木 二分木： すべての節点が子をたかだか2つしか持たない順序木． (a + b) * c + (d / -e) + 子が2個 * / 子が1個 a b e 子が0個
二分木の表現(1) 例によってWebで．．．
二分木の表現(2) struct node { char value; struct node *left; struct node *right; } ラベル 1ノードに相当 (構造体) 左の子のアドレス 右の子のアドレス
二分木の巡回法 木の巡回（traverse）：各節を1回づつ全節を調べる． 深さ優先探索法と幅優先探索法に分類される． + + * / * c d - + c d - a b e a b e 深さ優先探索 幅優先探索
深さ優先探索の種類 行きがけ順，帰りがけ順，通りがけ順の3通り． 行きがけ順：根→(左部分木)→(右部分木） （一回目） 行きがけ順：根→(左部分木)→(右部分木） （一回目） 帰りがけ順：(左部分木)→(右部分木)→根 （三回目） 通りがけ順：(左部分木)→根→(右部分木） （二回目） + * / + c d - a b e
行きがけ順 行きがけ順： 根 → (左部分木) → (右部分木） →処理順は +*+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
帰りがけ順 帰りがけ順： (左部分木) → (右部分木） → 根 →処理順は 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-/+
通りがけ順 通りがけ順： (左部分木) → 根→ (右部分木） →処理順は 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-
アルゴリズムの記述 手続き的に行きがけ順を記述すると… 木の根をnとおく スタックを空にする ノードnを調べる yes nが葉か？ yes スタックが 空か？ no no nの右の子を スタックに積む スタックから ノードを取り出し nとおく nの左の子をnとおく End
再帰アルゴリズムによる記述 再帰アルゴリズムだとシンプルに記述できる． void traverse(struct node *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; } + + 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; }
順序木の表現(1)
順序木の表現(2) struct node { char value; struct node *sibling; struct node *chlid; } ラベル 1ノードに相当 (構造体) 兄弟のアドレス 子供のアドレス
順序木と二分木 順序木を二分木とみなすことができる． f f g g f h a f a b a h a b b a h b h b b a