A

Binääripuu

Niitä on erilaisia binääripuutyypit mutta täällä aiomme keskustella erosta Täydellinen binääripuu ja Täysi binääripuu .

Täysi binaaripuu:

Täysi binääripuu on binääripuu, jossa kaikilla solmuilla on joko 0 tai 2 jälkeläistä . Toisin sanoen täysi binääripuu on binääripuu, jossa kaikilla solmuilla lehtisolmuja lukuun ottamatta on kaksi jälkeläistä.

Täysi binaarinen puu

Antaa, i on sisäisten solmujen lukumäärä
n on solmujen kokonaismäärä
l olla lehtien lukumäärä
l olla useita tasoja

Sitten,

Lehtien määrä on (i + 1) .
Solmujen kokonaismäärä on (2i + 1) .
Sisäisten solmujen lukumäärä on (n – 1) / 2 .
Lehtien määrä on (n + 1) / 2 .
Solmujen kokonaismäärä on (2 l - 1) .
Sisäisten solmujen lukumäärä on (l-1) .
Lehtien määrä on korkeintaan (2^l- 1) .

Täydellinen binääripuu:

Binääripuun sanotaan olevan a täydellinen binääripuu jos kaikilla sen tasoilla, paitsi mahdollisesti viimeisellä tasolla, on maksimimäärä mahdollisia solmuja ja kaikki solmut viimeinen taso näkyvät mahdollisimman vasemmalle .

Täydellinen binääripuu

On 2 pistettä, jotka voit tunnistaa täältä,

1. Lehtisolmun vasen puoli on aina täytettävä ensin.
2. Viimeisellä lehden solmulla ei tarvitse olla oikeaa sisarusta.

Tarkista seuraavat esimerkit ymmärtääksesi täydellisen ja täydellisen binääripuun paremmin.

Esimerkki 1:

Ei täydellinen eikä täysi

• Solmu C on siis vain yksi lapsi, se ei ole täysi binääripuu.
• Solmu C hänellä on myös oikea lapsi, mutta ei siis vasenta lasta se ei myöskään ole täydellinen binääripuu.

Näin ollen yllä oleva binääripuu on ei täydellinen eikä täysi binääripuu.

Esimerkki 2:

Täysi mutta ei täydellinen

sisältää merkkijonossa

• Kaikissa solmuissa on jompikumpi 0 tai 2 jälkeläisiä siis se on täysi binääripuu .
Se ei ole täydellinen binääripuu, koska solmu B ei ole lapsia, kun taas solmu C on lapsia, ja täydellisen binääripuun mukaan solmut tulee täyttää vasen puoli .

Tästä syystä yllä esitetty binääripuu on a Täysi binääripuu ja se on ei ole täydellinen binääripuu.