[ 通常表示 ]  [ 簡易表示 ]  [ シンプル表示 ]

「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典イメージぴよ画像「分かりそう」で「分からない」でも「分かった」気になれるIT用語辞典

完全二分木

pointこの用語のポイント

point枝分かれして広がっていく構造だよ

point1つの親に対して常に2つの子を持つよ

point枝分かれの最初から最後までの距離が全部同じだよ

スポンサーリンク

簡単に書くよ

完全二分木とは

パッと見で調和がとれている二分木のこと。(適当)
真面目に書くと

1つの親に対して常に2つの子を持ち、枝分かれの最初から最後までに挟む要素の数が全部同じなツリー構造(枝分かれして広がっていく構造)のこと
です。

image piyo

詳しく書くよ

順番に見ていきましょう。

ツリー構造木構造)は「1つのに対して複数のを持つ、枝分かれして広がっていく構造」ね。
上から下に広がっていく形で図を書くと、木を上下逆さまに見たような形になります。

完全二分木

このツリー構造のうち、枝分かれが最大2つまでのものを「二分木」と言います。
「最大つにかれる構造」だから「二分木」なんでしょうかね。

完全二分木2

二分木を構成する要素は

1.入ってくるのがなくて、出ていくのが2つ

完全二分木3

2.入ってくるのが1つで、出ていくのが2つ

完全二分木4

3.入ってくるのが1つで、出ていくのが1つ

完全二分木5

4.入ってくるのが1つで、出ていくのがない

完全二分木6

の4つです。

1が枝分かれのスタートです。
2と3が枝分かれの途中です。
4が枝分かれの最後になります。

完全二分木7

この二分木の中でも、特に

1.すべての枝分かれが2つ
2.すべての枝分かれの先っぽが最初の地点から同じ距離


になっている二分木が「完全二分木」です。
完全つにかれる構造」だから「完全二分木」なんでしょうかね。

完全二分木8

先ほど、二分木の要素は

1.入ってくるのがなくて、出ていくのが2つ
2.入ってくるのが1つで、出ていくのが2つ
3.入ってくるのが1つで、出ていくのが1つ
4.入ってくるのが1つで、出ていくのがない


の4つと説明しました。
この二分木の要素のうち

(1)3の要素がない

完全二分木9

(2)1から4に到着するまでの2の数が全部同じ

完全二分木10

になっている二分木が、完全二分木です。

image piyo2

一言でまとめるよ

まぁ「完全二分木」って単語が出てきたら「枝分かれの数が常に2つで、枝分かれの最初から最後までが全部同じ距離な二分木なんだな~」と、お考えください。

一番上に戻るよ
スポンサーリンク