Kako natisniti vsa listna vozlišča binarnega drevesa od leve proti desni v JavaScriptu?

Vizualna predstavitev obravnavanih konceptov je prikazana na spodnji sliki:

Ta vodnik razlaga postopek tiskanja vseh listnih vozlišč binarnega drevesa tako, da pokriva spodnje razdelke:

• Kako prepoznati listne vozle?
• Kako natisniti vsa listna vozlišča binarnega drevesa od leve proti desni v JavaScriptu?
• Dodatni nasvet: Tiskanje listnih vozlišč binarnega drevesa od desne proti levi
• Zaključek

Kako prepoznati listne vozle?

' list ' vozlišča so tista, ki nimajo podrejenih vozlišč, ali če smo natančni, ki imajo ' višina ” od “ 0 ”. Če ima vozlišče ' višina ' večji kot ' 0 ” potem je to vozlišče lahko notranje vozlišče ali korensko vozlišče. ' list ” Vozlišča se običajno vrnejo nazaj, da identificirajo izvirni vir, iz katerega je to vozlišče ustvarjeno. Večinoma se uporablja pri algoritmih iskanja ali odkrivanja napak za iskanje vzroka napake ali težave.

Kako natisniti vsa listna vozlišča binarnega drevesa od leve proti desni v JavaScriptu?

Obstajata dva pristopa' rekurzivno « in » iterativno ', da izberete vsa listna vozlišča, ki so na voljo v podanem binarnem drevesu v želenem ' levo ' do ' prav ” smer. Praktična izvedba teh pristopov je prikazana v spodnjih razdelkih:

• Rekurzivno natisnite vsa listna vozlišča binarnega drevesa od leve proti desni
• Natisnite vsa listna vozlišča binarnega drevesa z uporabo iterativnega pristopa

1. način: Rekurzivno natisnite vsa listna vozlišča binarnega drevesa od leve proti desni

Rekurzivni pristop izbere vsa vozlišča v a algoritem iskanja v globino način, ki najprej prečka celotna leva stranska vozlišča, nato srednje vozlišče in na koncu desna stranska vozlišča. Ta operacija se izvaja rekurzivno za vsako vozlišče in ko ni nadaljnjega prečkanja ' list ” so vozlišča identificirana. Če želite bolje razumeti ta koncept, obiščite spodnji delček kode:

Razlaga zgornjega kodnega bloka je navedena spodaj:

• Najprej ustvarite razred z imenom ' vozlišče «, ki ustvari novo vozlišče in nastavi njegovo vrednost na » 0 ”. Priloženo ' levo « in » prav » stranska vozlišča so nastavljena na » nič ” privzeto z uporabo konstruktorja razreda.
• Nato določite » displayLeafNodes() ' funkcija, ki sprejme en sam parameter ' rootNode ”. Ta parametrska vrednost se obravnava kot trenutno izbrano vozlišče binarnega drevesa.
• Znotraj funkcije je » če ” se uporablja za preverjanje, ali je rootNode ” je nična ali ne. V primeru ' nič ” se je nadaljnje izvajanje za to vozlišče ustavilo. V drugem primeru je korensko vozlišče ' levo « in » prav ” stranska vozlišča so preverjena za ” nič ”. Če sta obe ničelni, je vrednost tega ' vozlišče ” se natisne.
• Če je ' levo « ali » prav « vozlišče ni »ničelno«, nato to stran vozlišča prenesite v » displayLeafNodes() ” za rekurzivno operacijo.
• Definirajte novo funkcijo z imenom ' provNode() «, ki sprejme en sam parameter » val ”. Znotraj funkcije ustvarite nov primerek » Vozlišče ' razred z imenom ' tempNode ”. Dodelite parameter ' val ' kot vrednost za lastnost razreda ' vsebino « in nastavite » levo « in » prav »stranska vozlišča do« nič ' privzeto.
• Končno ustvarite objekt z imenom ' rootNode ' za ' provNode() ” in posredujte vrednost vozlišča kot ta parameter funkcije. Ustvarite levo in desno stransko vozlišče tako, da dodate ' levo « in » prav ' ključne besede z 'rootNode' in jim dodelite vrednost z isto funkcijo ' provNode() ”.
• ' levo « pomeni levi položaj korenskega vozlišča in » levo.levo » položaj pomeni levo od leve, enak pristop se uporabi v primeru » prav « in » prav ”
• Ko definirate drevo, podajte »rootNode« kot argument za » displayLeadNodes() ” za izbiro in tiskanje vseh listnih vozlišč ustvarjenega drevesa.

Izhod, ustvarjen po prevajanju, potrjuje, da je bilo listno vozlišče podanega drevesa pridobljeno in natisnjeno prek konzole:

2. način: Natisnite vsa listna vozlišča binarnega drevesa z uporabo iterativnega pristopa

