理解する必要がある二分木の公式

1. 一般的なバイナリ ツリーのプロパティ

プロパティ 1. 空ではないバイナリ ツリーの i レベルには、最大でも2^i ノード。

プロパティ 2. 高さ K の二分木には、最大 2^(k 1)-1 個のノードがあります。

プロパティ 3. 空ではないバイナリ ツリーの場合、葉ノードの数が n0 で、次数 2 のノードの数が n2 の場合、n0=n2 1 となります。

2, 完全なバイナリ ツリー

定義: バイナリ ツリーの場合、下位 2 レベルのノードの次数のみが 2 未満です。他のすべてのレベルのノードが 2 に等しく、最下層のノードが層の左端の位置に集中している場合、この二分木は完全二分木と呼ばれます。

プロパティ 1. n 個のノードを持つ完全な二分木の高さ k は [log^2n] です。

プロパティ 2. n 個のノードを持つ完全なバイナリ ツリーの場合、バイナリ ツリー内のすべてのノードが上 (ルート ノード) から下 (葉ノード) まで、左から右に順序付けされている場合、番号付けは 0 から始まります。

(1) i=0 の場合、それはルート ノードであり、親ノードはありません。i>0 の場合、親ノードの添え字は (i-1)/2 です。

(2) 2i 1

(3) 2i 2

3, 完全なバイナリ ツリー

定義: バイナリ ツリーのいずれかのノードがリーフであるか、空ではない 2 つのサブツリーを持つ場合、このバイナリ ツリーはフルバイナリツリーと呼ばれます。

プロパティ、完全なバイナリ ツリーでは、葉ノードの数は枝ノードの数より 1 多くなります。

4, 拡張されたバイナリ ツリー

定義: 拡張されたバイナリ ツリーは、既存のバイナリ ツリーを拡張したものです。拡張後、元のバイナリ ツリーのノードは次のようになります。次数 2 の分岐。ノード。つまり、元のノードの次数が 2 の場合はそのまま、次数が 1 の場合は 1 つの枝が追加され、次数が 0 の場合は 2 つの枝が追加されます。

プロパティ 1. 拡張バイナリ ツリーでは、外部ノードの数は内部ノードの数より 1 多くなります。

プロパティ 2. 拡張二分木では、外部パス長 E と内部パス長 I の間に次の関係が満たされます: E=I 2n (n は内部ノードの数)。

よくある質問に関連する技術的な記事については、FAQ 列を参照してください。もっと！

以上が理解する必要がある二分木の公式の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。