データ構造の二分木とプロパティ
このセクションでは、1つの二分木データ構造のいくつかの重要なプロパティを確認します。このような二分木があるとします。
一部のプロパティは-
です- レベル「l」のノードの最大数は$2^{l-1}$になります。ここで、レベルは、ルート自体を含む、ルートからノードへのパス上のノードの数です。ルートのレベルは1であると考えています。
- 高さhの二分木に存在するノードの最大数は$2^ {h}-1$です。ここで、heightは、ルートからリーフへのパス上のノードの最大数です。ここでは、1つのノードを持つ木の高さが1であると考えています。
- n個のノードを持つ二分木では、可能な最小の高さまたは最小のレベル数は$ \ log_ {2} \ lgroup {n + 1} \rgroup$です。リーフノードの高さを0と見なすと、式は$ \ log_ {2} \ lgroup {n + 1} \ rgroup-1 $ になります。
- 「L」の葉を持つ二分木には、少なくとも$ \ log_ {2} {L +1}$のレベル数があります
- 二分木に0個または2個の子がある場合、リーフノードの数は常に2個の子を持つノードより1つ多くなります。
N.B.二分木は一種の木なので、グラフ理論におけるツリーのすべての特性を備えています。
-
データ構造における二分木探索
このセクションでは、バイナリ検索ツリーに存在するキーをトラバースするためのさまざまなトラバーサルアルゴリズムについて説明します。これらのトラバーサルは、インオーダートラバーサル、プレオーダートラバーサル、ポストオーダートラバーサル、およびレベルオーダートラバーサルです。 このようなツリーが1つあるとします- インオーダートラバーサルシーケンスは、-5 8 10 15 16 20 23のようになります。 プレオーダートラバーサルシーケンスは、-10 5 8 16 15 20 23のようになります。 ポストオーダートラバーサルシーケンスは次のようになります− 8 5 15 23 20
-
データ構造における二分木表現
ここでは、コンピュータのメモリでバイナリツリーを表現する方法を説明します。表現するには2つの異なる方法があります。これらは配列とリンクリストを使用しています。 このようなツリーが1つあるとします- 配列表現は、レベル順の方法を使用して要素をスキャンすることにより、ツリーデータを格納します。したがって、ノードをレベルごとに格納します。一部の要素が欠落している場合は、空白のままにします。上記のツリーの表現は以下のようになります- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 10 5