Det binära trädet innebär att noden kan ha maximalt två barn. Här antyder binärt namn i sig att 'två'; därför kan varje nod ha antingen 0, 1 eller 2 barn.

Låt oss förstå det binära trädet genom ett exempel.

Ovanstående träd är ett binärt träd eftersom varje nod innehåller de yttersta två barnen. Den logiska representationen av ovanstående träd ges nedan:

turbo c++ ladda ner

I ovanstående träd innehåller nod 1 två pekare, dvs vänster och en höger pekare som pekar till vänster respektive höger nod. Noden 2 innehåller båda noderna (vänster och höger nod); därför har den två pekare (vänster och höger). Noderna 3, 5 och 6 är bladnoderna, så alla dessa noder innehåller NULL pekare på både vänster och höger del.

Egenskaper för binärt träd

• På varje nivå av i är det maximala antalet noder 2ⁱ.
• Trädets höjd definieras som den längsta vägen från rotnoden till lövnoden. Trädet som visas ovan har en höjd lika med 3. Därför är det maximala antalet noder på höjd 3 lika med (1+2+4+8) = 15. I allmänhet är det maximala antalet noder som är möjligt på höjden h är (2⁰+ 2¹+ 2²+….2^h) = 2^h+1-1.
• Minsta möjliga antal noder på höjden h är lika med h+1 .
• Om antalet noder är minimum, så skulle trädets höjd vara maximal. Omvänt, om antalet noder är maximalt, skulle trädets höjd vara minimum.

Om det finns 'n' antal noder i det binära trädet.

Minsta höjd kan beräknas som:

Som vi vet att,

n = 2^h+1-1

n+1 = 2^h+1

Ta stock på båda sidorna,

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

logga₂(n+1) = h+1

h = log₂(n+1) - 1

Den maximala höjden kan beräknas som:

Som vi vet att,

n = h+1

h=n-1

Typer av binära träd

Det finns fyra typer av binära träd:

Fullständig/ korrekt/ strikt binärt träd Komplett binärt träd Perfekt binärt träd Degenererat binärt träd Balanserat binärt träd

1. Fullständigt/ ordentligt/ strikt binärt träd

Det fullständiga binära trädet är också känt som ett strikt binärt träd. Trädet kan endast betraktas som det fullständiga binära trädet om varje nod måste innehålla antingen 0 eller 2 barn. Det fullständiga binära trädet kan också definieras som trädet där varje nod måste innehålla 2 barn utom lövnoderna.

Låt oss titta på det enkla exemplet med det fullständiga binära trädet.

I ovanstående träd kan vi observera att varje nod antingen innehåller noll eller två barn; därför är det ett fullständigt binärt träd.

Egenskaper för Full Binary Tree

• Antalet lövnoder är lika med antalet interna noder plus 1. I exemplet ovan är antalet interna noder 5; därför är antalet lövnoder lika med 6.
• Det maximala antalet noder är detsamma som antalet noder i det binära trädet, dvs 2^h+1-1.
• Minsta antalet noder i det fullständiga binära trädet är 2*h-1.
• Minsta höjden för det fullständiga binära trädet är logga₂(n+1) - 1.
• Den maximala höjden för det fullständiga binära trädet kan beräknas som:

n= 2*h - 1

n+1 = 2*h

h = n+1/2

Komplett binärt träd

Det kompletta binära trädet är ett träd där alla noder är helt fyllda utom den sista nivån. I den sista nivån måste alla noder vara så vänster som möjligt. I ett komplett binärt träd ska noderna läggas till från vänster.

Låt oss skapa ett komplett binärt träd.

Ovanstående träd är ett komplett binärt träd eftersom alla noder är helt fyllda och alla noder i den sista nivån läggs till till vänster först.

Egenskaper för komplett binärt träd

lexikografiskt

• Det maximala antalet noder i ett komplett binärt träd är 2^h+1- 1.
• Minsta antalet noder i ett komplett binärt träd är 2^h.
• Minsta höjden för ett komplett binärt träd är logga₂(n+1) - 1.
• Den maximala höjden för ett komplett binärt träd är

Perfekt binärt träd

Ett träd är ett perfekt binärt träd om alla interna noder har 2 barn, och alla lövnoder är på samma nivå.

Låt oss titta på ett enkelt exempel på ett perfekt binärt träd.

Nedanstående träd är inte ett perfekt binärt träd eftersom alla bladnoder inte är på samma nivå.

Notera: Alla de perfekta binära träden är de kompletta binära träden såväl som det fullständiga binära trädet, men vice versa är inte sant, det vill säga alla kompletta binära träd och fullständiga binära träd är de perfekta binära träden.

Degenererat binärt träd

Det degenererade binära trädet är ett träd där alla interna noder bara har ett barn.

Låt oss förstå det Degenererade binära trädet genom exempel.

Ovanstående träd är ett degenererat binärt träd eftersom alla noder bara har ett barn. Det är också känt som ett rättsnedvridet träd eftersom alla noder endast har ett högerbarn.

Ovanstående träd är också ett degenererat binärt träd eftersom alla noder bara har ett barn. Det är också känt som ett vänstersnett träd eftersom alla noder endast har ett vänsterbarn.

Balanserat binärt träd

Det balanserade binära trädet är ett träd där både vänster och höger träd skiljer sig åt med minst 1. Till exempel, AVL och Röd-svarta träd är balanserade binära träd.

Låt oss förstå det balanserade binära trädet genom exempel.

Ovanstående träd är ett balanserat binärt träd eftersom skillnaden mellan det vänstra underträdet och det högra underträdet är noll.

Ovanstående träd är inte ett balanserat binärt träd eftersom skillnaden mellan det vänstra underträdet och det högra underträdet är större än 1.

Implementering av binärt träd

Ett binärt träd implementeras med hjälp av pekare. Den första noden i trädet representeras av rotpekaren. Varje nod i trädet består av tre delar, dvs data, vänsterpekare och högerpekare. För att skapa ett binärt träd måste vi först skapa noden. Vi kommer att skapa noden för användardefinierad enligt nedan:

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

I ovanstående struktur, data är värdet, vänster pekare innehåller adressen till den vänstra noden, och höger pekare innehåller adressen till den högra noden.

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; } } 

Ovanstående kod anropar funktionen create() rekursivt och skapar en ny nod för varje rekursivt anrop. När alla noder skapas, bildar den en binär trädstruktur. Processen att besöka noderna är känd som trädpassering. Det finns tre typer av genomgångar som används för att besöka en nod:

• Inorder genomgång
• Förbeställ genomgång
• Postorder traversal