Det binære treet betyr at noden kan ha maksimalt to barn. Her antyder binært navn i seg selv at 'to'; derfor kan hver node ha enten 0, 1 eller 2 barn.

La oss forstå det binære treet gjennom et eksempel.

Treet ovenfor er et binært tre fordi hver node inneholder de ytterste to barna. Den logiske representasjonen av treet ovenfor er gitt nedenfor:

I treet ovenfor inneholder node 1 to pekere, dvs. venstre og høyre peker som peker til henholdsvis venstre og høyre node. Noden 2 inneholder begge nodene (venstre og høyre node); derfor har den to pekere (venstre og høyre). Nodene 3, 5 og 6 er bladnodene, så alle disse nodene inneholder NULL peker på både venstre og høyre del.

Egenskaper til binært tre

• På hvert nivå av i er det maksimale antallet noder 2^Jeg.
• Høyden på treet er definert som den lengste veien fra rotnoden til bladnoden. Treet som er vist ovenfor har en høyde lik 3. Derfor er det maksimale antallet noder i høyden 3 lik (1+2+4+8) = 15. Generelt er det maksimalt mulige antallet noder i høyden h er (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Minimum antall noder mulig i høyden h er lik h+1 .
• Hvis antall noder er minimum, vil høyden på treet være maksimal. Omvendt, hvis antall noder er maksimalt, vil høyden på treet være minimum.

Hvis det er 'n' antall noder i det binære treet.

Minimumshøyden kan beregnes som:

sammenlignbart grensesnitt i java

Som vi vet det,

n = 2^h+1-1

n+1 = 2^h+1

Tar tømmerstokk på begge sider,

Logg₂(n+1) = log2(2^h+1)

Logg₂(n+1) = h+1

h = logg₂(n+1) - 1

Maksimal høyde kan beregnes som:

Som vi vet det,

n = h+1

np.gjennomsnitt

h = n-1

Typer av binære tre

Det er fire typer binære tre:

Fullt/ riktig/ strengt binært tre Komplett binært tre Perfekt binært tre Degenerert binært tre Balansert binært tre

1. Fullt/ riktig/ strengt binært tre

Det fulle binære treet er også kjent som et strengt binært tre. Treet kan bare betraktes som det fullstendige binære treet hvis hver node må inneholde enten 0 eller 2 barn. Det fulle binære treet kan også defineres som treet der hver node må inneholde 2 barn bortsett fra bladnodene.

La oss se på det enkle eksemplet på Full Binary-treet.

I treet ovenfor kan vi observere at hver node enten inneholder null eller to barn; derfor er det et fullt binært tre.

Egenskaper til Full Binary Tree

• Antall bladnoder er lik antall interne noder pluss 1. I eksemplet ovenfor er antallet interne noder 5; derfor er antallet bladnoder lik 6.
• Maksimalt antall noder er det samme som antall noder i det binære treet, dvs. 2^h+1-1.
• Minimum antall noder i hele binære treet er 2*h-1.
• Minimumshøyden på det fulle binære treet er Logg₂(n+1) - 1.
• Maksimal høyde på hele binære treet kan beregnes som:

n= 2*t - 1

n+1 = 2*t

h = n+1/2

Komplett binært tre

java int til dobbel

Det komplette binære treet er et tre der alle nodene er fullstendig fylt bortsett fra det siste nivået. På det siste nivået må alle nodene være så venstre som mulig. I et komplett binært tre skal nodene legges til fra venstre.

diskret matematikk negasjon

La oss lage et komplett binært tre.

Treet ovenfor er et komplett binært tre fordi alle nodene er fullstendig fylt, og alle nodene i det siste nivået legges til til venstre først.

Egenskaper til komplett binært tre

• Maksimalt antall noder i komplett binært tre er 2^h+1- 1.
• Minimum antall noder i komplett binært tre er 2^h.
• Minimumshøyden på et komplett binært tre er Logg₂(n+1) - 1.
• Maksimal høyde på et komplett binært tre er

Perfekt binært tre

Et tre er et perfekt binært tre hvis alle de interne nodene har 2 barn, og alle bladnodene er på samme nivå.

La oss se på et enkelt eksempel på et perfekt binært tre.

Treet nedenfor er ikke et perfekt binært tre fordi alle bladnodene ikke er på samme nivå.

Merk: Alle de perfekte binære trærne er de komplette binære trærne så vel som det fullstendige binære treet, men omvendt er ikke sant, det vil si at alle komplette binære trær og fulle binære trær er de perfekte binære trærne.

Degenerert binært tre

Det degenererte binære treet er et tre der alle interne noder bare har ett barn.

La oss forstå det degenererte binære treet gjennom eksempler.

Treet ovenfor er et degenerert binært tre fordi alle nodene har bare ett barn. Det er også kjent som et rettskjevt tre da alle nodene kun har et høyre barn.

Treet ovenfor er også et degenerert binært tre fordi alle nodene har bare ett barn. Det er også kjent som et venstreskjevt tre da alle nodene kun har et venstre barn.

Balansert binært tre

Det balanserte binære treet er et tre der både venstre og høyre tre er forskjellig med minst 1. For eksempel, AVL og Rød-svarte trær er balanserte binære tre.

La oss forstå det balanserte binære treet gjennom eksempler.

java-matriser

Treet ovenfor er et balansert binært tre fordi forskjellen mellom venstre undertre og høyre undertre er null.

Treet ovenfor er ikke et balansert binært tre fordi forskjellen mellom venstre undertre og høyre undertre er større enn 1.

Binær treimplementering

Et binært tre implementeres ved hjelp av pekere. Den første noden i treet er representert av rotpekeren. Hver node i treet består av tre deler, dvs. data, venstre peker og høyre peker. For å lage et binært tre, må vi først lage noden. Vi vil opprette noden til brukerdefinert som vist nedenfor:

 struct node { int data, struct node *left, *right; } 

I strukturen ovenfor, data er verdien, venstre peker inneholder adressen til venstre node, og høyre peker inneholder adressen til høyre node.

Binary Tree-program i C

 #include struct node { int data; struct node *left, *right; } void main() { struct node *root; root = create(); } struct node *create() { struct node *temp; int data; temp = (struct node *)malloc(sizeof(struct node)); printf('Press 0 to exit'); printf('
Press 1 for new node'); printf('Enter your choice : '); scanf('%d', &choice); if(choice==0) { return 0; } else { printf('Enter the data:'); scanf('%d', &data); temp->data = data; printf('Enter the left child of %d', data); temp->left = create(); printf('Enter the right child of %d', data); temp->right = create(); return temp; } } 

Koden ovenfor kaller create()-funksjonen rekursivt og oppretter ny node for hvert rekursivt kall. Når alle nodene er opprettet, danner det en binær trestruktur. Prosessen med å besøke nodene er kjent som tregjennomgang. Det er tre typer traverseringer som brukes for å besøke en node:

• Inorder kryssing
• Forhåndsbestill traversering
• Postordregjennomgang