Hva er et fullt binært tre?

Et fullt binært tre kan defineres som en binært tre der alle nodene har 0 eller to barn. Med andre ord kan det fulle binære treet defineres som et binært tre der alle nodene har to barn bortsett fra bladnodene.

Treet nedenfor er et fullstendig binært tre:

Treet ovenfor er et fullt binært tre da alle nodene unntatt bladnodene har to barn.

Full binær tresetning:

arrays java

Betrakt et binært tre som et ikke-tomt tre da:

• La jeg være interne noder i et tre og L for å være en bladnode i et tre, så vil antallet bladnoder være lik:
  L = I + 1
• Hvis T har I antall interne noder og N er det totale antallet noder, vil det totale antallet noder være lik:
  N = 2I + 1
• Hvis T inneholder 'N' totalt antall noder og 'I' for å være antall interne noder, vil antallet interne noder være lik:
  I = (N-1)/2
• Hvis 'T' har 'N' totalt antall noder, og 'L' er et antall bladnoder, vil antallet bladnoder være lik:
  L = (N+1)/2
• Hvis 'T' inneholder 'L' antall bladnoder, vil det totale antallet noder være lik:
  N = 2L - 1
• Hvis 'T' har 'L' antall bladnoder, og 'I' er et antall interne noder, vil antallet interne noder være lik:
  I = L - 1

Hva er et komplett binært tre?

Et binært tre sies å være et komplett binært tre når alle nivåene er fullstendig fylt bortsett fra det siste nivået, som er fylt fra venstre.

Treet nedenfor er et komplett binært tre:

Det komplette binære treet ligner på det fullstendige binære treet bortsett fra de to forskjellene som er gitt nedenfor:

• Fyllingen av bladnoden må starte fra venstre side.
• Det er ikke obligatorisk at siste bladknute må ha riktig søsken.

La oss forstå punktene ovenfor gjennom et eksempel:

strengmetoder

Tenk på treet nedenfor:

Treet ovenfor er et komplett binært tre, men ikke et fullt binært tre da node 6 ikke har sitt rette søsken.

c programstrengarray

Opprettelse av komplett binært tre

Anta at vi har en matrise med 6 elementer vist som nedenfor:

Arrayen ovenfor inneholder 6 elementer, dvs. 1, 2, 3, 4, 5, 6. Følgende er trinnene som skal brukes for å lage et komplett binært tre:

Trinn 1: Først vil vi velge det første elementet i matrisen, dvs. 1, og lage en rotnode av treet. Antall tilgjengelige elementer i det første nivået er 1.

Steg 2: Nå vil vi velge det andre og tredje elementet i matrisen. Hold det andre elementet og det tredje elementet i matrisen som venstre og høyre underordnede av rotnoden henholdsvis vist som nedenfor:

Som vi kan observere ovenfor, er antall tilgjengelige elementer på det andre nivået 2.

Trinn 3: Nå skal vi velge de neste to elementene fra matrisen, dvs. 4 og 5. Hold disse to elementene til venstre og høyre for node 2 vist som nedenfor:

Som vi kan observere ovenfor at node 4 og 5 er henholdsvis venstre og høyre barn til node 2.

Trinn 4: Nå vil vi velge det siste elementet i matrisen, dvs. 6, og beholde det som venstre underordnede av noden 3, da vi vet at i et komplett binært tre, er nodene fylt fra venstre side vist som nedenfor:

jsp

Som vi kan observere at det andre nivået inneholder 3 elementer.

La oss forstå forskjellene mellom komplett og fullt binært tre gjennom bildene.

1. Det binære treet som er vist nedenfor er verken et komplett eller et fullstendig binært tre. Det er ikke et fullstendig binært tre fordi node 3 har bare ett barn. Det er heller ikke et komplett binært tre da nodene skal fylles fra venstre side, men node 3 har høyre barn og har ikke venstre barn.
   
2. Det binære treet, som er vist nedenfor, er et fullstendig binært tre, men ikke et fullstendig binært tre. Det er et fullt binært tre fordi alle nodene har enten 0 eller 2 barn. Det er ikke et komplett binært tre fordi node 3 ikke har noen barn mens node 2 har sine barn og vi vet at nodene skal fylles fra venstre side i et komplett binært tre.
   
3. Det binære treet som er vist nedenfor er et komplett binært tre, men ikke et fullstendig binært tre. Det er et komplett binært tre ettersom alle nodene er fylt igjen. Det er ikke et fullstendig binært tre da node 2 bare har ett barn.
   
4. Det binære treet som er vist nedenfor er et komplett så vel som et fullstendig binært tre. Det er et komplett binært tre ettersom alle nodene er fylt igjen. Det er et fullt binært tre ettersom alle nodene har enten 0 eller 2 barn.