De visuele weergave van de besproken concepten wordt weergegeven in de onderstaande figuur:
Deze gids legt het proces uit van het afdrukken van alle bladknooppunten van een binaire boom door de onderstaande secties te behandelen:
- Hoe bladknooppunten identificeren?
- Hoe print ik alle bladknooppunten van een binaire boom van links naar rechts in JavaScript?
- Bonustip: bladknooppunten van een binaire boom van rechts naar links afdrukken
- Conclusie
Hoe bladknooppunten identificeren?
De ' blad 'knooppunten zijn degenen die geen onderliggende knooppunten hebben, of om specifieker te zijn, die de' hoogte ' van ' 0 ”. Als het knooppunt een “ hoogte ' groter dan ' 0 ', dan kan dat knooppunt het binnenknooppunt of het hoofdknooppunt zijn. De ' blad Knooppunten worden meestal teruggevonden om de oorspronkelijke bron te identificeren van waaruit dit knooppunt is gegenereerd. Het wordt meestal gebruikt bij zoek- of foutopsporingsalgoritmen om de oorzaak van een fout of probleem te vinden.
Hoe print ik alle bladknooppunten van een binaire boom van links naar rechts in JavaScript?
Er zijn twee benaderingen “ recursief ' En ' iteratief ” om alle leaf-knooppunten te selecteren die beschikbaar zijn in de opgegeven binaire boom in de gewenste “ links ' naar ' rechts richting. De praktische implementatie van deze benaderingen wordt gedemonstreerd in de onderstaande paragrafen:
- Druk alle bladknooppunten van een binaire boom recursief van links naar rechts af
- Druk alle bladknooppunten van een binaire boom af met behulp van de iteratieve aanpak
Methode 1: Druk alle bladknooppunten van een binaire boom recursief van links naar rechts af
De recursieve benadering selecteert alle knooppunten in a diepte-eerst zoekalgoritme manier die eerst de gehele linkerknooppunten doorkruist, vervolgens het middelste knooppunt en uiteindelijk de rechterknooppunten. Deze bewerking wordt recursief uitgevoerd voor elk knooppunt en wanneer er geen verdere doorkruising van de “ blad Knooppunten worden geïdentificeerd. Om dit concept beter te begrijpen, bezoekt u het onderstaande codefragment:
klas Knooppunt{
bouwer ( )
{
dit . inhoud = 0 ;
dit . links = nul ;
dit . rechts = nul ;
}
} ;
waar displayLeafNodes = ( rootNode ) =>
{
als ( rootNode == nul )
opbrengst ;
als ( rootNode. links == nul && rootNode. rechts == nul )
{
document. schrijven ( rootNode. inhoud + ' ' ) ;
opbrengst ;
}
als ( rootNode. links != nul )
displayLeafNodes ( rootNode. links ) ;
als ( rootNode. rechts != nul )
displayLeafNodes ( rootNode. rechts ) ;
}
was sampleNode = ( val ) =>
{
was tempNode = nieuw Knooppunt ( ) ;
tempNode. inhoud = val ;
tempNode. links = nul ;
tempNode. rechts = nul ;
opbrengst tempNode ;
}
was rootNode = provNode ( 3 ) ;
rootNode. links = provNode ( 6 ) ;
rootNode. rechts = provNode ( 9 ) ;
rootNode. links . links = provNode ( 12 ) ;
rootNode. links . rechts = provNode ( vijftien ) ;
rootNode. links . rechts . rechts = provNode ( 24 ) ;
rootNode. rechts . links = provNode ( 18 ) ;
rootNode. rechts . rechts = provNode ( eenentwintig ) ;
displayLeafNodes ( rootNode ) ;
De uitleg van het bovenstaande codeblok staat hieronder:
- Maak eerst een klasse met de naam “ knooppunt ”, dat een nieuw knooppunt creëert en de waarde ervan instelt op “ 0 ”. Het bijgevoegde “ links ' En ' rechts ' zijknooppunten zijn ingesteld op ' nul ” standaard met behulp van de klassenconstructor.
- Definieer vervolgens een “ displayLeafNodes() ”-functie die een enkele parameter van “ accepteert rootNode ”. Deze parameterwaarde wordt beschouwd als het momenteel geselecteerde knooppunt van een binaire boom.
- Binnen de functie wordt de “ als ”-verklaring wordt gebruikt om te controleren of de “ rootNode 'is nul of niet. In het geval van ' nul ”de verdere uitvoering stopte voor dat knooppunt. In het andere geval is de rootNode “ links ' En ' rechts 'zijknooppunten worden gecontroleerd op' nul ”. Als beide nul zijn, is de waarde daarvan “ knooppunt ” wordt afgedrukt.
- Als de “ links ' of ' rechts 'knooppunt niet 'null' is, geef dan die kant van het knooppunt door aan de ' displayLeafNodes() ”-functie voor de recursieve bewerking.
- Definieer een nieuwe functie met de naam “ provNode() ” die de enkele parameter van “ accepteert val ”. Maak binnen de functie een nieuw exemplaar van de “ Knooppunt 'klasse genaamd' tempNode ”. Wijs de parameter “ val ” als de waarde voor klasse-eigenschap “ inhoud ' en stel de ' links ' En ' rechts ” zijknooppunten naar “ nul ' standaard.
- Maak ten slotte een object met de naam “ rootNode ' voor de ' provNode() 'functie en geef de knooppuntwaarde door als deze functieparameter. Maak de linker- en rechterknooppunten door de “ links ' En ' rechts ” trefwoorden met de “rootNode” en wijs er waarde aan toe met dezelfde functie “ provNode() ”.
- De ' links ” betekent de linkerpositie van het hoofdknooppunt en de “ links links ” positie betekent links van links dezelfde benadering wordt toegepast in het geval van “ rechts ' En ' rechts ”
- Na het definiëren van de boom geeft u de “rootNode” door als argument voor de “ displayLeadNodes() '-functie om alle bladknooppunten van de gemaakte boom te selecteren en af te drukken.
De uitvoer die na de compilatie wordt gegenereerd, bevestigt dat het bladknooppunt van de opgegeven boom is opgehaald en via de console is afgedrukt:
Methode 2: Druk alle bladknooppunten van een binaire boom af met behulp van de iteratieve aanpak
De ' iteratief ' aanpak is de meest efficiënte aanpak, het maakt gebruik van het concept van ' duw ' En ' knal ” om de “ blad knooppunten. De belangrijkste punten of werking van deze aanpak worden hieronder vermeld:
klas Knooppunt{
bouwer ( waarde )
{
dit . gegevens = waarde ;
dit . links = nul ;
dit . rechts = nul ;
}
} ;
waar displayLeafNodes = ( rootNode ) =>
{
als ( ! rootNode )
opbrengst ;
laten lijst = [ ] ;
lijst. duw ( rootNode ) ;
terwijl ( lijst. lengte > 0 ) {
rootNode = lijst [ lijst. lengte - 1 ] ;
lijst. knal ( ) ;
als ( ! rootNode. links && ! rootNode. rechts )
document. schrijven ( rootNode. gegevens + ' ' ) ;
als ( rootNode. rechts )
lijst. duw ( rootNode. rechts ) ;
als ( rootNode. links )
lijst. duw ( rootNode. links ) ;
}
}
was rootNode = nieuw Knooppunt ( 3 ) ;
rootNode. links = nieuw Knooppunt ( 6 ) ;
rootNode. rechts = nieuw Knooppunt ( 9 ) ;
rootNode. links . links = nieuw Knooppunt ( 12 ) ;
rootNode. links . rechts = nieuw Knooppunt ( vijftien ) ;
rootNode. links . rechts . rechts = nieuw Knooppunt ( 24 ) ;
rootNode. rechts . links = nieuw Knooppunt ( 18 ) ;
rootNode. rechts . rechts = nieuw Knooppunt ( eenentwintig ) ;
displayLeafNodes ( rootNode ) ;
De uitleg van de bovenstaande code staat hieronder:
- Maak eerst een “ Knooppunt ” klasse die een enkele parameter ontvangt “ waarde ', die is ingesteld als de waarde van het nieuw gemaakte knooppunt, en de linker- en rechterkant zijn ingesteld op nul. Net zoals gedaan in het bovenstaande voorbeeld.
- Maak vervolgens een functie “ displayLeafNodes() ” die een enkele parameter accepteert van “ rootNode ”. Deze “rootNode” wordt beschouwd als de binaire boom en de leegte ervan wordt eerst gecontroleerd.
- Als het knooppunt niet leeg is, verschijnt er een lege lijst met de naam “ lijst ” is gemaakt en de “ rootNode ' parameter wordt erin ingevoegd met behulp van de ' duw() methode.
- Dan de ' terwijl() ” wordt gebruikt en wordt uitgevoerd tot de lengte van een “ lijst ”. Binnen de lus, het element dat zich onderaan een boom bevindt of “ lijst ” wordt verwijderd met behulp van de “ knal() methode.
- Nu is het bestaan van de “ links ' En ' rechts ' zijden van 'rootNode' is aangevinkt, en als beide zijden niet bestaan, betekent dit dat er geen onderliggend knooppunt is. Vervolgens wordt dit knooppunt op het scherm weergegeven en geïdentificeerd als een bladknooppunt.
- Als er een knooppunt aan de linker- of rechterkant is, betekent dit dat er kinderen zijn. Dan dat ' links ' En ' rechts ' knooppunt wordt in de ' lijst ” voor verdere werking van het vinden van het bladknooppunt.
- Maak uiteindelijk een aangepaste binaire boom door de knooppuntwaarden door te geven als parameters voor de “ Knooppunt 'klasse-constructor. Geef na het maken de boom “rootNode” door als argument voor de “ displayLeafNodes() ” functie.
De uitvoer die na de compilatie wordt gegenereerd, laat zien dat de bladknooppunten van de opgegeven boom worden afgedrukt:
Bonustip: bladknooppunten van een binaire boom van rechts naar links afdrukken
Om alle leaf-knooppunten op te halen die geen onderliggende knooppunten hebben in de “ rechts ' naar ' links ”richting, wordt de recursieve benadering het meest aanbevolen vanwege het gemak ervan. Dezelfde boom die in de bovenstaande paragrafen is besproken, zal bijvoorbeeld worden gebruikt om het bladknooppunt op te halen, maar dan in de “ rechts ' naar de ' links richting, zoals hieronder weergegeven:
klas Knooppunt{
bouwer ( waarde )
{
dit . gegevens = waarde ;
dit . links = nul ;
dit . rechts = nul ;
}
} ;
functieweergaveLeafNodes ( wortel )
{
als ( wortel == nul )
{
opbrengst ;
}
als ( wortel. links == nul && wortel. rechts == nul )
{
document. schrijven ( wortel. gegevens + ' ' ) ;
opbrengst ;
}
als ( wortel. rechts != nul )
{
displayLeafNodes ( wortel. rechts ) ;
}
als ( wortel. links != nul )
{
displayLeafNodes ( wortel. links ) ;
}
}
was rootNode = nieuw Knooppunt ( 3 ) ;
rootNode. links = nieuw Knooppunt ( 6 ) ;
rootNode. rechts = nieuw Knooppunt ( 9 ) ;
rootNode. links . links = nieuw Knooppunt ( 12 ) ;
rootNode. links . rechts = nieuw Knooppunt ( vijftien ) ;
rootNode. links . rechts . rechts = nieuw Knooppunt ( 24 ) ;
rootNode. rechts . links = nieuw Knooppunt ( 18 ) ;
rootNode. rechts . rechts = nieuw Knooppunt ( eenentwintig ) ;
displayLeafNodes ( rootNode ) ;
De bovengenoemde code werkt als volgt:
- Eerst de klasse “ Knooppunt ” is gemaakt die de standaardconstructor gebruikt om een nieuw knooppunt in de boom toe te voegen, alleen de link die in de bovenstaande voorbeelden is gedaan.
- Vervolgens wordt de “ displayLeadNodes() Er wordt een functie gemaakt die een enkele parameter van “ rootNode ”. Deze parameter wordt gecontroleerd op de “ nul ” voorwaarde via de “ als ' stelling.
- Als het opgegeven knooppunt niet waar is, dan is het “ links ' En ' rechts 'zijknooppunten worden gecontroleerd op' nul ' voorwaarde. Als beide nul zijn, wordt het knooppunt geïdentificeerd als een “ blad 'knooppunt en afgedrukt over de webpagina.
- Geef daarna de “ rechts ' En ' links ” knooppunten van de “ rootNode ' naar de ' displayLeafNodes() ” functie.
- Wijs de positie van elk knooppunt toe door de instanties te maken met behulp van de “ nieuw 'zoekwoord en de' Knooppunt() 'constructor en specificeer de positie als de constructorparameter.
- De ' links ” betekent de linkerpositie van het hoofdknooppunt en de “ links links 'positie betekent links of links. Dezelfde aanpak wordt toegepast in het geval van “ rechts ' En ' rechts ”.
- Geef ten slotte de “ rootNode ” als argument voor de “ displayLeafNode() ” functie.
De gegenereerde uitvoer laat zien dat bladknooppunten van rechts naar links worden afgedrukt.
Dat gaat allemaal over het afdrukken van alle bladknooppunten van een binaire boom in elke gewenste richting.
Conclusie
Om alle bladknooppunten van een binaire boom af te drukken, maakt u een willekeurige klasse die waarden creëert en toewijst aan de boomknooppunten. Maak vervolgens een willekeurige functie die een enkel knooppunt van de boom in een hiërarchie van boven naar beneden accepteert. Deze functie bevat meerdere “ als ” voorwaarden die controleren of de “ knooppunt ' is niet leeg en heeft geen knooppunten in de ' links ' En ' rechts ' richting, dan wordt dat knooppunt beschouwd als een ' blad 'knooppunt en wordt weergegeven op de console. In deze handleiding wordt de procedure uitgelegd voor het afdrukken van alle bladknooppunten van een binaire boom, van links naar rechts of van rechts naar links.