あ

二分木

Inkscape vs Gimp

違いがある 二分木の種類 しかし、ここではその違いについて説明します。 完全な二分木 そして 完全なバイナリ ツリー 。

完全なバイナリ ツリー:

完全なバイナリ ツリーとは、次のようなバイナリ ツリーです。 すべてのノードには 0 または 2 の子孫があります 。言い換えると、完全なバイナリ ツリーは、リーフ ノードを除くすべてのノードに 2 つの子孫があるバイナリ ツリーです。

完全なバイナリ ツリー

させて、 私 内部ノードの数になります
n ノードの総数になります
私 葉の数になる
私 レベル数になる

それから、

葉の数は、 (i + 1) 。
ノードの総数は (2i + 1) 。
内部ノードの数は (n – 1) / 2 。
葉の数は、 (n + 1) / 2 。
ノードの総数は (2l-1) 。
内部ノードの数は (l – 1) 。
葉の数は最大で (2^私- 1) 。

完全なバイナリ ツリー:

二分木とは、 完全な二分木 おそらく最後のレベルを除くすべてのレベルに可能なノードの最大数があり、そのすべてのノードが 最後のレベルはできるだけ左に表示されます 。

完全な二分木

ここからわかるポイントは2つあり、

1. リーフ ノードの左端は常に最初に入力する必要があります。
2. 最後の葉ノードに正しい兄弟がある必要はありません。

完全なバイナリ ツリーをよりよく理解するには、次の例を確認してください。

Beatsヘッドフォンをペアリングする方法

例 2:

bash 読み取りファイル

完全だが完全ではない

• すべてのノードには次のいずれかが備わっています。 0 または 2 したがって、子孫は、 それは完全なバイナリツリーです 。
ノードが存在するため、完全なバイナリ ツリーではありません。 B ノードには子がありませんが、 C には子があり、完全なバイナリ ツリーによれば、ノードは 左側 。

したがって、上に示した二分木は 完全なバイナリ ツリー そしてそれは 完全なバイナリ ツリーではありません。

例 3:

完了しているが完全ではない

すべてのノードが満たされたままであるため、これは完全な二分木です。
• したがって、ノード B には子が 1 つだけあります。 完全なバイナリ ツリーではありません。

したがって、上に示した二分木は 完全な二分木 そしてそれは 完全なバイナリ ツリーではありません。

例 4:

完全かつ完全

• それは 完全なバイナリ すべてのノードが 満たされたまま 。
• すべてのノードには次のいずれかが備わっています。 0 または 2 子孫、 したがって、それは 完全なバイナリツリー 。

したがって、上に示した二分木は次のようになります。 完全なバイナリ ツリーと完全なバイナリ ツリーの両方。