Zelfstudie over boomgegevensstructuur voor beginners

Invoering

Een boom in software is als een biologische boom, maar met de volgende verschillen:

• Het is ondersteboven getekend.
• Het heeft maar één wortel en geen stengel.
• De takken komen uit de wortel.
• Een punt waar een vertakking van een andere vertakking of de wortel vertrekt, wordt het knooppunt genoemd.
• Elk knooppunt heeft een waarde.

De takken van de softwareboom worden weergegeven door rechte lijnen. Een goed voorbeeld van een softwareboom die je misschien hebt gebruikt, is de mappenboom van de harde schijf van je computer.

Er zijn verschillende soorten bomen. Er is de algemene boom waarvan andere bomen zijn afgeleid. Andere bomen worden afgeleid door beperkingen in de algemene boom te introduceren. U wilt bijvoorbeeld een boom waarin niet meer dan twee takken uit een knoop komen; zo'n boom zou een binaire boom worden genoemd.  Dit artikel beschrijft de algemene boomstructuur en hoe toegang te krijgen tot al zijn knooppunten.

De hyperlink om de code te downloaden staat onderaan dit artikel.

Om de codevoorbeelden in dit artikel te begrijpen, moet u basiskennis hebben van JavaScript (ECMAScript). Als u die kennis niet heeft, kunt u deze verkrijgen via http://www.breed netwerk.com/ChrysanthusForcha-1/ECMAScript-2015-cursus.htm

Het algemene boomdiagram

'A' is het hoofdknooppunt; het is het knooppunt op het eerste niveau. B, C, D staan ​​op de tweede regel; dit zijn knooppunten op het tweede niveau. E, F, G, H, I, J, K bevinden zich op de derde regel en het zijn knooppunten op het derde niveau. Een vierde regel zou knooppunten op het vierde niveau hebben opgeleverd, enzovoort and.

Boomeigenschappen

- Alle takken voor alle niveaus van knooppunten hebben één bron, namelijk het hoofdknooppunt.

- Een boom heeft N - 1 takken, waarbij N het totale aantal knopen is. Het bovenstaande diagram voor de algemene boom heeft 11 knooppunten en 10 takken.

- In tegenstelling tot mensen, waar elk kind twee ouders heeft, heeft bij de softwareboom elk kind slechts één ouder. Het wortelknooppunt is de grootste voorouderouder. Een ouder kan meer dan één kind hebben. Elk knooppunt, behalve het hoofdknooppunt, is een kind.

Boom Woordenschat

• Wortelknooppunt: Dit is het hoogste knooppunt in de boom en heeft geen ouder. Elk ander knooppunt heeft een ouder.
• Blad knooppunten: Een bladknooppunt is een knooppunt dat geen kind heeft. Ze bevinden zich meestal aan de onderkant van de boom en soms aan de linker- en/of rechterkant van de boom.
• Sleutel: Dit is de waarde van een boom. Het kan een getal zijn; het kan een string zijn; het kan zelfs een operator zijn zoals + of - of x.
• Niveaus: Het hoofdknooppunt bevindt zich op het eerste niveau. De kinderen bevinden zich op het tweede niveau; De kinderen van de knooppunten van het tweede niveau bevinden zich op het derde niveau, enzovoort.
• Bovenliggend knooppunt: Elk knooppunt, behalve het hoofdknooppunt, heeft een bovenliggend knooppunt dat ermee verbonden is door een vertakking. Elk knooppunt, behalve het hoofdknooppunt, is een onderliggend knooppunt.
• Broer/zus knooppunten: Broer/zus-knooppunten zijn knooppunten die dezelfde ouder hebben.
• Pad: De takken (rechte lijnen) die het ene knooppunt met het andere verbinden, via andere knooppunten, vormen een pad. De takken kunnen al dan niet pijlen zijn.
• Voorouderknooppunt: Alle hogere knooppunten die met een kind zijn verbonden, inclusief het bovenliggende en het hoofdknooppunt, zijn voorouderknooppunten.
• Nakomeling Knooppunt: Alle lagere knooppunten die zijn verbonden met een knooppunt, tot aan de verbonden bladeren, zijn afstammelingen. De knoop in kwestie maakt geen deel uit van de afstammelingknopen. Het betreffende knooppunt hoeft niet het hoofdknooppunt te zijn.
• Subboom: Een knoop plus al zijn afstammelingen tot aan de verwante bladeren, vormen een subboom. Het startknooppunt is inbegrepen en hoeft niet de root te zijn; anders zou het de hele boom zijn.
• Mate: Het aantal kinderen dat een knoop heeft, wordt de graad van de knoop genoemd.

