行きがけ順、通りがけ順、帰りがけ順探索
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/05/29 13:54 UTC 版)
「二分木」の記事における「行きがけ順、通りがけ順、帰りがけ順探索」の解説
二分木においてはあるノードとその子孫もまた二分木を構成する。これを部分木と呼ぶ。従って二分木を部分木に分け、再帰を用いて探索する方法は自然である。根を調べてからそれにぶらさがる部分木を調べるのが行きがけ順 (preorder)、部分木を調べてからその根を調べるのが帰りがけ順 (postorder) 、片方の部分木を調べ、根を調べ、次いで反対の部分木を調べるのが通りがけ順 (in-order) である。二分探索木では通りがけ順探索はノードを大きさ順(あるいは大きさの逆順)に調べることになる。
※この「行きがけ順、通りがけ順、帰りがけ順探索」の解説は、「二分木」の解説の一部です。
「行きがけ順、通りがけ順、帰りがけ順探索」を含む「二分木」の記事については、「二分木」の概要を参照ください。
- 行きがけ順、通りがけ順、帰りがけ順探索のページへのリンク