二分木の基本的な性質

コンピュータ サイエンスでは、バイナリ ツリーは、ノードごとに最大 2 つのサブツリーを持つツリー構造です。通常、サブツリーは「左サブツリー」および「右サブツリー」と呼ばれます。バイナリ ツリーは、バイナリ検索ツリーとバイナリ ヒープの実装によく使用されます。

深さ k で 2^k-1 個のノードを持つバイナリ ツリーは、フル バイナリ ツリーと呼ばれます。この種のツリーの特徴は、各レベルのノード数が最大ノード数であることです。バイナリ ツリーでは、最後のレベルを除いて、他のすべてのレベルがいっぱいで、最後のレベルがいっぱいであるか、右側にいくつかの連続したノードが欠けている場合、そのバイナリ ツリーは完全なバイナリ ツリーです。 n 個のノードを持つ完全なバイナリ ツリーの深さは、floor(log2n) 1 です。深さ k の完全なバイナリ ツリーには、少なくとも 2k-1 個のリーフ ノード、最大で 2k-1 個のノードがあります。

バイナリ ツリーのプロパティ

(1) 空ではないバイナリ ツリーでは、i 番目のレベルのノードの総数は を超えません。 i>=1;

(2) 深さ h のバイナリ ツリーには、最大 個のノード (h>=1) と少なくとも h 個のノードがあります;

(3) 任意の二分木、葉ノードの数が N0 で、次数 2 のノードの総数が N2 の場合、N0=N2 1;

(4) n 個のノードを持つ完全な二分木の深さは (注: [ ] は切り捨てを意味します)

推奨コース: PHP チュートリアル 。

(5) N 個のノードを持つ完全なバイナリ ツリーの各ノードが順番に格納される場合、ノードには次の関係があります。

I がノード番号の場合、I> の場合;1、その親ノードの数は I/2 です;

2*IN の場合、左の子はありません;

2*I 1 の場合;N、その場合、適切な子供は存在しません。

(6) N 個のノードが与えられると、h(N) 個の異なるバイナリ ツリーを形成できます。

h(N) はカテラン数の N 項です。 h(n)=C(2*n,n)/(n 1)。

(7) 分岐点は i 個あり、I はすべての分岐点の道長の合計、J は葉の道長の合計 J=I 2i [2]

基本概念

バイナリ ツリーは再帰的に定義され、そのノードは左右のサブツリーに分割されます。論理的には、バイナリ ツリーには 5 つの基本形式があります:

(1 ) 空のバイナリ ツリー - 図 (a) に示す;

(2) ルート ノードが 1 つだけあるバイナリ ツリー - (b) に示す;

(3) のみ左のサブツリー - (c) に示すように;

(4) 右のサブツリーのみ - 図 (d) に示すように;

(5) 完全なバイナリ ツリー - (e に示す) ）。

注: バイナリ ツリーにはツリーと多くの類似点がありますが、バイナリ ツリーはツリーの特殊なケースではありません。 [1]

Type

(1) 完全な二分木 - 二分木の高さが h の場合、h 番目の層を除き、他のすべての層(1~h -1) ノード数が最大数に達しました h 層には葉ノードがあり、それが左から右に並んでいる完全な二分木です。

(2) 完全なバイナリ ツリー - リーフ ノードを除くすべてのノードに左右のサブリーフがあり、リーフ ノードがすべて最下位にあるバイナリ ツリー。

(3) バランス バイナリ ツリー - バランス バイナリ ツリーは、AVL ツリーとも呼ばれます (AVL アルゴリズムとは異なります)。これはバイナリ ソート ツリーであり、次の特性があります: 空のツリーであるか、または左右のサブツリー間の高さの差の絶対値は 1 を超えず、左右のサブツリーは両方ともバランスの取れた二分木です。

識別

二分木は木の特別なケースではありません。木と多くの類似点がありますが、木と二分木の間には 2 つの主な違いがあります:

1. ツリー内のノードの最大次数に制限はありませんが、バイナリ ツリー内のノードの最大次数は 2 です;

2. 間には左右の区別はありません。木のノード、二分木のノードには左と右があります。

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