De binaire boom betekent dat het knooppunt maximaal twee kinderen kan hebben. Hier suggereert de binaire naam zelf dat 'twee'; daarom kan elk knooppunt 0, 1 of 2 kinderen hebben.

Laten we de binaire boom begrijpen aan de hand van een voorbeeld.

De bovenstaande boom is een binaire boom omdat elk knooppunt maximaal twee kinderen bevat. De logische weergave van de bovenstaande boom wordt hieronder gegeven:

In de bovenstaande boom bevat knooppunt 1 twee aanwijzers, d.w.z. een linker- en een rechteraanwijzer die respectievelijk naar het linker- en rechterknooppunt wijzen. Het knooppunt 2 bevat beide knooppunten (linker- en rechterknooppunt); daarom heeft het twee wijzers (links en rechts). De knooppunten 3, 5 en 6 zijn de bladknooppunten, dus al deze knooppunten bevatten NUL aanwijzer op zowel het linker- als het rechtergedeelte.

Eigenschappen van binaire boom

• Op elk niveau van i is het maximale aantal knooppunten 2ⁱ.
• De hoogte van de boom wordt gedefinieerd als het langste pad van het wortelknooppunt naar het bladknooppunt. De boom die hierboven wordt weergegeven heeft een hoogte gelijk aan 3. Daarom is het maximale aantal knooppunten op hoogte 3 gelijk aan (1+2+4+8) = 15. Over het algemeen is het maximale aantal knooppunten dat mogelijk is op hoogte h zijn (2⁰+ 2¹+ 2²+….2^H) = 2^u+1-1.
• Het minimaal mogelijke aantal knooppunten op hoogte h is gelijk aan u+1 .
• Als het aantal knooppunten minimaal is, is de hoogte van de boom maximaal. Omgekeerd, als het aantal knooppunten maximaal is, zou de hoogte van de boom minimaal zijn.

Als er 'n' aantal knooppunten in de binaire boom zijn.

De minimale hoogte kan als volgt worden berekend:

Zoals wij dat weten,

Java-collecties Java

n = 2^u+1-1

n+1 = 2^u+1

Aan beide kanten een log nemen,

loggen₂(n+1) = log2(2^u+1)

loggen₂(n+1) = h+1

h = logboek₂(n+1) - 1

De maximale hoogte kan als volgt worden berekend:

Zoals wij dat weten,

n = h+1

h= n-1

Soorten binaire boom

Er zijn vier soorten binaire bomen:

Volledige/juiste/strikte binaire boom Volledige binaire boom Perfecte binaire boom Gedegenereerde binaire boom Evenwichtige binaire boom

1. Volledige/juiste/strikte binaire boom

De volledige binaire boom wordt ook wel een strikt binaire boom genoemd. De boom kan alleen als de volledige binaire boom worden beschouwd als elk knooppunt 0 of 2 kinderen moet bevatten. De volledige binaire boom kan ook worden gedefinieerd als de boom waarin elk knooppunt twee kinderen moet bevatten, behalve de bladknooppunten.

Laten we eens kijken naar het eenvoudige voorbeeld van de volledige binaire boom.

In de bovenstaande boom kunnen we zien dat elk knooppunt nul of twee kinderen bevat; daarom is het een volledige binaire boom.

Eigenschappen van volledige binaire boom

• Het aantal bladknooppunten is gelijk aan het aantal interne knooppunten plus 1. In het bovenstaande voorbeeld is het aantal interne knooppunten 5; daarom is het aantal bladknooppunten gelijk aan 6.
• Het maximale aantal knooppunten is hetzelfde als het aantal knooppunten in de binaire boom, d.w.z. 2^u+1-1.
• Het minimumaantal knooppunten in de volledige binaire boom is 2*h-1.
• De minimale hoogte van de volledige binaire boom is loggen₂(n+1) - 1.
• De maximale hoogte van de volledige binaire boom kan als volgt worden berekend:

n= 2*u - 1

n+1 = 2*u

h = n+1/2

Volledige binaire boom

