2分探索木の説明で、深さ優先探索、幅優先探索の話をしたので、補足説明。
幅優先探索(breadth-first search)は、待ち行列を使って実装可能なことを示すサンプルコード。待ち行列は授業で説明したFIFOでは、データ件数0になる際の処理を手抜きで説明しているため、C++ の deque で記述。
深さ優先探索(deep-first search)は、スタックを使って実装可能なことを示すために、あえて再帰呼び出しを使わずに記述してみた。
#include <deque>
#include <algorithm>
int main() {
std::deque<struct Tree*> deq ;
struct Tree* p ;
// 幅優先探索(FIFOを使って)
deq.push_front( top ) ;
while( !deq.empty() ) {
// 待ち行列の最初を取り出す
p = deq.front() ;
deq.pop_front() ;
if ( p != NULL ) {
printf( "%d\n" , p->data ) ;
// 待ち行列に枝葉を追加
deq.push_back( p->left ) ;
deq.push_back( p->right ) ;
}
}
// 深さ優先探索(再帰呼び出しを使わずstack/LIFOで実装)
p = top ;
for( ;; ) {
// 分岐をpushしながら左下にまっしぐら
while( p != NULL ) {
deq.push_front( p ) ;
p = p->left ;
}
if ( deq.empty() )
break ;
// pushしておいた分岐点をpopして繰り返し
p = deq.front() ;
deq.pop_front() ;
printf( "%d\n" , p->data ) ;
p = p->right ;
}
return 0 ;
}