advertenties

boom vertegenwoordigt de knooppunten verbonden door randen. We zullen binaire boom of binaire zoek boom specifiek bespreken.

Binary Tree is een speciale datastructuur die wordt gebruikt voor gegevensopslag. Een binaire boom heeft een speciale voorwaarde dat elk knooppunt maximaal twee kinderen kan hebben., Een binaire boom heeft de voordelen van zowel een geordende array en een gekoppelde lijst als zoeken is zo snel als in een gesorteerde array en invoegen of verwijderen operatie zijn zo snel als in gekoppelde lijst.

belangrijke termen

Hieronder volgen de belangrijke termen met betrekking tot de boom.

  • pad-pad verwijst naar de reeks knopen langs de randen van een boom.

  • Root-het knooppunt aan de bovenkant van de boom wordt root genoemd. Er is slechts één root per tree en één pad van de root node naar een node.,

  • Parent – elke node behalve de root node heeft een rand naar boven naar een node genaamd parent.

  • Child – het knooppunt onder een gegeven knooppunt dat verbonden is door de rand naar beneden wordt zijn dochterknooppunt genoemd.

  • blad-de knoop die geen onderliggende knoop heeft wordt de bladknoop genoemd.

  • Subtree-Subtree vertegenwoordigt de afstammelingen van een knoop.

  • bezoeken-bezoeken verwijst naar het controleren van de waarde van een knooppunt wanneer controle op het knooppunt is.

  • doorkruisen-doorkruisen betekent door knopen in een specifieke volgorde.,

  • niveaus – niveau van een knooppunt vertegenwoordigt het genereren van een knooppunt. Als de root node op niveau 0 is, dan is zijn volgende kind node op niveau 1, zijn kleinkind is op niveau 2, enzovoort.

  • keys-Key representeert een waarde van een knooppunt op basis waarvan een zoekopdracht voor een knooppunt moet worden uitgevoerd.

binaire Zoekboomrepresentatie

binaire zoekboom vertoont een speciaal gedrag. Het linker kind van een knooppunt moet een waarde hebben die kleiner is dan de waarde van de ouder en het rechter kind van het knooppunt moet een waarde hebben die groter is dan de waarde van de ouder.,

We gaan boomstructuur implementeren met behulp van knooppuntobject en ze verbinden door middel van referenties.

Tree Node

de code om een tree node te schrijven zou vergelijkbaar zijn met wat hieronder wordt gegeven. Het heeft een data deel en verwijzingen naar de linker en rechter kind knooppunten.

struct node { int data; struct node *leftChild; struct node *rightChild;};

In een boomstructuur hebben alle knopen een gemeenschappelijke constructie.

BST basisbewerkingen

de basisbewerkingen die kunnen worden uitgevoerd op een binaire zoekboomgegevensstructuur, zijn de volgende –

  • Insert − voegt een element in een boomstructuur in / Maak een boomstructuur aan.,

  • zoeken-Zoekt Een element in een boomstructuur.

  • pre-order Traversal-doorkruist een boom op een pre-order manier.

  • in volgorde – doorkruist een boom op een in-volgorde manier.

  • Postordertraversal-doorkruist een boom op een post-order manier.

We zullen leren het maken (invoegen in) van een boomstructuur en het zoeken naar een gegevensitem in een boom in dit hoofdstuk. We zullen in het komende hoofdstuk Meer leren over de methoden om bomen te doorkruisen.

Insert operatie

de allereerste insertie maakt de boomstructuur., Daarna, wanneer een element moet worden ingevoegd, zoek eerst de juiste locatie. Begin met zoeken vanuit het root-knooppunt, en als de gegevens kleiner zijn dan de sleutelwaarde, zoek dan naar de lege locatie in de linker subboom en voeg de gegevens in. Zoek anders naar de lege locatie in de rechter subboom en voeg de gegevens in.,

algoritme

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

implementatie

de implementatie van insert −functie moet er zo uitzien –

zoekopdracht

wanneer een element moet worden doorzocht, begin dan met zoeken vanaf het root-knooppunt, en als de gegevens kleiner zijn dan de sleutelwaarde, zoek dan naar het element in de linker subboom. Zoek anders naar het element in de rechter subboom. Volg hetzelfde algoritme voor elk knooppunt.

algoritme

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

de implementatie van dit algoritme moet er zo uitzien.,

om meer te weten te komen over de implementatie van de gegevensstructuur van de binaire zoekboom, Klik hier.

advertenties

0