「木構造 (データ構造)」の版間の差分
削除された内容 追加された内容
35行目:
== 走査法 ==
木構造の走査
; 前順・先行順・前置順・行きがけ順
:# 根ノードを調査する。
:# もしあれば、左の部分木を前順走査する。
:# もしあれば、右の部分木を前順走査する。
: これは、[[深さ優先探索]]とも呼ばれる。[[2分探索木]]のコピーを作る際によく利用される。また、数式の[[構文木]]から[[ポーランド記法]]の表現を得るのにも利用される。
; 間順・中間順・通りがけ順
:# もしあれば、左の部分木を間順走査する。
:# 根ノードを調査する。
:# もしあれば、右の部分木を間順走査する。
: [[2分探索木]]では、間順走査によって走査する順がソートされた順序になるため、よく使われる。
; 後順・後行順・後置順・帰りがけ順
:# もしあれば、左の部分木を後順走査する。
:# もしあれば、右の部分木を後順走査する。
|