深さ優先探索と幅優先探索
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 ; }