Ero täydellisen binaaripuun ja täydellisen binaaripuun välillä

Täydellinen binaaripuu vs. täydellinen binaaripuu

Binaaripuu on puu, jossa jokaisella solmulla on yksi tai kaksi lasta. Binaaripuussa solmulla voi olla enintään kaksi lasta. Binaaripuussa lapset kutsutaan ”vasen” ja ”oikea” lapsi. Lasten solmut sisältävät viittauksen vanhempiinsa. Täydellinen binaaripuu on binaaripuu, jossa jokainen binaaripuun taso on täysin täytetty, paitsi viimeinen taso. Täyttämättömällä tasolla solmut kiinnitetään vasemmasta reunasta. Täydellinen binääripuu on puu, jossa jokaisella puun solmulla on kaksi lasta paitsi puun lehdet.

Mikä on täydellinen binaaripuu?

Täysi binaarinen puu on binaarinen puu, jossa jokaisella puun solmulla on tarkalleen nolla tai kaksi lasta. Toisin sanoen jokaisella puun solmulla, paitsi lehtiä, on tarkalleen kaksi lasta. Seuraava kuva 1 kuvaa täydellistä binääristä puuta. Täysin binaarisessa puussa solmujen (n), lavojen (l) ja sisäisten solmujen (i) lukumäärä on kytketty erityisellä tavalla siten, että jos tiedät jonkin niistä, voit määrittää kaksi muuta arvot seuraavasti:

1. Jos täydellä binaaripuulla on i sisäisiä solmuja:

- Lehtien lukumäärä l = i + 1

- Solmujen kokonaismäärä n = 2 * i + 1

2. Jos täydellä binaaripuulla on n solmua:

- Sisäisten solmujen lukumäärä i = (n-1) / 2

- Lehtien lukumäärä l = (n + 1) / 2

3. Jos täydellä binaaripuulla on l lehtiä:

- Solmujen kokonaismäärä n = 2 * l-1

- Sisäisten solmujen lukumäärä i = l-1

Mikä on täydellinen binaaripuu?

Kuten kuviossa 2 esitetään, täydellinen binaaripuu on binaaripuu, jossa jokainen puun taso on täysin täytetty, paitsi viimeinen taso. Viimeisellä tasolla solmut tulisi myös kiinnittää vasemmasta reunasta alkaen. Täydellinen binaaripuu, jonka korkeus on h, täyttää seuraavat ehdot:

- Juurisolmusta lähtien viimeisen tason yläpuolella oleva taso edustaa koko binaarista puua, jonka korkeus on h-1

- Yhdellä tai useammalla viimeisen tason solmulla voi olla 0 tai 1 lapsi

- Jos a, b ovat kaksi solmua viimeisen tason yläpuolella olevalla tasolla, niin a: lla on enemmän lapsia kuin b, jos ja vain jos a sijaitsee vasemmalla b

Mitä eroa täydellisen binaaripuun ja täydellisen binaaripuun välillä on??

Täydellisillä binaaripuilla ja täydellisillä binaaripuilla on selvä ero. Vaikka täysi binaaripuu on binaaripuu, jossa jokaisella solmulla on nolla tai kaksi lasta, täydellinen binaaripuu on binaaripuu, jossa jokainen binaaripuun taso on täysin täytetty paitsi viimeinen taso. Joidenkin erityisten tietorakenteiden, kuten kasojen, on oltava täydellisiä binääripuita, kun taas niiden ei tarvitse olla täydellisiä binääripuita. Jos tiedät binaaripuun kokonaismäärästä, solmujen lukumäärästä tai sisäisten solmujen lukumäärästä, löydät kaksi muuta helppoa. Mutta täydellisellä binaaripuulla ei ole erityistä ominaisuutta, joka liittyy näihin kolmeen määritteeseen.