Forskellen mellem Komplet Binary Tree og Full Binary Tree

Komplet binært træ vs fuldt binært træ

Binært træ er et træ, hvor hver knude har et eller to børn. I et binært træ kan en node ikke have mere end to børn. I et binært træ benævnes børn som "venstre" og "højre" børn. Børneknuderne indeholder en henvisning til deres forælder. Et komplet binært træ er et binært træ, hvor hvert niveau af det binære træ er fuldt ud undtagen det sidste niveau. I det ufyldte niveau fastgøres knudepunkterne startende fra den mest venstre position. Et fuldt binært træ er et træ, hvor hver knude i træet har to børn undtagen træets blade.

Hvad er fuldt binært træ?

Fuldt binært træ er et binært træ, hvor hver knude i træet har nøjagtigt nul eller to børn. Med andre ord, hver knude i træet undtagen bladene har nøjagtigt to børn. Figur 1 nedenfor viser et fuldt binært træ. I et fuldt binært træ er antallet af noder (n), antallet af laves (l) og antallet af interne noder (i) relateret på en speciel måde, så hvis du kender nogen af ​​dem, kan du bestemme de to andre værdier som følger:

1. Hvis et fuldt binært træ har interne noder:

- Antal blade l = i + 1

- Samlet antal knudepunkter n = 2 * i + 1

2. Hvis et fuldt binært træ har n-noder:

- Antal interne noder i = (n-1) / 2

- Antal blade l = (n + 1) / 2

3. Hvis et fuldt binært træ har l-blade:

- Samlet antal knudepunkter n = 2 * l-1

- Antal interne noder i = l-1

Hvad er komplet binært træ?

Som vist i figur 2 er et komplet binært træ et binært træ, hvor hvert niveau af træet er fuldt ud undtagen det sidste niveau. I det sidste niveau skal der også knyttes knudepunkter, der starter fra den mest venstre position. Et komplet binært træ med højde h opfylder følgende betingelser:

- Fra rodnoden repræsenterer niveauet over sidste niveau et fuldt binært træ med højden h-1

- En eller flere noder i sidste niveau kan have 0 eller 1 børn

- Hvis a, b er to noder i niveauet over det sidste niveau, har a flere børn end b hvis og kun hvis a er placeret tilbage af b

Hvad er forskellen mellem Komplet Binary Tree og Full Binary Tree?

Komplette binære træer og fulde binære træer har en klar forskel. Mens et fuldt binært træ er et binært træ, hvor hvert knudepunkt har nul eller to børn, er et komplet binært træ et binært træ, hvor hvert niveau af det binære træ er fuldt ud undtagen det sidste niveau. Nogle specielle datastrukturer som dynger skal være komplette binære træer, mens de ikke behøver at være fulde binære træer. I et fuldt binært træ, hvis du kender antallet af samlede noder eller antallet af høje eller antallet af interne noder, kan du finde de andre to meget let. Men et komplet binært træ har ikke en særlig egenskab, der vedrører disse tre attributter.