EN
Et binært træ
Der er forskellige typer af binære træer men her skal vi diskutere forskellen på Komplet binært træ og Fuldt binært træ .
ipconfig til ubuntu
Fuldt binært træ:
Et fuldt binært træ er et binært træ, hvori alle noderne har enten 0 eller 2 afkom . Med andre ord er et fuldt binært træ et binært træ, hvor alle noder, undtagen bladknuderne, har to afkom.
Et fuldt binært træ
Lade, jeg være antallet af interne knudepunkter
n være det samlede antal noder
l være antal blade
l være antal niveauerDerefter,
Antallet af blade er (i + 1) .
Det samlede antal noder er (2i + 1) .
Antallet af interne noder er (n – 1) / 2 .
Antallet af blade er (n + 1) / 2 .
Det samlede antal noder er (2l – 1) .
Antallet af interne noder er (l – 1) .
Antallet af blade er højst (2l- 1) .
Komplet binært træ:
Et binært træ siges at være en komplet binært træ hvis alle dets niveauer, undtagen muligvis det sidste niveau, har det maksimale antal mulige noder, og alle noderne i sidste niveau vises så langt til venstre som muligt .
Et komplet binært træ
Der er 2 punkter, som du kan genkende herfra,
vindue.åbn
- Den venstre side af bladknuden skal altid udfyldes først.
- Det er ikke nødvendigt for den sidste bladknude at have en ret søskende.
Tjek følgende eksempler for at forstå det fulde og komplette binære træ på en bedre måde.
Eksempel 1:
Hverken komplet eller fuld
- Node C har derfor kun et barn, det er ikke et fuldt binært træ.
- Node C har også et højre barn, men intet venstre barn, derfor det er heller ikke et komplet binært træ.
Derfor er det binære træ vist ovenfor hverken komplet eller fuldt binært træ.
Eksempel 2:
Fuld men ikke komplet
- Alle noderne har enten 0 eller 2 afkom derfor, det er et fuldt binært træ .
Det er ikke et komplet binært træ, fordi node B har ingen børn, hvorimod node C har børn, og ifølge et komplet binært træ skal noder udfyldes fra venstre side .Derfor er det binære træ vist ovenfor en Fuldt binært træ og det er ikke et komplet binært træ.
normale former
Eksempel 3:
Komplet, men ikke fuld
Det er et komplet binært træ, da alle noderne er udfyldt.
- Node B har kun ét barn, derfor det er ikke et fuldt binært træ.
Derfor er det binære træ vist ovenfor en Komplet binært træ og det er ikke et fuldt binært træ.
Eksempel 4:
Fuldstændig og fuld
- Det er en Komplet binær træ, fordi alle noderne er venstre udfyldt .
- Alle noderne har enten 0 eller 2 afkom, derfor er det en fuldt binært træ .
Derfor er det binære træ vist ovenfor både et komplet og et fuldt binært træ.
| Ja Nej. | Komplet binært træ | Fuldt binært træ |
| 1. | I et komplet binært træ kan en node på det sidste niveau kun have ét barn. | I et fuldt binært træ kan en node ikke kun have ét barn. |
| 2. | I et komplet binært træ skal noden udfyldes fra venstre mod højre. | Der er ingen rækkefølge af udfyldning af noder i et fuldt binært træ. |
| 3. | Komplette binære træer bruges hovedsageligt i heap-baserede datastrukturer. | Fuldt binært træ har ingen anvendelse som sådan, men kaldes også et ordentligt binært træ. |
| 4. | Et komplet binært træ kaldes også næsten komplet binært træ. | Et fuldt binært træ også kaldet korrekt binært træ eller 2-træ. |
| 5 | Et komplet binært træ skal have hele bladknuden i nøjagtig samme dybde. | I fuldt binært træ behøver bladniveau ikke nødvendigvis at være i samme dybde. |