trees c basic terminology
In deze diepgaande zelfstudie over C ++ -bomen worden boomsoorten, technieken voor het doorlopen van bomen en basisterminologie uitgelegd met afbeeldingen en voorbeeldprogramma's:
In deze C ++ -serie hebben we tot nu toe de lineaire gegevensstructuur van zowel statische als dynamische aard gezien. Nu gaan we verder met de niet-lineaire datastructuur. De eerste datastructuur in deze categorie is 'Bomen'.
Bomen zijn niet-lineaire hiërarchische gegevensstructuren. Een boom is een verzameling knooppunten die met elkaar zijn verbonden door middel van 'randen' die al dan niet gericht zijn. Een van de knooppunten wordt aangeduid als 'Hoofdknooppunt' en de overige knooppunten worden kindknooppunten of de bladknooppunten van het hoofdknooppunt genoemd.
In het algemeen kan elk knooppunt evenveel kinderen hebben, maar slechts één bovenliggend knooppunt.
Bekijk de volledige C ++ trainingsserie
Knooppunten van een boom bevinden zich op hetzelfde niveau als zusterknooppunten of ze kunnen een ouder-kindrelatie hebben. Knooppunten met dezelfde ouder zijn knooppunten op hetzelfde niveau.
Wat je leert:
Bomen in C ++
Hieronder ziet u een voorbeeldboom met zijn verschillende onderdelen.
Laten we eens kijken naar de definities van enkele basistermen die we voor bomen gebruiken.
- Root-knooppunt: Dit is het bovenste knooppunt in de boomhiërarchie. In het bovenstaande diagram is knooppunt A het hoofdknooppunt. Merk op dat het hoofdknooppunt geen ouder heeft.
- Leaf node: Het is het onderste knooppunt in een boomhiërarchie. Bladknooppunten zijn de knooppunten die geen onderliggende knooppunten hebben. Ze worden ook wel externe knooppunten genoemd. Knooppunten E, F, G, H en C in de bovenstaande boom zijn allemaal bladknooppunten.
- Subboom: Subtree vertegenwoordigt verschillende afstammelingen van een knoop wanneer de root niet nul is. Een boom bestaat meestal uit een wortelknooppunt en een of meer substructuren. In het bovenstaande diagram zijn (B-E, B-F) en (D-G, D-H) substructuren.
- Bovenliggend knooppunt: Elk knooppunt behalve het hoofdknooppunt dat een kindknooppunt heeft en een rand naar boven naar het bovenliggende knooppunt.
- Voorouder knooppunt: Het is een voorgangerknooppunt op een pad van de root naar dat knooppunt. Merk op dat de wortel geen voorouders heeft. In het bovenstaande diagram zijn A en B de voorouders van E.
- Sleutel: Het vertegenwoordigt de waarde van een knooppunt.
- Niveau: Staat voor het genereren van een knooppunt. Een hoofdknooppunt bevindt zich altijd op niveau 1. Kindknooppunten van de wortel bevinden zich op niveau 2, kleinkinderen van de wortel bevinden zich op niveau 3 enzovoort. Over het algemeen bevindt elk knooppunt zich op een hoger niveau dan het bovenliggende niveau.
- Pad: Het pad is een opeenvolging van opeenvolgende randen. In het bovenstaande diagram is het pad naar E A => B-> E.
- Mate: De graad van een knooppunt geeft het aantal kinderen aan dat een knooppunt heeft. In het bovenstaande diagram is de graad van B en D elk 2, terwijl de graad van C 0 is.
Soorten C ++ -bomen
De datastructuur van de boom kan in de volgende subtypen worden ingedeeld, zoals weergegeven in het onderstaande diagram.
# 1) Algemene boom
De algemene boom is de basisweergave van een boom. Het heeft een knooppunt en een of meer onderliggende knooppunten. Het knooppunt op het hoogste niveau, d.w.z. het hoofdknooppunt, is aanwezig op niveau 1 en alle andere knooppunten kunnen op verschillende niveaus aanwezig zijn.
Een algemene boom wordt getoond in de onderstaande afbeelding.
Zoals weergegeven in de bovenstaande afbeelding, kan een algemene boom een willekeurig aantal substructuren bevatten. De knooppunten B, C en D zijn aanwezig op niveau 2 en zijn knooppunten op hetzelfde niveau. Evenzo zijn knooppunten E, F, G en H ook knooppunten op hetzelfde niveau.
De knooppunten die op verschillende niveaus aanwezig zijn, kunnen een ouder-kindrelatie vertonen. In de bovenstaande afbeelding zijn knooppunten B, C en D kinderen van A. Knooppunten E en F zijn kinderen van B, terwijl knooppunten G en H kinderen zijn van D.
De algemene structuur wordt hieronder gedemonstreerd met behulp van de C ++ -implementatie:
Uitgang:
De gemaakte algemene boom is als volgt:
10
hoe .jar-bestanden worden afgespeeld
20 30
40
# 2) Bossen
Telkens wanneer we het rootknooppunt uit de boom verwijderen en de randen die de elementen van het volgende niveau en de wortel verbinden, krijgen we onsamenhangende sets van bomen zoals hieronder getoond.
In de bovenstaande afbeelding hebben we twee bossen verkregen door het hoofdknooppunt A en de drie randen te verwijderen die het hoofdknooppunt met knooppunten B, C en D verbinden.
# 3) Binaire boom
Een datastructuur van een boom waarin elk knooppunt maximaal twee onderliggende knooppunten heeft, wordt een binaire boom genoemd. Een binaire boom is de meest populaire datastructuur van een boom en wordt gebruikt in een reeks toepassingen zoals evaluatie van uitdrukkingen, databases, enz.
De volgende afbeelding toont een binaire boom.
In de bovenstaande afbeelding zien we dat knooppunten A, B en D elk twee kinderen hebben. Een binaire boom waarin elk knooppunt precies nul of twee kinderen heeft, wordt een volledige binaire boom genoemd. In deze boom zijn er geen knooppunten die één kind hebben.
Een complete binaire boom heeft een binaire boom die volledig is gevuld met uitzondering van het laagste niveau dat van links naar rechts wordt gevuld. De hierboven getoonde binaire boom is een volledige binaire boom.
Hieronder volgt een eenvoudig programma om een binaire boom te demonstreren. Merk op dat de uitvoer van de boom de volgorde van de doorloop van de invoerboom is.
Uitgang:
wat is het besturingssysteem op de computer
Binaire structuur gemaakt:
5 10 15 20 30 40 45
# 4) Binaire zoekboom
De binaire boom die is geordend, wordt de binaire zoekboom genoemd. In een binaire zoekboom zijn de knooppunten aan de linkerkant kleiner dan het hoofdknooppunt, terwijl de knooppunten aan de rechterkant groter zijn dan of gelijk zijn aan het hoofdknooppunt.
Een voorbeeld van een binaire zoekboom wordt hieronder getoond.
In de bovenstaande afbeelding kunnen we zien dat de linkerknooppunten allemaal kleiner zijn dan 20, wat het wortelelement is. De rechterknooppunten zijn daarentegen groter dan het hoofdknooppunt. De binaire zoekboom wordt gebruikt bij zoek- en sorteertechnieken.
# 5) Uitdrukkingsboom
Een binaire boom die wordt gebruikt om eenvoudige rekenkundige uitdrukkingen te evalueren, wordt een uitdrukkingsboom genoemd.
Een eenvoudige uitdrukkingsboom wordt hieronder getoond.
In de bovenstaande voorbeelduitdrukkingsboom vertegenwoordigen we de uitdrukking (a + b) / (a-b). Zoals weergegeven in de bovenstaande afbeelding, vertegenwoordigen de niet-bladknooppunten van de boom de operatoren van de uitdrukking, terwijl de bladknooppunten de operanden vertegenwoordigen.
Uitdrukkingsbomen worden voornamelijk gebruikt om algebraïsche uitdrukkingen op te lossen.
Tree Traversal Technieken
We hebben lineaire datastructuren gezien zoals arrays, gekoppelde lijsten, stapels, wachtrijen, enz. Al deze datastructuren hebben een gemeenschappelijke traversietechniek die de structuur slechts op één manier doorloopt, d.w.z. lineair.
Maar in het geval van bomen hebben we verschillende doorgangstechnieken, zoals hieronder vermeld:
# 1) In volgorde: Bij deze traversale techniek doorlopen we eerst de linker substructuur totdat er geen knooppunten meer zijn in de linker substructuur. Hierna bezoeken we het hoofdknooppunt en gaan dan verder met het doorlopen van de rechter substructuur totdat er geen knooppunten meer zijn om te doorlopen in de rechter substructuur. De volgorde van inOrder traversal is dus left-> root-> right.
# 2) Pre-order: Voor de pre-order traversale techniek verwerken we eerst de root node, dan doorlopen we de gehele linker substructuur en tenslotte doorlopen we de rechter substructuur. Daarom is de volgorde van preorder traversal root-> left-> right.
# 3) Nabestelling: Bij de post-order traversal-techniek doorlopen we de linker substructuur, dan de rechter substructuur en tenslotte het root-knooppunt. De volgorde van doorlopen voor de postordertechniek is left-> right-> root.
Als n het hoofdknooppunt is en ‘l’ en ’r’ respectievelijk de linker- en rechterknooppunten van de boom zijn, zijn de algoritmen voor het doorlopen van bomen als volgt:
In volgorde (lnr) algoritme:
- Beweeg de linker substructuur met inOrder (left-subboom).
- Bezoek het hoofdknooppunt (n).
- Beweeg de rechter substructuur met inOrder (rechts-substructuur).
Preorder (nlr) algoritme:
- Bezoek het hoofdknooppunt (n).
- Beweeg de linker substructuur met preorder (left-substree).
- Doorloop de rechter substructuur met preorder (rechter substructuur).
Postorder (lrn) algoritme:
- Beweeg de linker substructuur met postOrder (left-substree).
- Doorloop de rechter substructuur met postOrder (rechter substructuur).
- Bezoek het hoofdknooppunt (n).
Uit de bovenstaande algoritmen van traversale technieken zien we dat de technieken op een bepaalde boom recursief kunnen worden toegepast om het gewenste resultaat te krijgen.
Beschouw de volgende boom.
Met behulp van de bovenstaande doorgangstechnieken wordt de doorloopvolgorde voor de bovenstaande boom hieronder weergegeven:
- InOrder traversal: 2 3 5 6 10
- PreOrder traversal: 6 3 2 5 10
- PostOrder traversal: 2 5 3 10 6
Gevolgtrekking
Bomen zijn een niet-lineaire hiërarchische datastructuur die in veel toepassingen op softwaregebied wordt gebruikt.
In tegenstelling tot lineaire datastructuren die maar één manier hebben om de lijst te doorlopen, kunnen we bomen op verschillende manieren doorkruisen. We hebben in deze tutorial een gedetailleerde studie van traversale technieken en de verschillende soorten bomen gehad.
Bekijk hier de C ++ Beginnersgids
Aanbevolen literatuur
- B Tree en B + Tree gegevensstructuur in C ++
- Binaire boomgegevensstructuur in C ++
- Soorten risico's in softwareprojecten
- AVL Tree and Heap-gegevensstructuur in C ++
- Python-gegevenstypen
- 20 eenvoudige vragen om de basiskennis van uw software te testen (online quiz)
- C ++ gegevenstypen
- Basis invoer- / uitvoerbewerkingen in C ++