De volledige binaire boom is een boom waarin alle knooppunten volledig gevuld zijn, behalve het laatste niveau. Op het laatste niveau moeten alle knooppunten zo links mogelijk zijn. In een volledige binaire boom moeten de knooppunten vanaf de linkerkant worden toegevoegd.

Laten we een volledige binaire boom maken.

De bovenstaande boom is een volledige binaire boom omdat alle knooppunten volledig gevuld zijn en alle knooppunten op het laatste niveau eerst aan de linkerkant worden toegevoegd.

Eigenschappen van volledige binaire boom

• Het maximale aantal knooppunten in een volledige binaire boom is 2^u+1- 1.
• Het minimumaantal knooppunten in een volledige binaire boom is 2^H.
• De minimale hoogte van een volledige binaire boom is loggen₂(n+1) - 1.
• De maximale hoogte van een volledige binaire boom is

Perfecte binaire boom

Een boom is een perfecte binaire boom als alle interne knooppunten twee kinderen hebben en alle bladknooppunten zich op hetzelfde niveau bevinden.

Laten we eens kijken naar een eenvoudig voorbeeld van een perfecte binaire boom.

De onderstaande boom is geen perfecte binaire boom omdat niet alle bladknooppunten zich op hetzelfde niveau bevinden.

Opmerking: Alle perfecte binaire bomen zijn zowel de volledige binaire bomen als de volledige binaire boom, maar omgekeerd is dit niet waar, dat wil zeggen dat alle complete binaire bomen en volledige binaire bomen de perfecte binaire bomen zijn.

Gedegenereerde binaire boom

De gedegenereerde binaire boom is een boom waarin alle interne knooppunten slechts één kind hebben.

Laten we de gedegenereerde binaire boom begrijpen aan de hand van voorbeelden.

De bovenstaande boom is een gedegenereerde binaire boom omdat alle knooppunten slechts één kind hebben. Het wordt ook wel een naar rechts scheve boom genoemd, omdat alle knooppunten alleen een rechts kind hebben.

De bovenstaande boom is ook een gedegenereerde binaire boom omdat alle knooppunten slechts één kind hebben. Het wordt ook wel een linksscheve boom genoemd, omdat alle knooppunten alleen een links kind hebben.

samengestelde primaire sleutel

Evenwichtige binaire boom

De gebalanceerde binaire boom is een boom waarin zowel de linker- als de rechterboom maximaal 1 verschillen. Bijvoorbeeld: AVL En Rood-zwarte bomen zijn een evenwichtige binaire boom.

Laten we de gebalanceerde binaire boom begrijpen aan de hand van voorbeelden.

De bovenstaande boom is een gebalanceerde binaire boom omdat het verschil tussen de linker deelboom en de rechter deelboom nul is.

De bovenstaande boom is geen gebalanceerde binaire boom omdat het verschil tussen de linker deelboom en de rechter deelboom groter is dan 1.

Implementatie van binaire bomen

Een binaire boom wordt geïmplementeerd met behulp van pointers. Het eerste knooppunt in de boom wordt weergegeven door de rootpointer. Elk knooppunt in de boom bestaat uit drie delen, d.w.z. gegevens, linkeraanwijzer en rechteraanwijzer. Om een ​​binaire boom te maken, moeten we eerst het knooppunt maken. We zullen het door de gebruiker gedefinieerde knooppunt maken, zoals hieronder weergegeven:

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

In de bovenstaande structuur is gegevens is de waarde, linker wijzer bevat het adres van het linkerknooppunt, en rechter wijzer bevat het adres van het juiste knooppunt.

Binary Tree-programma in 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; } } 

De bovenstaande code roept de functie create() recursief aan en maakt een nieuw knooppunt bij elke recursieve aanroep. Wanneer alle knooppunten zijn gemaakt, vormt het een binaire boomstructuur. Het proces van het bezoeken van de knooppunten staat bekend als boomtraversal. Er zijn drie soorten traversals die worden gebruikt om een ​​knooppunt te bezoeken:

• In volgorde doorkruisen
• Doortocht vooraf bestellen
• Het passeren van postwissels