Forskel mellem komplet binært træ og fuld binærtræ

Komplet binærtræ vs fuld binærtræ

Binærtræ er et træ, hvor hver knude har en eller to børn. I et binært træ kan en knude ikke have mere end to børn. I et binærtræ betegnes børn som "venstre" og "rigtige" børn. Børneknuderne indeholder en henvisning til deres forælder. Et komplet binærtræ er et binært træ, hvor hvert niveau af det binære træ er fuldstændigt fyldt undtagen det sidste niveau. I det uopfyldte niveau er knudepunkterne fastgjort ud fra venstre side. Et fuldt binærtræ er et træ, hvor hver knude i træet har to børn undtagen træets blade.

Hvad er fuld binærtræ?

Fuld binærtræ er et binært træ, hvor hver knude i træet har nøjagtigt nul eller to børn. Med andre ord har hver knude i træet undtagen bladene nøjagtigt to børn. Figur 1 nedenfor viser et fuldt binærtræ. I et fuldt binært træ er antallet af noder (n), antal laves (l) og antallet af interne noder (i) relateret på en særlig 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ærtræ har i interne noder:

- Antal blade l = i + 1

- Samlet antal noder n = 2 * i + 1

2. Hvis et fuldt binærtræ har n noder:

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

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

3. Hvis et fuldt binærtræ har l blade:

- Samlet antal noder n = 2 * l-1

- Antal interne noder i = 1-1

Hvad er komplet binærtræ?

Som vist i figur 2 er et komplet binærtræ et binærtræ, hvor hvert niveau af træet er fuldstændigt fyldt undtagen det sidste niveau. På det sidste niveau skal der også knyttes knuder fra start til venstre. Et komplet binært træ med højde h opfylder følgende betingelser:

- Fra rodknuden repræsenterer niveauet over sidste niveau et fuldt binært træhøjde h-1

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

- Hvis a, b er to noder i niveauet over det sidste niveau, så har a flere børn end b hvis og kun hvis a er placeret til venstre for b

Hvad er forskellen mellem Complete Binary Tree og fuld binærtræ?

Komplette binære træer og fulde binære træer har en klar forskel. Mens et fuldt binærtræ er et binært træ, hvor hver knude har nul eller to børn, er et komplet binærtræ et binærtræ, hvor hvert niveau af binærtræet er fuldstændigt fyldt 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 fuld binærtræ, hvis du kender antallet af samlede noder eller antallet af laves eller antallet af interne knuder, kan du finde de to andre meget let.Men et komplet binærtræ har ikke en særlig ejendom, der relaterer disse tre attributter.