Binary trees
Introduction
二分木は、各ノードが最大 2 つの子 (左の子と右の子) を持つデータ構造のタイプです。二分木は、二分探索木と二分ヒープの実装に使用され、効率的な検索とソートに使用されます。二分木は、k が 2 である K 分木の特殊なケースです。二分木の一般的な操作には、挿入、削除、トラバーサルがあります。これらの操作を実行する難易度は、木がバランスが取れているかどうか、またノードがリーフ ノードであるかブランチ ノードであるかによって異なります。バランスの取れた木 では、各ノードの左と右のサブツリーの深さの差は 1 以下です。これにより、深さ (高さ** とも呼ばれる) を予測できるようになります。これは、ルートからリーフまでのノードの測定値で、ルートが 0、後続のノードが (1,2..n) です。これは、log2(n) の整数部分で表すことができます。ここで、n は木内のノードの数です。
g s 9
/ \ / \ / \
b m f u 5 13
/ \ / \ / \
c d t y 11 15
ツリーに対して実行される操作には、深さ優先探索と幅優先探索という 2 つの主な方法のいずれかによる検索が必要です。深さ優先探索 (DFS) は、ツリーまたはグラフのデータ構造を走査または検索するためのアルゴリズムです。ルートから開始し、各ブランチに沿ってあり能な限り探索してからバックトラックします。深さ優先探索の走査には、前順序 訪問、左、右、内順序 訪問、右、後順序 左、右、訪問の 3 つの種類があります。幅優先探索 (BFS) は、ツリーまたはグラフの構造を走査または検索するためのアルゴリズムです。レベル順序では、下位レベルに移動する前に、そのレベルのすべてのノードを訪問します。
Exercise
以下は、挿入と出力の機能を持つ二分木の実装です。この木は順序付けされていますが、バランスはとれていません。この例では、挿入時に順序付けが維持されます。
出力ルーチンを深さ優先探索の pre-order に変更してください。
Sponsors
