Hvad er et fuldt binært træ?
Et fuldt binært træ kan defineres som en binært træ hvor alle noderne har 0 eller to børn. Med andre ord kan det fulde binære træ defineres som et binært træ, hvor alle noderne har to børn undtagen bladknuderne.
Nedenstående træ er et fuldt binært træ:
Ovenstående træ er et fuldt binært træ, da alle noderne undtagen bladknuderne har to børn.
Fuld binær træsætning:
arrays java
Betragt et binært træ T som et ikke-tomt træ:
- Lad jeg være interne noder i et træ og L for at være en bladknude i et træ, så ville antallet af bladknuder være lig med:
L = I + 1 - Hvis T har I antallet af interne knudepunkter og N til at være det samlede antal knudepunkter, så vil det samlede antal knudepunkter være lig med:
N = 2I + 1 - Hvis T indeholder 'N' totalt antal noder og 'I' for at være antallet af interne noder, så vil antallet af interne noder være lig med:
I = (N-1)/2 - Hvis 'T' har 'N' totalt antal noder, og 'L' er et antal bladknuder, så vil antallet af bladknuder være lig med:
L = (N+1)/2 - Hvis 'T' indeholder 'L' antal bladknuder, vil det samlede antal knudepunkter være lig med:
N = 2L - 1 - Hvis 'T' har 'L' antal bladknuder, og 'I' er et antal interne knudepunkter, vil antallet af interne knudepunkter være lig med:
I = L - 1
Hvad er et komplet binært træ?
Et binært træ siges at være et komplet binært træ, når alle niveauerne er fuldstændigt fyldt undtagen det sidste niveau, som er fyldt fra venstre.
Nedenstående træ er et komplet binært træ:
Det komplette binære træ ligner det fulde binære træ bortset fra de to forskelle, som er angivet nedenfor:
- Fyldningen af bladknuden skal starte fra den venstre side.
- Det er ikke obligatorisk, at den sidste bladknude skal have den rigtige søskende.
Lad os forstå ovenstående punkter gennem et eksempel:
strengmetoder
Overvej nedenstående træ:
Ovenstående træ er et komplet binært træ, men ikke et fuldt binært træ, da node 6 ikke har sin rigtige søskende.
java indeks af
Oprettelse af komplet binært træ
Antag, at vi har en matrix af 6 elementer vist som nedenfor:
Ovenstående array indeholder 6 elementer, dvs. 1, 2, 3, 4, 5, 6. Følgende er de trin, der skal bruges til at skabe et komplet binært træ:
Trin 1: Først vil vi vælge det første element i arrayet, dvs. 1, og lave en rodknude til træet. Antallet af tilgængelige elementer i det første niveau er 1.
Trin 2: Nu vil vi vælge det andet og tredje element i arrayet. Behold det andet element og det tredje element i arrayet som henholdsvis venstre og højre underordnede af rodknuden vist som nedenfor:
Som vi kan observere ovenfor, er antallet af tilgængelige elementer på andet niveau 2.
Trin 3: Nu vil vi vælge de næste to elementer fra arrayet, dvs. 4 og 5. Hold disse to elementer til venstre og højre for node 2 vist som nedenfor:
Som vi kan observere ovenfor, er noderne 4 og 5 henholdsvis venstre og højre barn af node 2.
Trin 4: Nu vil vi vælge det sidste element i arrayet, dvs. 6, og beholde det som venstre underordnede af node 3, da vi ved, at i et komplet binært træ er noderne udfyldt fra venstre side vist som nedenfor:
k-nn algoritme
Som vi kan observere, indeholder det andet niveau 3 elementer.
Lad os forstå forskellene mellem komplet og fuldt binært træ gennem billederne.
- Det binære træ, som er vist nedenfor, er hverken et komplet eller et fuldt binært træ. Det er ikke et fuldt binært træ, fordi node 3 kun har ét barn. Det er heller ikke et komplet binært træ, da noderne skal udfyldes fra venstre side, men node 3 har et højre barn og har ikke et venstre barn.
- Det binære træ, som er vist nedenfor, er et fuldt binært træ, men ikke et komplet binært træ. Det er et fuldt binært træ, fordi alle noderne har enten 0 eller 2 børn. Det er ikke et komplet binært træ, fordi node 3 ikke har nogen børn, mens node 2 har sine børn, og vi ved, at noderne skal udfyldes fra venstre side i et komplet binært træ.
- Det binære træ, som er vist nedenfor, er et komplet binært træ, men ikke et fuldt binært træ. Det er et komplet binært træ, da alle noderne er udfyldt. Det er ikke et fuldt binært træ, da node 2 kun har ét barn.
- Det binære træ, som er vist nedenfor, er et komplet såvel som et fuldt binært træ. Det er et komplet binært træ, da alle noderne er udfyldt. Det er et fuldt binært træ, da alle noderne har enten 0 eller 2 børn.
