バイナリサーチツリーの走査

放送大学-情報コース‐

科目：データ構造とプログラミング

#6　バイナリサーチツリー

走査(そうさ)について書きます。

■走査とは

あるルールにそって、ノードにアクセスしていく事。

ノードとは下図(ツリー)の「〇」の所です。データって事かな。

各ノードに立ち寄っていく作業=走査

■走査の種類

代表的なもの3つ

●行きがけ順走査

・ルートノード(頂上のノード）を走査

↓

・左側のサブツリーを走査

↓

・右側のサブツリーを走査

●通りがけ順走査

・左側のサブツリーを走査

↓

・ルートノードを走査

↓

・右側のサブツリーを相殺

●帰りがけ順走査

・左側のサブツリーを走査

↓

・右側のサブツリーを走査

↓

・ルートノードを走査

以上です