Det binære træ betyder, at noden maksimalt kan have to børn. Her antyder binært navn i sig selv, at 'to'; derfor kan hver node have enten 0, 1 eller 2 børn.

Lad os forstå det binære træ gennem et eksempel.

Ovenstående træ er et binært træ, fordi hver node indeholder de yderste to børn. Den logiske repræsentation af ovenstående træ er givet nedenfor:

I ovenstående træ indeholder node 1 to pointere, dvs. venstre og højre pointer, der peger til henholdsvis venstre og højre node. Node 2 indeholder begge noder (venstre og højre node); derfor har den to pointere (venstre og højre). Noderne 3, 5 og 6 er bladknuderne, så alle disse noder indeholder NUL markør på både venstre og højre del.

Egenskaber af binært træ

• På hvert niveau af i er det maksimale antal noder 2^jeg.
• Træets højde er defineret som den længste vej fra rodknuden til bladknuden. Træet som er vist ovenfor har en højde lig med 3. Derfor er det maksimale antal noder i højden 3 lig med (1+2+4+8) = 15. Generelt er det maksimale antal noder muligt i højden h er (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Det mindste antal mulige noder i højden h er lig med h+1 .
• Hvis antallet af noder er minimum, så ville højden af ​​træet være maksimum. Omvendt, hvis antallet af noder er maksimalt, så vil højden af ​​træet være minimum.

Hvis der er 'n' antal noder i det binære træ.

Minimumshøjden kan beregnes som:

sammenlignelig grænseflade i java

Som vi ved det,

n = 2^h+1-1

n+1 = 2^h+1

Ved at tage træ på begge sider,

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

log₂(n+1) = h+1

h = log₂(n+1) - 1

Den maksimale højde kan beregnes som:

Som vi ved det,

n = h+1

arv i java

h = n-1

Typer af binære træer

Der er fire typer binært træ:

Fuldt/ ordentligt/ strengt binært træ Komplet binært træ Perfekt binært træ Degenereret binært træ Balanceret binært træ

1. Fuldt/ ordentligt/ strengt binært træ

Det fulde binære træ er også kendt som et strengt binært træ. Træet kan kun betragtes som det fulde binære træ, hvis hver node skal indeholde enten 0 eller 2 børn. Det fulde binære træ kan også defineres som det træ, hvor hver node skal indeholde 2 børn undtagen bladknuderne.

Lad os se på det enkle eksempel på det fulde binære træ.

I ovenstående træ kan vi observere, at hver node enten indeholder nul eller to børn; derfor er det et fuldt binært træ.

Egenskaber af fuldt binært træ

• Antallet af bladknuder er lig med antallet af interne knudepunkter plus 1. I ovenstående eksempel er antallet af interne knudepunkter 5; derfor er antallet af bladknuder lig med 6.
• Det maksimale antal noder er det samme som antallet af noder i det binære træ, dvs. 2^h+1-1.
• Minimumsantallet af noder i det fulde binære træ er 2*h-1.
• Minimumshøjden af ​​det fulde binære træ er log₂(n+1) - 1.
• Den maksimale højde af det fulde binære træ kan beregnes som:

n= 2*t - 1

n+1 = 2*h

h = n+1/2

Komplet binært træ

scanner.next java

Det komplette binære træ er et træ, hvor alle noder er fuldstændigt udfyldt undtagen det sidste niveau. På det sidste niveau skal alle noderne være så venstre som muligt. I et komplet binært træ skal noderne tilføjes fra venstre.

hvordan man forvandler streng til int

Lad os skabe et komplet binært træ.

Ovenstående træ er et komplet binært træ, fordi alle noderne er fuldstændigt fyldte, og alle noderne i det sidste niveau tilføjes først til venstre.

Egenskaber for komplet binært træ

• Det maksimale antal noder i det komplette binære træ er 2^h+1- 1.
• Minimumsantallet af noder i det komplette binære træ er 2^h.
• Minimumshøjden af ​​et komplet binært træ er log₂(n+1) - 1.
• Den maksimale højde af et komplet binært træ er

Perfekt binært træ

Et træ er et perfekt binært træ, hvis alle de indre noder har 2 børn, og alle bladknuderne er på samme niveau.

Lad os se på et simpelt eksempel på et perfekt binært træ.

Nedenstående træ er ikke et perfekt binært træ, fordi alle bladknuderne ikke er på samme niveau.

Bemærk: Alle de perfekte binære træer er de komplette binære træer såvel som det fulde binære træ, men omvendt er det ikke sandt, dvs. alle komplette binære træer og fulde binære træer er de perfekte binære træer.

Degenereret binært træ

Det degenererede binære træ er et træ, hvor alle de interne knudepunkter kun har ét børn.

Lad os forstå det degenererede binære træ gennem eksempler.

Ovenstående træ er et degenereret binært træ, fordi alle noderne kun har ét barn. Det er også kendt som et højreskævt træ, da alle noderne kun har et højre barn.

Ovenstående træ er også et degenereret binært træ, fordi alle noderne kun har ét barn. Det er også kendt som et venstreskævt træ, da alle noderne kun har et venstre barn.

Balanceret binært træ

Det balancerede binære træ er et træ, hvor både venstre og højre træ adskiller sig med mindst 1. F.eks. AVL og Rød-sorte træer er afbalancerede binære træer.

Lad os forstå det afbalancerede binære træ gennem eksempler.

fcfs

Ovenstående træ er et balanceret binært træ, fordi forskellen mellem venstre undertræ og højre undertræ er nul.

Ovenstående træ er ikke et balanceret binært træ, fordi forskellen mellem det venstre undertræ og det højre undertræ er større end 1.

Implementering af binært træ

Et binært træ implementeres ved hjælp af pointere. Den første knude i træet er repræsenteret af rodmarkøren. Hver knude i træet består af tre dele, dvs. data, venstre pointer og højre pointer. For at oprette et binært træ skal vi først oprette noden. Vi vil oprette noden af ​​brugerdefineret som vist nedenfor:

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

I ovenstående struktur, data er værdien, venstre markør indeholder adressen på den venstre knude, og højre pointer indeholder adressen på den højre 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; } } 

Ovenstående kode kalder funktionen create() rekursivt og skaber en ny node på hvert rekursivt kald. Når alle noderne er oprettet, danner det en binær træstruktur. Processen med at besøge noderne er kendt som trægennemgang. Der er tre typer gennemløb, der bruges til at besøge en node:

• Gennemgang af uorden
• Forudbestil gennemløb
• Postordregennemgang