' iterativno » je najučinkovitejši pristop, uporablja koncept » potiskati « in » pop «, da izberete » list ” vozlišča. Spodaj so navedene ključne točke ali delovanje tega pristopa:

Razlaga zgornje kode je zapisana spodaj:

• Najprej ustvarite » Vozlišče ' razred, ki prejme en sam parameter ' vrednost ”, ki je nastavljena kot vrednost novo ustvarjenega vozlišča, leva in desna stran pa sta nastavljeni na nič. Tako kot v zgornjem primeru.
• Nato ustvarite funkcijo ' displayLeafNodes() «, ki sprejme en sam parameter » rootNode ”. To 'rootNode' se obravnava kot binarno drevo in najprej se preveri njegova praznina.
• Če vozlišče ni prazno, potem prazen seznam z imenom ' seznam « je ustvarjen in » rootNode ' se vanj vstavi parameter z uporabo ' potisni() ” metoda.
• Potem, ' medtem() ' se uporablja, ki se izvaja do dolžine ' seznam ”. Znotraj zanke je element, ki se nahaja na dnu drevesa ali ' seznam « se odstrani z uporabo » pop() ” metoda.
• Zdaj pa obstoj » levo « in » prav ” strani “rootNode” je preverjeno in če obe strani ne obstajata, to pomeni, da nima podrejenega vozlišča. Nato se to vozlišče prikaže na zaslonu in identificira kot listno vozlišče.
• Če je vozlišče na levi ali desni strani, pomeni, da ima otroke. Potem to ' levo « in » prav « je vozlišče potisnjeno v » seznam ” za nadaljnje delovanje iskanja listnega vozlišča.
• Na koncu ustvarite binarno drevo po meri tako, da posredujete vrednosti vozlišča kot parametre za » Vozlišče ” konstruktor razreda. Po ustvarjanju posredujte drevo »rootNode« kot argument za » displayLeafNodes() ”.

Izhod, ustvarjen po prevajanju, kaže, da so listna vozlišča danega drevesa natisnjena:

Dodatni nasvet: Tiskanje listnih vozlišč binarnega drevesa od desne proti levi

Če želite pridobiti vsa listna vozlišča, ki nimajo podrejenih vozlišč v ' prav ' do ' levo ” smeri je zaradi enostavnosti najbolj priporočljiv rekurzivni pristop. Na primer, isto drevo, opisano v zgornjih razdelkih, bo uporabljeno za pridobivanje listnega vozlišča, vendar v ' prav ' do ' levo ”, kot je prikazano spodaj:

Zgoraj navedena koda deluje takole:

• Najprej razred ' Vozlišče ” je ustvarjen, ki uporablja privzeti konstruktor za dodajanje novega vozlišča v drevo samo povezavo, izvedeno v zgornjih primerih.
• Nato je ' displayLeadNodes() ' je ustvarjena funkcija, ki sprejme en sam parameter ' rootNode ”. Ta parameter se preveri za ' nič ' pogoj prek ' če ” izjava.
• Če navedeno vozlišče ni resnično, potem je njegovo ' levo « in » prav ” stranska vozlišča so preverjena za ” nič ” stanje. Če sta oba ničelna, bo vozlišče identificirano kot ' list ” in natisnjena čez spletno stran.
• Po tem prenesite » prav « in » levo ' vozlišča ' rootNode ' do ' displayLeafNodes() ”.
• Dodelite položaj vsakega vozlišča tako, da ustvarite primerke z uporabo ' novo ' ključna beseda in ' Vozlišče() ” in podajanje položaja kot parametra konstruktorja.
• ' levo « pomeni levi položaj korenskega vozlišča in » levo.levo ” položaj pomeni levo ali levo. Enak pristop se uporablja v primeru ' prav « in » prav ”.
• Končno prenesite ' rootNode « kot argument za » displayLeafNode() ”.

Ustvarjeni izhod kaže, da so vozlišča listov natisnjena v smeri od desne proti levi.

To je vse o tiskanju vseh listnih vozlišč binarnega drevesa v kateri koli želeni smeri.

Zaključek

Če želite natisniti vsa listna vozlišča binarnega drevesa, ustvarite naključni razred, ki ustvarja in dodeljuje vrednosti vozliščem drevesa. Nato ustvarite naključno funkcijo, ki sprejme eno vozlišče drevesa v hierarhiji od vrha do dna. Ta funkcija vsebuje več ' če « pogoji, ki preverjajo, ali je » vozlišče « ni prazen in nima vozlišč v » levo « in » prav ', se to vozlišče obravnava kot ' list ” in se prikaže na konzoli. V tem priročniku je razložen postopek tiskanja vseh listnih vozlišč binarnega drevesa od leve proti desni ali od desne proti levi.