Binaire boomgegevensstructuur in C ++

binary tree data structure c

Deze diepgaande zelfstudie over binaire bomen in C ++ legt typen, representatie, verplaatsing, toepassingen en implementatie van binaire bomen in C ++ uit:

Een binaire boom is een veelgebruikte boomgegevensstructuur. Als elk knooppunt van een boom maximaal twee onderliggende knooppunten heeft, wordt de boom een ​​binaire boom genoemd.

Dus een typische binaire boom heeft de volgende componenten:

• Een linker substructuur
• Een hoofdknooppunt
• Een juiste substructuur

​ Bekijk de volledige lijst met C ++ - zelfstudies in deze serie.

Wat je leert:

• Binaire structuur in C ++
• Soorten binaire boom
  • # 1) Volledige binaire boom
  • # 2) Volledige binaire structuur
  • # 3) Perfecte binaire boom
  • # 4) Een gedegenereerde boom
  • # 5) Evenwichtige binaire boom
• Binaire boomweergave
  • # 1) Opeenvolgende weergave
  • # 2) Vertegenwoordiging op een gekoppelde lijst
• Binaire boomimplementatie in C ++
• Binaire Tree Traversal
• Toepassingen van binaire boom
• Gevolgtrekking
• Aanbevolen literatuur

Binaire structuur in C ++

Een picturale weergave van een binaire boom wordt hieronder getoond:

In een bepaalde binaire boom is het maximale aantal knooppunten op elk niveau 2^l-1waarbij ‘l’ het niveaunummer is.

Dus in het geval van het rootknooppunt op niveau 1, is het maximale aantal knooppunten = 2^1-1= 2⁰= 1

Aangezien elk knooppunt in een binaire boom maximaal twee knooppunten heeft, is het maximale aantal knooppunten op het volgende niveau 2 * 2^l-1​

hoe u het .jar-bestand uitvoert

Gegeven een binaire boom met diepte of hoogte van h, het maximale aantal knooppunten in een binaire boom met hoogte h = 2^h- 1.

Vandaar dat in een binaire boom met een hoogte van 3 (hierboven weergegeven) het maximale aantal knooppunten = 2³-1 = 7.

Laten we nu de verschillende soorten binaire bomen bespreken.

Soorten binaire boom

Hieronder volgen de meest voorkomende soorten binaire bomen.

# 1) Volledige binaire boom

Een binaire boom waarin elk knooppunt 0 of 2 kinderen heeft, wordt een volledige binaire boom genoemd.

Hierboven is een volledige binaire boom weergegeven waarin we kunnen zien dat al zijn knooppunten behalve de bladknooppunten twee kinderen hebben. Als L het aantal bladknooppunten is en ‘l’ het aantal interne of niet-bladknooppunten is, dan is voor een volledige binaire boom L = l + 1.

# 2) Volledige binaire structuur

Een complete binaire boom heeft alle niveaus gevuld behalve het laatste niveau en het laatste niveau heeft al zijn knooppunten zo veel als links.

De hierboven getoonde boom is een complete binaire boom. Een typisch voorbeeld van een complete binaire boom is een binaire heap die we in de latere tutorials zullen bespreken.

# 3) Perfecte binaire boom

Een binaire boom wordt perfect genoemd als alle interne knooppunten twee kinderen hebben en alle bladknooppunten zich op hetzelfde niveau bevinden.

Een binair boomvoorbeeld hierboven is een perfecte binaire boom aangezien elk van zijn knooppunten twee kinderen heeft en alle bladknooppunten zich op hetzelfde niveau bevinden.

Een perfecte binaire boom van hoogte h heeft 2^h- 1 aantal knooppunten.

# 4) Een gedegenereerde boom

Een binaire boom waarbij elk intern knooppunt slechts één kind heeft, wordt een gedegenereerde boom genoemd.

De hierboven getoonde boom is een gedegenereerde boom. Wat betreft de prestaties van deze boom zijn de gedegenereerde bomen hetzelfde als gekoppelde lijsten.

# 5) Evenwichtige binaire boom

Een binaire boom waarin de diepte van de twee substructuren van elk knooppunt nooit meer dan 1 verschilt, wordt een gebalanceerde binaire boom genoemd.

De hierboven getoonde binaire boom is een gebalanceerde binaire boom aangezien de diepte van de twee substructuren van elk knooppunt niet meer is dan 1. AVL-bomen die we in onze volgende tutorials zullen bespreken, zijn een gemeenschappelijke gebalanceerde boom.

Binaire boomweergave

Een binaire boom krijgt op twee manieren geheugen toegewezen.

# 1) Opeenvolgende weergave

Dit is de eenvoudigste techniek om een ​​datastructuur in een boom op te slaan. Een array wordt gebruikt om de boomknooppunten op te slaan. Het aantal knooppunten in een boomstructuur bepaalt de grootte van de array. Het hoofdknooppunt van de boom wordt opgeslagen bij de eerste index in de array.

Over het algemeen geldt dat als een knooppunt is opgeslagen op de i^thlocatie, dan wordt het linker en rechter kind opgeslagen op respectievelijk 2i en 2i + 1 locatie.

Beschouw de volgende binaire structuur.

De opeenvolgende weergave van de bovenstaande binaire boom is als volgt:

In de bovenstaande weergave zien we dat het linker- en rechterkind van elk knooppunt is opgeslagen op respectievelijk locaties 2 * (knooppunt_locatie) en 2 * (knooppunt_locatie) +1.

