Binaaripuu tarkoittaa, että solmulla voi olla enintään kaksi lasta. Tässä binäärinimi itsessään viittaa siihen, että 'kaksi'; siksi jokaisella solmulla voi olla joko 0, 1 tai 2 lasta.

Ymmärretään binääripuu esimerkin kautta.

Yllä oleva puu on binääripuu, koska jokainen solmu sisältää äärimmäisen kaksi lasta. Yllä olevan puun looginen esitys on annettu alla:

Yllä olevassa puussa solmu 1 sisältää kaksi osoitinta, eli vasemman ja oikean osoittimen, jotka osoittavat vasempaan ja oikeaan solmuun. Solmu 2 sisältää molemmat solmut (vasen ja oikea solmu); siksi siinä on kaksi osoitinta (vasen ja oikea). Solmut 3, 5 ja 6 ovat lehtisolmuja, joten kaikki nämä solmut sisältävät TYHJÄ osoitin sekä vasemmalla että oikealla puolella.

Binaaripuun ominaisuudet

• Jokaisella i:n tasolla solmujen enimmäismäärä on 2ⁱ.
• Puun korkeus määritellään pisimmäksi poluksi juurisolmusta lehtisolmuun. Yllä esitetyn puun korkeus on 3. Siksi korkeudella 3 olevien solmujen maksimimäärä on (1+2+4+8) = 15. Yleensä korkeudella h suurin mahdollinen solmumäärä on (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Pienin mahdollinen solmumäärä korkeudella h on yhtä suuri kuin h+1 .
• Jos solmujen lukumäärä on minimi, niin puun korkeus olisi maksimi. Päinvastoin, jos solmujen lukumäärä on maksimi, puun korkeus olisi pienin.

Jos binääripuussa on 'n' määrä solmuja.

java regex $

Minimikorkeus voidaan laskea seuraavasti:

Kuten tiedämme,

n = 2^h+1-1

n+1 = 2^h+1

Ottaen puun molemmilta puolilta,

Hirsi₂(n+1) = log2(2^h+1)

Hirsi₂(n+1) = h+1

h = loki₂(n+1) - 1

Suurin korkeus voidaan laskea seuraavasti:

Kuten tiedämme,

n = h+1

h = n-1

Binääripuutyypit

Binääripuita on neljää tyyppiä:

Täysi / oikea / tiukka binaaripuu Täydellinen binaaripuu Täydellinen binaaripuu Degeneroitunut binaaripuu Tasapainoinen binaaripuu

1. Täysi / oikea / tiukka binaaripuu

matriisi javassa

Täysi binääripuu tunnetaan myös tiukkana binääripuuna. Puuta voidaan pitää täydellisenä binääripuuna vain, jos jokaisessa solmussa on oltava joko 0 tai 2 alapistettä. Täysi binääripuu voidaan myös määritellä puuksi, jossa jokaisessa solmussa on oltava 2 lapsia lehtisolmuja lukuun ottamatta.

Katsotaanpa yksinkertaista esimerkkiä koko binaaripuusta.

Yllä olevassa puussa voimme havaita, että jokainen solmu sisältää joko nollan tai kaksi lasta; siksi se on täysi binaarinen puu.

Täyden binaaripuun ominaisuudet

• Lehtisolmujen lukumäärä on yhtä suuri kuin sisäisten solmujen lukumäärä plus 1. Yllä olevassa esimerkissä sisäisten solmujen lukumäärä on 5; siksi lehtien solmujen lukumäärä on 6.
• Solmujen enimmäismäärä on sama kuin binääripuun solmujen lukumäärä, eli 2^h+1-1.
• Täyden binääripuun solmujen vähimmäismäärä on 2*h-1.
• Täyden binääripuun vähimmäiskorkeus on Hirsi₂(n+1) - 1.
• Täyden binääripuun maksimikorkeus voidaan laskea seuraavasti:

n = 2*h - 1

n+1 = 2*h

h = n+1/2

Täydellinen binääripuu

Täydellinen binääripuu on puu, jossa kaikki solmut ovat täysin täytettynä viimeistä tasoa lukuun ottamatta. Viimeisellä tasolla kaikkien solmujen on oltava mahdollisimman vasemmalla. Täydellisessä binääripuussa solmut tulee lisätä vasemmalta.

Luodaan täydellinen binääripuu.

Yllä oleva puu on täydellinen binääripuu, koska kaikki solmut ovat täysin täytettyinä ja kaikki viimeisen tason solmut lisätään ensin vasemmalle.

Täydellisen binaaripuun ominaisuudet

• Täydellisen binääripuun solmujen enimmäismäärä on 2^h+1- 1.
• Täydellisen binääripuun solmujen vähimmäismäärä on 2^h.
• Täydellisen binääripuun vähimmäiskorkeus on Hirsi₂(n+1) - 1.
• Täydellisen binääripuun enimmäiskorkeus on

Täydellinen binaaripuu

Puu on täydellinen binääripuu, jos kaikilla sisäisillä solmuilla on 2 lasta ja kaikki lehtisolmut ovat samalla tasolla.

Katsotaanpa yksinkertaista esimerkkiä täydellisestä binääripuusta.

Alla oleva puu ei ole täydellinen binääripuu, koska kaikki lehtien solmut eivät ole samalla tasolla.

Huomautus: Kaikki täydelliset binääripuut ovat täydellisiä binääripuita sekä täydellisiä binääripuita, mutta päinvastoin ei pidä paikkaansa, eli kaikki täydelliset binääripuut ja täydelliset binääripuut ovat täydellisiä binääripuita.

Degeneroitunut binääripuu

Degeneroitunut binääripuu on puu, jossa kaikilla sisäisillä solmuilla on vain yksi lapsi.

Ymmärretään degeneroitunutta binaaripuuta esimerkkien kautta.

Yllä oleva puu on rappeutunut binääripuu, koska kaikilla solmuilla on vain yksi lapsi. Se tunnetaan myös oikealle vinopuuna, koska kaikilla solmuilla on vain oikea lapsi.

Yllä oleva puu on myös rappeutunut binääripuu, koska kaikilla solmuilla on vain yksi lapsi. Se tunnetaan myös vasemmalle vinopuuna, koska kaikilla solmuilla on vain vasen lapsi.

Tasapainoinen binääripuu

Tasapainotettu binääripuu on puu, jossa sekä vasen että oikea puu eroavat korkeintaan 1:llä. AVL ja Puna-mustat puut ovat tasapainoisia binääripuuta.

Ymmärretään tasapainoinen binääripuu esimerkkien kautta.

Yllä oleva puu on tasapainotettu binääripuu, koska ero vasemman ja oikean alipuun välillä on nolla.

Yllä oleva puu ei ole tasapainotettu binääripuu, koska ero vasemman ja oikean alipuun välillä on suurempi kuin 1.

r c-kielellä

Binaaripuun toteutus

Binääripuu toteutetaan osoittimien avulla. Puun ensimmäistä solmua edustaa juuriosoitin. Jokainen puun solmu koostuu kolmesta osasta, eli tiedosta, vasemmasta ja oikeasta osoittimesta. Binääripuun luomiseksi meidän on ensin luotava solmu. Luomme käyttäjän määrittämän solmun alla olevan kuvan mukaisesti:

 struct node { int data, struct node *left, *right; } 

Yllä olevassa rakenteessa tiedot on arvo, vasen osoitin sisältää vasemman solmun osoitteen ja oikea osoitin sisältää oikean solmun osoitteen.

Binääripuu-ohjelma C-muodossa

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Yllä oleva koodi kutsuu create()-funktiota rekursiivisesti ja luo uuden solmun jokaisessa rekursiivisessa kutsussa. Kun kaikki solmut on luotu, se muodostaa binääripuurakenteen. Solmuissa vierailuprosessi tunnetaan nimellä puun läpikulku. Solmussa vierailemiseen käytetään kolmen tyyppisiä läpikulkuja:

• Tilauksen läpikulku
• Ennakkotilaa läpikulku
• Postimääräyksen läpikulku