二分木の 5 つの性質

#バイナリ ツリーには次の 5 つのプロパティがあります:

#1. i 番目 (i>=1)二分木の 1 つの層には最大 2＾(i - 1) 個のノードがあります。

2. 深さ k (k>=0) の二分木には、少なくとも k 個、最大で 2＾ｋｋ1 個のノードがあります。

3. 空ではない二分木の場合、葉ノードの数が n0 で、次数 2 の非葉ノードの数が n2 の場合、n0 = n2 +1 となります。

4. n 個のノードを持つ完全なバイナリ ツリーの深さは int_UP (log (2, n 1)) です。

5. n 個のノードを持つ完全な二分木が上から下に構築される場合、同じ層のノードには左から右に連続して 1、2、3 の番号が付けられます。 ． ． ． ． ． , n を計算し、このノード番号に従ってツリー内の各ノードを 1 次元配列に順番に格納し、番号 i のノードをノード i (i>=1 && i(1) i = 1 の場合、ノード i はルートであり、親ノードはありません; i> 1 の場合、ノード i の親ノードはノード int_DOWN (i / 2 );

(2) 2*i (3) 2*i(4) ノード番号 i が奇数の場合、i! =1 の場合、右側の兄弟位置にあり、その左側の兄弟はノード i-1 になります;

(5) ノード番号 i が偶数の場合、i! =n、左側の兄弟位置にあり、その右側の兄弟はノード i+1 です;

(6) ノード i のレベルは int_DOWN (log (2, i)) + 1 です。

いくつかのプロパティの証明

プロパティ 1 は数学的帰納法によって証明できます

プロパティ 2 の証明:

プロパティ 1 によるk 層の最大総ノード数は 2＾0＋2＾ 1＋...＋2^ (ｋ-1) = 2^ｋ- 1;

性質の証明３ :

まず、ノードの観点から、n1+n2+n0=n を式(1)とします;

エッジの観点から見ると、n2 は に接続されます。 2 つのエッジ、n1 が 1 つのエッジに接続され、n 個のノードがペアで接続されています。n-1 個の辺が必要で、2*n2+n1=n-1 が得られます。これは式 (2) です。

式 (1)-(2) から、

n0 -n2=1 が得られます。

以上が二分木の 5 つの性質の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。