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

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

2分木

pointこの用語のポイント

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

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

スポンサーリンク

簡単に書くよ

2分木とは

枝分かれが2つまでのツリー構造のこと。
もう少し噛み砕いて書くと

1つの親に対して最大2つまでの子を持つ、枝分かれして広がっていく構造のこと
です。

image piyo

詳しく書くよ

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

2分木

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

2分木2

2分木を構成する要素は

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

2分木3

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

2分木4

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

2分木5

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

2分木6

の4つです。

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

2分木7

また、2分木の中でも、特に

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


ものを「完全2分木」と言います。

2分木8

先ほど、2分木の要素は

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


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

(1)3の要素がない

2分木9

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

2分木10

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

ついでなので、一緒に覚えてあげてください。

image piyo2

一言でまとめるよ

まぁ「2分木」って単語が出てきたら「それぞれの要素の枝分かれが最大2つまでのツリー構造なんだな~」と、お考えください。

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