EN
Et binært tre
Det er forskjellige typer binære tre men her skal vi diskutere forskjellen på Komplett binært tre og Fullt binært tre .
ipconfig for ubuntu
Fullt binært tre:
Et fullt binært tre er et binært tre der alle nodene har enten 0 eller 2 avkom . Med andre ord er et fullt binært tre et binært tre der alle noder, bortsett fra bladnodene, har to avkom.
Et fullt binært tre
La, Jeg være antall interne noder
n være det totale antallet noder
l være antall blader
l være antall nivåerDeretter,
Antall blader er (i + 1) .
Totalt antall noder er (2i + 1) .
Antall interne noder er (n – 1) / 2 .
Antall blader er (n + 1) / 2 .
Totalt antall noder er (2l – 1) .
Antall interne noder er (l – 1) .
Antall blader er på det meste (2l- 1) .
Komplett binært tre:
Et binært tre sies å være en komplett binært tre hvis alle nivåene, unntatt det siste nivået, har maksimalt antall mulige noder, og alle nodene i siste nivå vises så langt til venstre som mulig .
Et komplett binært tre
Det er 2 punkter du kan kjenne igjen herfra,
Last ned autocad 2019 engelsk mediafire
- Den venstre siden av bladnoden skal alltid fylles først.
- Det er ikke nødvendig for den siste bladnoden å ha et riktig søsken.
Sjekk følgende eksempler for å forstå det fullstendige og komplette binære treet på en bedre måte.
Eksempel 1:
Verken komplett eller full
- Node C har derfor bare ett barn, det er ikke et fullstendig binært tre.
- Node C har også et høyre barn, men ikke noe venstre barn, derfor det er heller ikke et komplett binært tre.
Derfor er det binære treet vist ovenfor verken komplett eller fullt binært tre.
Eksempel 2:
Full, men ikke komplett
- Alle nodene har enten 0 eller 2 avkom, derfor, det er et fullt binært tre .
Det er ikke et komplett binært tre fordi node B har ingen barn mens node C har barn, og i henhold til et komplett binært tre, skal noder fylles fra venstre side .Derfor er det binære treet vist ovenfor en Fullt binært tre og det er ikke et komplett binært tre.
normale former
Eksempel 3:
Komplett men ikke full
Det er et komplett binært tre ettersom alle nodene er fylt igjen.
- Node B har derfor bare ett barn det er ikke et fullstendig binært tre.
Derfor er det binære treet vist ovenfor en Komplett binært tre og det er ikke et fullstendig binært tre.
Eksempel 4:
Komplett og full
- Det er en Fullfør binær tre fordi alle nodene er venstre fylt .
- Alle nodene har enten 0 eller 2 avkom, derfor er det en fullt binært tre .
Derfor er det binære treet vist ovenfor både et komplett og et fullstendig binært tre.
| Ja Nei. | Komplett binært tre | Fullt binært tre |
| 1. | I et komplett binært tre kan en node på det siste nivået bare ha ett barn. | I et fullt binært tre kan ikke en node bare ha ett barn. |
| 2. | I et komplett binært tre skal noden fylles fra venstre mot høyre. | Det er ingen rekkefølge for å fylle noder i et fullt binært tre. |
| 3. | Komplette binære trær brukes hovedsakelig i heap-baserte datastrukturer. | Fullt binært tre har ingen applikasjon som sådan, men kalles også et skikkelig binært tre. |
| 4. | Et komplett binært tre kalles også nesten komplett binært tre. | Et fullt binært tre også kalt riktig binært tre eller 2-tre. |
| 5 | Et komplett binært tre må ha hele bladnoden i nøyaktig samme dybde. | I fullt binært tre behøver ikke bladnivået nødvendigvis være i samme dybde. |