Erinevus täieliku kahendpuu ja täieliku kahendpuu vahel

Täielik binaarne puu vs täielik binaarne puu

Binaarne puu on puu, kus igal sõlmel on üks või kaks last. Binaarses puus ei tohi sõlmes olla rohkem kui kaks last. Binaarses puus nimetatakse lapsi vasak- ja parempoolseteks lasteks. Lapse sõlmed sisaldavad viidet oma vanemale. Täielik binaarne puu on binaarne puu, milles binaarpuu kõik astmed on täielikult täidetud, välja arvatud viimane tase. Täitmata tasemel kinnitatakse sõlmed alates vasakpoolsest servast. Täisbinaarne puu on puu, mille igas sõlmes on kaks last, välja arvatud puu lehed.

Mis on täisbinaarne puu?

Täisbinaarne puu on binaarne puu, milles igal puu sõlmel on täpselt null või kaks last. Teisisõnu, igal puusõlmel, välja arvatud lehed, on täpselt kaks last. Alloleval joonisel 1 on kujutatud täielik binaarne puu. Terves binaarses puus on sõlmede arv (n), järvede arv (l) ja sisemiste sõlmede arv (i) seotud erilisel viisil, nii et kui teate mõnda neist, saate määrata ülejäänud kaks väärtused järgmiselt:

1. Kui täielikul binaarsel puul on i sisemist sõlme:

- Lehtede arv l = i + 1

- Sõlmede koguarv n = 2 * i + 1

2. Kui terves binaarses puus on n sõlme:

- Sisemiste sõlmede arv i = (n-1) / 2

- Lehtede arv l = (n + 1) / 2

3. Kui tervel binaarsel puul on lehed:

- Sõlmede koguarv n = 2 * l-1

- Sisemiste sõlmede arv i = l-1

Mis on täielik kahendpuu?

Nagu on näidatud joonisel 2, on täielik binaarne puu binaarne puu, milles puu kõik astmed on täielikult täidetud, välja arvatud viimane tase. Samuti tuleks viimasel tasemel kinnitada sõlmed, alustades vasakpoolsest servast. Täielik binaarne puu kõrgusega h vastab järgmistele tingimustele:

- Juursõlmest alates tähistab viimase taseme kohal asuv tase täielikku binaarset puud kõrgusega h-1

- Ühel või mitmel viimase taseme sõlmel võib olla 0 või 1 laps

- Kui a, b on viimase taseme kohal kaks sõlme, siis a-l on rohkem lapsi kui b siis ja ainult siis, kui a asub b-st vasakul

Mis vahe on täielik binaarne puu ja täielik binaarne puu??

Täielikel binaarsel puul ja täielikul binaarsel puul on selge erinevus. Kui täielik binaarne puu on binaarne puu, kus igal sõlmel on null või kaks last, siis täielik binaarne puu on binaarne puu, kus binaarse puu kõik astmed on täielikult täidetud, välja arvatud viimane tase. Mõned spetsiaalsed andmestruktuurid, näiteks hunnikud, peavad olema täielikud binaarsed puud, samas kui need ei pea olema täielikud binaarsed puud. Kui teate binaarses puus, kui palju on sõlmede koguarvu või järvede arvu või sisemiste sõlmede arvu, leiate need ülejäänud kaks hõlpsalt. Kuid tervel binaarsel puul puudub spetsiaalne omadus, mis seoks neid kolme atribuuti.