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

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

二分木

pointこの用語のポイント

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

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

スポンサーリンク

簡単に書くよ

二分木とは

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

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つまでのツリー構造なんだな~」と、お考えください。

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