Bijvoorbeeld, de locatie van knooppunt 3 in de array is 3. Het linkerkind wordt dus op 2 * 3 = 6 geplaatst. Het rechterkind bevindt zich op de locatie 2 * 3 +1 = 7. Zoals we in de array kunnen zien, worden kinderen van de 3 die 6 en 7 zijn, worden op locatie 6 en 7 in de array geplaatst.

De opeenvolgende weergave van de boom is inefficiënt omdat de array die wordt gebruikt om de boomknooppunten op te slaan veel geheugenruimte in beslag neemt. Naarmate de boom groeit, wordt deze weergave inefficiënt en moeilijk te beheren.

Dit nadeel wordt ondervangen door de boomknooppunten op te slaan in een gekoppelde lijst. Merk op dat als de boom leeg is, de eerste locatie waar het hoofdknooppunt is opgeslagen, wordt ingesteld op 0.

# 2) Vertegenwoordiging op een gekoppelde lijst

Bij dit type weergave wordt een gekoppelde lijst gebruikt om de boomknooppunten op te slaan. Verschillende knooppunten zijn verspreid in het geheugen op niet-aangrenzende locaties en de knooppunten zijn verbonden met behulp van de ouder-kindrelatie als een boom.

Het volgende diagram toont een weergave van een gekoppelde lijst voor een boom.

Zoals weergegeven in de bovenstaande weergave, heeft elk knooppunt van een gekoppelde lijst drie componenten:

• Linker wijzer
• Gegevensgedeelte
• Rechter aanwijzer

De linkeraanwijzer heeft een aanwijzer naar het linkerkind van het knooppunt; de rechterpointer heeft een pointer naar het rechterkind van het knooppunt, terwijl het datagedeelte de feitelijke data van het knooppunt bevat. Als er geen kinderen zijn voor een bepaald knooppunt (bladknooppunt), worden de linker- en rechteraanwijzers voor dat knooppunt ingesteld op nul, zoals weergegeven in de bovenstaande afbeelding.

Binaire boomimplementatie in C ++

Vervolgens ontwikkelen we een binair boomprogramma met behulp van een gekoppelde lijstweergave in C ++. We gebruiken een structuur om een ​​enkel knooppunt te declareren en gebruiken vervolgens een klasse om een ​​gekoppelde lijst met knooppunten te ontwikkelen.

Uitgang:

Binaire structuur gemaakt:

5 10 15 20 30 40 45

Binaire Tree Traversal

We hebben traversals al besproken in onze basishandleiding over bomen. Laten we in deze sectie een programma implementeren dat knooppunten in de binaire boom invoegt en ook alle drie de traversals demonstreert, d.w.z. inorder, preorder en postorder, voor een binaire boom.

Uitgang:

In volgorde doorlopen:

A B C D E F G

Postorderverkeer:

G F E D C B A

Doorloop reserveren:

A B C D E F G

Toepassingen van binaire boom

Een binaire boom wordt in veel toepassingen gebruikt voor het opslaan van gegevens.

Enkele van de belangrijke toepassingen van binaire bomen worden hieronder opgesomd:

in functie hoofd ongedefinieerde verwijzing naar

• Binaire zoekbomen: Binaire bomen worden gebruikt om een ​​binaire zoekboom te construeren die in veel zoektoepassingen zoals sets en kaarten in veel taalbibliotheken wordt gebruikt.
• Hash-bomen: Wordt voornamelijk gebruikt om hashes te verifiëren in gespecialiseerde toepassingen voor het ondertekenen van afbeeldingen.
• Hopen: Heaps worden gebruikt voor het implementeren van prioriteitswachtrijen die worden gebruikt voor routers, planningsprocessors in het besturingssysteem, enz.
• Huffman-codering: Huffman-coderingsboom wordt gebruikt in compressie-algoritmen (zoals beeldcompressie) en in cryptografische toepassingen.
• Syntaxisboom: Compilers construeren vaak syntaxisbomen die niets anders zijn dan binaire bomen om uitdrukkingen die in het programma worden gebruikt, te ontleden.

Gevolgtrekking

Binaire bomen zijn veelgebruikte gegevensstructuren in de software-industrie. Binaire bomen zijn de bomen waarvan de knooppunten maximaal twee onderliggende knooppunten hebben. We hebben verschillende soorten binaire bomen gezien zoals een volledige binaire boom, een complete binaire boom, een perfecte binaire boom, een gedegenereerde binaire boom, een gebalanceerde binaire boom, enz.

Binaire boomgegevens kunnen ook worden doorlopen met behulp van inorder-, preorder- en postorder-traversale technieken die we in onze vorige tutorial hebben gezien. In het geheugen kan een binaire boom worden weergegeven met behulp van een gekoppelde lijst (niet-aaneengesloten geheugen) of arrays (sequentiële weergave).

Weergave van gekoppelde lijsten is efficiënter in vergelijking met arrays, omdat arrays veel ruimte in beslag nemen.

​ Bekijk hier de beste C ++ trainingshandleidingen.

Aanbevolen literatuur

• AVL Tree and Heap-gegevensstructuur in C ++
• B Tree en B + Tree gegevensstructuur in C ++
• Wachtrijgegevensstructuur in C ++ met illustratie
• Stapel gegevensstructuur in C ++ met illustratie
• Circulaire gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Gekoppelde lijstgegevensstructuur in C ++ met illustratie
• Inleiding tot gegevensstructuren in C ++
• Prioriteitswachtrijgegevensstructuur in C ++ met illustratie