Mikä on täysi binääripuu?

Täysi binääripuu voidaan määritellä a binääripuu jossa kaikilla solmuilla on 0 tai kaksi lasta. Toisin sanoen koko binääripuu voidaan määritellä binääripuuksi, jossa kaikilla solmuilla on kaksi lasta lehtisolmuja lukuun ottamatta.

ei tulosignaalia

Alla oleva puu on täysi binääripuu:

Yllä oleva puu on täysi binääripuu, koska kaikilla solmuilla lehtisolmuja lukuun ottamatta on kaksi lasta.

Täysi binaaripuulause:

Katsotaanpa binaaripuuta T ei-tyhjäksi puuksi:

• Olkoon minä puun sisäisiä solmuja ja L lehtisolmuja puussa, niin lehtisolmujen lukumäärä olisi yhtä suuri:
  L = I + 1
• Jos T:llä on I lukumäärä sisäisiä solmuja ja N on solmujen kokonaismäärä, niin solmujen kokonaismäärä olisi yhtä suuri:
  N = 2I + 1
• Jos T sisältää 'N' solmujen kokonaismäärän ja 'I' on sisäisten solmujen lukumäärä, sisäisten solmujen lukumäärä olisi yhtä suuri:
  I = (N-1)/2
• Jos 'T':llä on 'N' solmujen kokonaismäärä ja 'L' on lehtisolmujen lukumäärä, lehtisolmujen lukumäärä olisi yhtä suuri:
  L = (N+1)/2
• Jos 'T' sisältää 'L' lukumäärän lehtisolmuja, solmujen kokonaismäärä olisi yhtä suuri:
  N = 2L - 1
• Jos 'T':ssä on 'L' lehtisolmuja ja 'I' on sisäisten solmujen lukumäärä, sisäisten solmujen lukumäärä olisi yhtä suuri:
  I = L - 1

Mikä on täydellinen binääripuu?

Binääripuun sanotaan olevan täydellinen binääripuu, kun kaikki tasot ovat täysin täytettyinä paitsi viimeinen taso, joka täytetään vasemmalta.

Alla oleva puu on täydellinen binääripuu:

Täydellinen binääripuu on samanlainen kuin täysi binääripuu, lukuun ottamatta kahta alla olevaa eroa:

• Lehtisolmun täyttö tulee aloittaa vasemmalta puolelta.
• Ei ole pakollista, että viimeisellä lehtisolmulla on oltava oikea sisarus.

Ymmärretään yllä olevat kohdat esimerkin avulla:

Harkitse alla olevaa puuta:

Yllä oleva puu on täydellinen binääripuu, mutta ei täysi binääripuu, koska solmulla 6 ei ole sen oikeaa sisarusta.

Täydellisen binaaripuun luominen

Oletetaan, että meillä on alla olevan 6 elementin joukko:

Yllä oleva taulukko sisältää 6 elementtiä, eli 1, 2, 3, 4, 5, 6. Seuraavia vaiheita käytetään täydellisen binääripuun luomiseen:

Vaihe 1: Ensin valitaan taulukon ensimmäinen elementti, eli 1, ja tehdään puun juurisolmu. Ensimmäisellä tasolla käytettävissä olevien elementtien lukumäärä on 1.

Vaihe 2: Nyt valitsemme taulukon toisen ja kolmannen elementin. Säilytä taulukon toinen elementti ja kolmas elementti juurisolmun vasempana ja oikeanpuoleisena lapsina, kuten alla:

Kuten yllä havaitsemme, toisella tasolla käytettävissä olevien elementtien lukumäärä on 2.

Vaihe 3: Nyt valitsemme taulukosta seuraavat kaksi elementtiä, eli 4 ja 5. Pidä nämä kaksi elementtiä solmun 2 vasemmalla ja oikealla puolella alla esitetyllä tavalla:

Kuten edellä voidaan havaita, solmut 4 ja 5 ovat solmun 2 vasen ja oikea lapsi.

Vaihe 4: Nyt valitaan taulukon viimeinen elementti, eli 6, ja pidetään se solmun 3 vasemmana lapsena, koska tiedämme, että täydellisessä binääripuussa solmut täytetään vasemmalta puolelta kuten alla:

Kuten voimme havaita, että toinen taso sisältää 3 elementtiä.

Ymmärretään täydellisen ja täyden binääripuun erot kuvien avulla.

css lihavointiin

1. Alla esitetty binääripuu ei ole täydellinen eikä täysi binääripuu. Se ei ole täysi binääripuu, koska solmulla 3 on vain yksi lapsi. Se ei myöskään ole täydellinen binääripuu, koska solmut tulisi täyttää vasemmalta puolelta, mutta solmulla 3 on oikea lapsi, mutta sillä ei ole vasenta lasta.
   
2. Alla oleva binääripuu on täysi binääripuu, mutta ei täydellinen binääripuu. Se on täysi binääripuu, koska kaikilla solmuilla on joko 0 tai 2 lasta. Se ei ole täydellinen binääripuu, koska solmulla 3 ei ole lapsia, kun taas solmulla 2 on lapsensa ja tiedämme, että solmut tulisi täyttää vasemmalta puolelta täydellisessä binääripuussa.
   
3. Alla oleva binääripuu on täydellinen binääripuu, mutta ei täysi binääripuu. Se on täydellinen binääripuu, koska kaikki solmut jätetään täytetyiksi. Se ei ole täysi binääripuu, koska solmulla 2 on vain yksi lapsi.
   
4. Alla oleva binääripuu on sekä täydellinen että täysi binääripuu. Se on täydellinen binääripuu, koska kaikki solmut jätetään täytetyiksi. Se on täysi binääripuu, koska kaikilla solmuilla on joko 0 tai 2 lasta.