Alle knooppunten van een boom doorkruisen

Alle knooppunten van een boom zijn toegankelijk om elke waarde van het knooppunt te lezen of te wijzigen. Dit is echter niet willekeurig gedaan. Er zijn drie manieren om dit te doen, die allemaal de volgende diepte-eerste traversal inhouden:

1) In volgorde: Simpel gezegd, in dit schema wordt eerst de linker subboom doorlopen; dan wordt het rootknooppunt benaderd; dan wordt de rechter subboom doorlopen. Dit schema wordt gesymboliseerd als left->root->right. Fig 1 wordt hier opnieuw weergegeven voor gemakkelijke referentie:

Ervan uitgaande dat er twee broers en zussen per knoop zijn; dan betekent left->root->right dat je eerst toegang krijgt tot het laagste en meest linkse knooppunt, dan de ouder van het knooppunt en dan de rechter broer of zus. Als er meer dan twee broers en zussen zijn, neem dan de eerste als de linker en de rest van de rechter knooppunten als de rechter. Voor de algemene boom hierboven is de subboom linksonder toegankelijk om [EBF] te hebben. Dit is een subboom. De ouder van deze subboom is A; dus A wordt vervolgens benaderd om [EBF]A . te hebben. Vervolgens wordt de subboom [GCHI] geopend om een ​​grotere subboom te hebben, [[EBF]A[GCHI]]. Je kunt zien dat het linker->root->rechterprofiel zichzelf uitbeeldt. Deze grote linker subboom heeft de subboom, [JDK] aan de rechterkant om het doorlopen te voltooien, [[EBF]A[GCHI]] [JDK].

2) Vooraf bestellen: Simpel gezegd, in dit schema wordt eerst het hoofdknooppunt benaderd, vervolgens wordt de linker subboom doorlopen en vervolgens de rechter subboom doorkruist. Dit schema wordt gesymboliseerd als root->left->right. Fig 1 wordt hier opnieuw weergegeven voor gemakkelijke referentie easy.

Ervan uitgaande dat er twee broers en zussen per knoop zijn; dan betekent root->left->right dat je eerst de root opent, dan het linker onmiddellijke kind en dan het rechter onmiddellijke kind. Als er meer dan twee broers en zussen zijn, neem dan de eerste als de linker en de rest van de rechter knooppunten als de rechter. Het meest linkse kind van het linkerkind is de volgende die toegankelijk is. Voor de algemene boom hierboven is de root-subboom [ABCD]. Links van deze subboom heb je de subboom, [EF], die de toegangsvolgorde geeft, [ABCD][EF]. Rechts van deze grotere subboom heb je twee substructuren, [GHI] en [JK], die de volledige reeks geven, [ABCD][EF][GHI][JK]. Je kunt het root->links->rechterprofiel zien dat zichzelf uitbeeldt.

3) Na bestelling: Simpel gezegd, in dit schema wordt eerst de linker subboom doorlopen, dan wordt de rechter subboom doorlopen, en dan wordt de root benaderd. Dit schema wordt gesymboliseerd als left->right->root. Fig 1 wordt hier opnieuw weergegeven voor gemakkelijke referentie easy.

Voor deze boom zijn de subbomen [EFB], [GHIC], [JKD] en [A] die de reeks vormen, [EFB], [GHIC], [JKD][A]. Je kunt het linker->rechts->rootprofiel zien dat zichzelf uitbeeldt.

De boom maken

De bovenstaande boom wordt gemaakt met ECMAScript, wat lijkt op de nieuwste versie van JavaScript. Elk knooppunt is een array. Het eerste element van elke knooppuntarray is het bovenliggende element van het knooppunt, een andere array. De rest van de elementen van het knooppunt zijn de kinderen van het knooppunt, beginnend bij het meest linkse kind. Er is een ECMAScript-kaart die elke array relateert aan de bijbehorende string (letter). Het eerste codesegment is: