Käsiteltyjen käsitteiden visuaalinen esitys näkyy alla olevassa kuvassa:
Tämä opas selittää prosessin tulostaa kaikki binääripuun lehtisolmut kattamalla alla mainitut osat:
- Kuinka tunnistaa lehtisolmut?
- Kuinka tulostaa kaikki binaaripuun lehtisolmut vasemmalta oikealle JavaScriptissä?
- Bonusvinkki: Tulosta binaaripuun lehtisolmuja oikealta vasemmalle
- Johtopäätös
Kuinka tunnistaa lehtisolmut?
' puun lehti 'solmut ovat niitä, joilla ei ole lapsisolmuja, tai tarkemmin sanottuna joilla on ' korkeus '/' 0 ”. Jos solmussa on ' korkeus ' suurempi kuin ' 0 ', silloin tämä solmu voi olla sisäsolmu tai juurisolmu. ' puun lehti ”-solmut yleensä jäljitetään, jotta voidaan tunnistaa alkuperäinen lähde, josta tämä solmu on luotu. Sitä käytetään enimmäkseen haku- tai virheenetsintäalgoritmeissa virheen tai ongelman syyn löytämiseksi.
Kuinka tulostaa kaikki binaaripuun lehtisolmut vasemmalta oikealle JavaScriptissä?
On kaksi lähestymistapaa' rekursiivinen ' ja ' iteratiivinen ' valitaksesi kaikki tarjotussa binääripuussa käytettävissä olevat lehtisolmut halutussa ' vasemmalle ”–” oikein ”suuntaan. Näiden lähestymistapojen käytännön toteutus esitetään alla olevissa osioissa:
- Tulosta kaikki binaaripuun lehtisolmut vasemmalta oikealle rekursiivisesti
- Tulosta kaikki binaaripuun lehtisolmut iteratiivisella lähestymistavalla
Tapa 1: Tulosta kaikki binaaripuun lehtisolmut vasemmalta oikealle rekursiivisesti
Rekursiivinen lähestymistapa valitsee kaikki a:n solmut syvyys ensin -hakualgoritmi tavalla, joka ensin kulkee koko vasemmanpuoleisen solmun läpi, sitten keskisolmun ja lopuksi oikeanpuoleiset solmut. Tämä toiminto suoritetaan rekursiivisesti jokaiselle solmulle ja kun ei enää kuljeta ' puun lehti ” solmut tunnistetaan. Ymmärtääksesi paremmin tätä käsitettä, käy alla olevassa koodinpätkässä:
luokkaa Solmu{
rakentaja ( )
{
Tämä . sisältö = 0 ;
Tämä . vasemmalle = tyhjä ;
Tämä . oikein = tyhjä ;
}
} ;
missä LeafNodes näytetään = ( rootNode ) =>
{
jos ( rootNode == tyhjä )
palata ;
jos ( rootNode. vasemmalle == tyhjä && rootNode. oikein == tyhjä )
{
asiakirja. kirjoittaa ( rootNode. sisältö + ' ' ) ;
palata ;
}
jos ( rootNode. vasemmalle != tyhjä )
displayLeafNodes ( rootNode. vasemmalle ) ;
jos ( rootNode. oikein != tyhjä )
displayLeafNodes ( rootNode. oikein ) ;
}
oli sampleNode = ( val ) =>
{
oli tempNode = Uusi Solmu ( ) ;
tempNode. sisältö = val ;
tempNode. vasemmalle = tyhjä ;
tempNode. oikein = tyhjä ;
palata tempNode ;
}
oli rootNode = provNode ( 3 ) ;
rootNode. vasemmalle = provNode ( 6 ) ;
rootNode. oikein = provNode ( 9 ) ;
rootNode. vasemmalle . vasemmalle = provNode ( 12 ) ;
rootNode. vasemmalle . oikein = provNode ( viisitoista ) ;
rootNode. vasemmalle . oikein . oikein = provNode ( 24 ) ;
rootNode. oikein . vasemmalle = provNode ( 18 ) ;
rootNode. oikein . oikein = provNode ( kaksikymmentäyksi ) ;
displayLeafNodes ( rootNode ) ;
Yllä olevan koodilohkon selitys on esitetty alla:
- Luo ensin luokka nimeltä ' solmu ', joka luo uuden solmun ja asettaa sen arvoksi ' 0 ”. Liitteenä oleva ' vasemmalle ' ja ' oikein ' sivusolmut on asetettu ' tyhjä ” oletusarvoisesti luokan rakentajalla.
- Määritä seuraavaksi ' displayLeafNodes() '-toiminto, joka hyväksyy yhden parametrin ' rootNode ”. Tätä parametriarvoa pidetään binääripuun tällä hetkellä valittuna solmuna.
- Toiminnon sisällä ' jos '-lausetta käytetään tarkistamaan, onko ' rootNode ” on tyhjä tai ei. Siinä tapauksessa että ' tyhjä ” jatkosuoritus pysähtyi kyseiselle solmulle. Toisessa tapauksessa rootNode ' vasemmalle ' ja ' oikein ' sivusolmut tarkistetaan ' tyhjä ”. Jos molemmat ovat nolla, sen arvo solmu ” tulostetaan.
- Jos ' vasemmalle ' tai ' oikein ' solmu ei ole 'nolla', siirrä sitten solmun kyseinen puoli ' displayLeafNodes() ”-toiminto rekursiiviselle operaatiolle.
- Määritä uusi funktio nimeltä ' provNode() ', joka hyväksyy '' yhden parametrin val ”. Luo funktion sisällä uusi esiintymä ' Solmu 'luokka nimeltä' tempNode ”. Määritä parametri ' val 'luokan omaisuuden arvona' sisältö ' ja aseta ' vasemmalle ' ja ' oikein ' sivusolmut ' tyhjä ' oletuksena.
- Luo lopuksi objekti nimeltä ' rootNode ' varten ' provNode() ” -funktio ja välitä solmun arvo tämän funktion parametrina. Luo vasemman ja oikean puolen solmut lisäämällä ' vasemmalle ' ja ' oikein ' avainsanoja 'juurisolmulla' ja anna niille arvo samalla funktiolla ' provNode() ”.
- ' vasemmalle ' tarkoittaa juurisolmun vasenta sijaintia ja ' vasen.vasen ”-asento tarkoittaa, että vasen/vasemma samaa lähestymistapaa sovelletaan, kun ” oikein ' ja ' oikein ”
- Kun olet määrittänyt puun, välitä 'rootNode' argumentiksi ' displayLeadNodes() ”-toiminnolla voit valita ja tulostaa luodun puun kaikki lehtisolmut.
Käännöksen jälkeen luotu tulos vahvistaa, että toimitetun puun lehtisolmu on haettu ja tulostettu konsolin kautta:
Tapa 2: Tulosta kaikki binaaripuun lehtisolmut iteratiivisella lähestymistavalla
' iteratiivinen 'lähestymistapa on tehokkain lähestymistapa, se käyttää käsitettä ' työntää ' ja ' pop ' valitaksesi ' puun lehti ”solmut. Tämän lähestymistavan keskeiset kohdat tai toiminta on esitetty alla:
luokkaa Solmu{
rakentaja ( arvo )
{
Tämä . tiedot = arvo ;
Tämä . vasemmalle = tyhjä ;
Tämä . oikein = tyhjä ;
}
} ;
missä LeafNodes näytetään = ( rootNode ) =>
{
jos ( ! rootNode )
palata ;
anna listata = [ ] ;
lista. työntää ( rootNode ) ;
sillä aikaa ( lista. pituus > 0 ) {
rootNode = lista [ lista. pituus - 1 ] ;
lista. pop ( ) ;
jos ( ! rootNode. vasemmalle && ! rootNode. oikein )
asiakirja. kirjoittaa ( rootNode. tiedot + ' ' ) ;
jos ( rootNode. oikein )
lista. työntää ( rootNode. oikein ) ;
jos ( rootNode. vasemmalle )
lista. työntää ( rootNode. vasemmalle ) ;
}
}
oli rootNode = Uusi Solmu ( 3 ) ;
rootNode. vasemmalle = Uusi Solmu ( 6 ) ;
rootNode. oikein = Uusi Solmu ( 9 ) ;
rootNode. vasemmalle . vasemmalle = Uusi Solmu ( 12 ) ;
rootNode. vasemmalle . oikein = Uusi Solmu ( viisitoista ) ;
rootNode. vasemmalle . oikein . oikein = Uusi Solmu ( 24 ) ;
rootNode. oikein . vasemmalle = Uusi Solmu ( 18 ) ;
rootNode. oikein . oikein = Uusi Solmu ( kaksikymmentäyksi ) ;
displayLeafNodes ( rootNode ) ;
Yllä olevan koodin selitys on kirjoitettu alla:
- Luo ensin ' Solmu 'luokka, joka vastaanottaa yhden parametrin' arvo ', joka on asetettu juuri luodun solmun arvoksi, ja vasen ja oikea puoli asetetaan nollaksi. Aivan kuten yllä olevassa esimerkissä.
- Luo seuraavaksi funktio ' displayLeafNodes() ', joka hyväksyy yhden parametrin ' rootNode ”. Tätä 'juurisolmua' pidetään binääripuuna ja sen tyhjyys tarkistetaan ensin.
- Jos solmu ei ole tyhjä, niin tyhjä lista nimeltä ' lista ' luodaan ja ' rootNode ' parametri lisätään siihen käyttämällä ' työntää() ”menetelmä.
- Sitten ' sillä aikaa() ' käytetään, joka suoritetaan '' lista ”. Silmukan sisällä puun pohjassa oleva elementti tai ' lista ' poistetaan käyttämällä ' pop() ”menetelmä.
- Nyt '' vasemmalle ' ja ' oikein 'rootNode'-puolet tarkistetaan, ja jos molempia puolia ei ole, se tarkoittaa, että sillä ei ole lapsisolmua. Sitten tämä solmu näytetään näytöllä ja tunnistetaan lehtisolmuksi.
- Jos vasemmalla tai oikealla puolella on solmu, sillä on lapsia. Sitten tuo ' vasemmalle ' ja ' oikein ' solmu työnnetään ' lista ” lehtisolmun etsimisen jatkotoimenpiteitä varten.
- Luo lopuksi mukautettu binääripuu välittämällä solmuarvot parametreiksi Solmu ”luokan rakentaja. Luomisen jälkeen välitä puu 'rootNode' argumentiksi ' displayLeafNodes() ”-toiminto.
Käännöksen jälkeen luotu tulos osoittaa, että toimitetun puun lehtisolmut on tulostettu:
Bonusvinkki: Tulosta binaaripuun lehtisolmuja oikealta vasemmalle
Voit hakea kaikki lehtisolmut, joissa ei ole lapsisolmuja ' oikein ”–” vasemmalle ” suuntaan, rekursiivinen lähestymistapa on helppokäyttöisyytensä vuoksi suosituin. Esimerkiksi samaa puuta, josta on keskusteltu yllä olevissa osissa, käytetään lehtisolmun hakemiseen, mutta ' oikein ' kohtaan ' vasemmalle '-suuntaan, kuten alla:
luokkaa Solmu{
rakentaja ( arvo )
{
Tämä . tiedot = arvo ;
Tämä . vasemmalle = tyhjä ;
Tämä . oikein = tyhjä ;
}
} ;
toiminto displayLeafNodes ( juuri )
{
jos ( juuri == tyhjä )
{
palata ;
}
jos ( juuri. vasemmalle == tyhjä && juuri. oikein == tyhjä )
{
asiakirja. kirjoittaa ( juuri. tiedot + ' ' ) ;
palata ;
}
jos ( juuri. oikein != tyhjä )
{
displayLeafNodes ( juuri. oikein ) ;
}
jos ( juuri. vasemmalle != tyhjä )
{
displayLeafNodes ( juuri. vasemmalle ) ;
}
}
oli rootNode = Uusi Solmu ( 3 ) ;
rootNode. vasemmalle = Uusi Solmu ( 6 ) ;
rootNode. oikein = Uusi Solmu ( 9 ) ;
rootNode. vasemmalle . vasemmalle = Uusi Solmu ( 12 ) ;
rootNode. vasemmalle . oikein = Uusi Solmu ( viisitoista ) ;
rootNode. vasemmalle . oikein . oikein = Uusi Solmu ( 24 ) ;
rootNode. oikein . vasemmalle = Uusi Solmu ( 18 ) ;
rootNode. oikein . oikein = Uusi Solmu ( kaksikymmentäyksi ) ;
displayLeafNodes ( rootNode ) ;
Yllä mainittu koodi toimii näin:
- Ensin luokka ' Solmu ' luodaan, joka käyttää oletuskonstruktoria uuden solmun lisäämiseen puuhun vain yllä olevissa esimerkeissä tehdyn linkin avulla.
- Seuraavaksi ' displayLeadNodes() ' -toiminto luodaan, joka hyväksyy yhden parametrin ' rootNode ”. Tämä parametri tarkistetaan ' tyhjä ' ehto ' jos ”lausunto.
- Jos annettu solmu ei ole tosi, sen ' vasemmalle ' ja ' oikein ' sivusolmut tarkistetaan ' tyhjä ”ehto. Jos molemmat ovat nolla, solmu tunnistetaan ' puun lehti ”-solmu ja tulostettu verkkosivun päälle.
- Ohita sen jälkeen ' oikein ' ja ' vasemmalle ' solmut ' rootNode ' kohtaan ' displayLeafNodes() ”-toiminto.
- Varaa kunkin solmun sijainti luomalla esiintymät käyttämällä ' Uusi 'avainsana ja ' Solmu() ” konstruktori ja määrittämällä paikan konstruktoriparametriksi.
- ' vasemmalle ' tarkoittaa juurisolmun vasenta sijaintia ja ' vasen.vasen ”-asento tarkoittaa vasenta tai vasenta. Samaa lähestymistapaa sovelletaan ' oikein ' ja ' oikein ”.
- Ohita lopuksi ' rootNode 'argumenttina' displayLeafNode() ”-toiminto.
Luotu tulos osoittaa, että lehtisolmut tulostetaan oikealta vasemmalle.
Siinä on kyse binääripuun kaikkien lehtisolmujen tulostamisesta mihin tahansa haluttuun suuntaan.
Johtopäätös
Jos haluat tulostaa binääripuun kaikki lehtisolmut, luo satunnainen luokka, joka luo ja määrittää arvot puun solmuille. Luo seuraavaksi satunnainen funktio, joka hyväksyy puun yhden solmun ylhäältä alas -hierarkiassa. Tämä toiminto sisältää useita ' jos 'olosuhteet, jotka tarkistavat, onko ' solmu ' ei ole tyhjä eikä siinä ole solmuja ' vasemmalle ' ja ' oikein ' suuntaan, niin kyseistä solmua pidetään ' puun lehti ”-solmu ja näkyy konsolissa. Tässä oppaassa on selostettu binääripuun kaikkien lehtisolmujen tulostaminen vasemmalta oikealle tai oikealta vasemmalle.