「木構造 (データ構造)」の版間の差分

削除された内容 追加された内容
35行目:
 
== 走査法 ==
木構造の走査 (traversal) <ref>{{lang-en-short|traverse}}</ref>とは、木構造にある全ノードを一回ずつ体系的に調査する処理である。以下のアルゴリズムは[[二分木]]に関するものだが、他の木構造にも応用可能である。[[連結リスト]]や1次元の[[配列]]のような線形性のあるデータ構造では、走査は順番に行われるだけで、論理的には一種類しかない。しかし、木構造の走査にはいくつかの方法がある。一般に、現在のノードを調査し、その子ノードに対して同じことを繰り返す。従って、[[再帰呼び出し]]で容易に表現できる([[ループ (プログラミング)|ループ]]でも実装可能)。走査法は、ノードを調査する順序によって以下の3つに分類される(いずれの方法も、根から探索を開始する)。
 
; 前順・先行順・前置順・行きがけ順 (<ref>{{lang-en-short|preorder)}}</ref>
:# 根ノードを調査する。
:# もしあれば、左の部分木を前順走査する。
:# もしあれば、右の部分木を前順走査する。
: これは、[[深さ優先探索]]とも呼ばれる。[[2分探索木]]のコピーを作る際によく利用される。また、数式の[[構文木]]から[[ポーランド記法]]の表現を得るのにも利用される。
; 間順・中間順・通りがけ順 (<ref>{{lang-en-short|inorder)}}</ref>
:# もしあれば、左の部分木を間順走査する。
:# 根ノードを調査する。
:# もしあれば、右の部分木を間順走査する。
: [[2分探索木]]では、間順走査によって走査する順がソートされた順序になるため、よく使われる。
; 後順・後行順・後置順・帰りがけ順 (<ref>{{lang-en-short|postorder) }}</ref>
:# もしあれば、左の部分木を後順走査する。
:# もしあれば、右の部分木を後順走査する。