データ構造における二分木表現
ここでは、コンピュータのメモリでバイナリツリーを表現する方法を説明します。表現するには2つの異なる方法があります。これらは配列とリンクリストを使用しています。
このようなツリーが1つあるとします-
配列表現は、レベル順の方法を使用して要素をスキャンすることにより、ツリーデータを格納します。したがって、ノードをレベルごとに格納します。一部の要素が欠落している場合は、空白のままにします。上記のツリーの表現は以下のようになります-
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| 10 | 5 | 16 | - | 8 | 15 | 20 | - | - | - | - | - | - | - | 23 |
インデックス1はルートを保持しており、2つの子5と16があり、場所2と3に配置されています。一部の子が欠落しているため、場所は空白のままになっています。
この表現では、次の式を使用して、1つのノードの2つの子の位置を簡単に取得できます-
$$ child_ {1} =2 * parent $$
$$ child_ {2} =\ lgroup2 * parent \ rgroup + 1 $$
子から親インデックスを取得するには、次の式に従う必要があります-
$$ parent =\ begin {bmatrix} \ frac {child} {2} \ end {bmatrix} $$
このアプローチは優れており、親と子のインデックスを簡単に見つけることができますが、メモリ効率は良くありません。それは役に立たない多くのスペースを占めるでしょう。この表現は、完全な二分木または完全な二分木に適しています。
別のアプローチは、リンクリストを使用することです。要素ごとにノードを作成します。これは以下のようになります-
-
データ構造における二分木探索
このセクションでは、バイナリ検索ツリーに存在するキーをトラバースするためのさまざまなトラバーサルアルゴリズムについて説明します。これらのトラバーサルは、インオーダートラバーサル、プレオーダートラバーサル、ポストオーダートラバーサル、およびレベルオーダートラバーサルです。 このようなツリーが1つあるとします- インオーダートラバーサルシーケンスは、-5 8 10 15 16 20 23のようになります。 プレオーダートラバーサルシーケンスは、-10 5 8 16 15 20 23のようになります。 ポストオーダートラバーサルシーケンスは次のようになります− 8 5 15 23 20
-
データ構造の二分木とプロパティ
このセクションでは、1つの二分木データ構造のいくつかの重要なプロパティを確認します。このような二分木があるとします。 一部のプロパティは-です レベル「l」のノードの最大数は$2^{l-1}$になります。ここで、レベルは、ルート自体を含む、ルートからノードへのパス上のノードの数です。ルートのレベルは1であると考えています。 高さhの二分木に存在するノードの最大数は$2^ {h}-1$です。ここで、heightは、ルートからリーフへのパス上のノードの最大数です。ここでは、1つのノードを持つ木の高さが1であると考えています。 n個のノードを持つ二分木では、可能な最小の高さまたは最小のレ