二分木は非線形データ構造です。各ノードには最大 2つの子があるので、二分木と呼ばれています。これらの子は左の子と右の子と呼ばれています。また、最上位のノードをルートと呼ぶ無向グラフと解釈することもできます。一方向にしか移動できない線形データ構造とは異なり、木はさまざまな方法で移動することができます。深さや幅に沿って探索することで木を探索することができます。最初の方法は深さ優先走査と呼ばれ、2 番目の方法は幅優先走査と呼ばれます。この記事では、深さ優先探索について説明します。 デプスファースト走査には、インオーダー、プレオーダー、ポストオーダーの 3 種類があります。それぞれについて一つずつ解説していきます。 二分木走査 インオーダー走査 この探索では、まず左サブツリー、次にルート、そして最後に右サブツリーを訪れます。すべてのノードはサブツリーに似ています。BST では、順序を変えて探索すると、すべての要素が昇順で返されます。