Ako vytlačiť všetky listové uzly binárneho stromu zľava doprava v JavaScripte?

Vizuálne znázornenie diskutovaných konceptov je znázornené na obrázku nižšie:

Táto príručka vysvetľuje proces tlače všetkých listových uzlov binárneho stromu tým, že zahŕňa nižšie uvedené časti:

• Ako identifikovať uzliny listov?
• Ako vytlačiť všetky listové uzly binárneho stromu zľava doprava v JavaScripte?
• Bonusový tip: Tlač listových uzlov binárneho stromu sprava doľava
• Záver

Ako identifikovať uzliny listov?

' list 'uzly sú tie, ktoré nemajú žiadne podradené uzly, alebo konkrétne, ktoré majú ' výška “z “ 0 “. Ak má uzol „ výška ' väčší než ' 0 “, potom tento uzol môže byť vnútorným uzlom alebo koreňovým uzlom. ' list ” uzly sú zvyčajne spätne sledované, aby sa identifikoval pôvodný zdroj, odkiaľ je tento uzol vygenerovaný. Väčšinou sa používa v algoritmoch vyhľadávania alebo hľadania chýb na nájdenie príčiny chyby alebo problému.

Ako vytlačiť všetky listové uzly binárneho stromu zľava doprava v JavaScripte?

Sú dva prístupy“ rekurzívne “ a „ iteratívny “, aby ste vybrali všetky listové uzly dostupné v poskytnutom binárnom strome v požadovanom „ vľavo “ až “ správny “smer. Praktická implementácia týchto prístupov je demonštrovaná v nižšie uvedených častiach:

• Vytlačte všetky listové uzly binárneho stromu zľava doprava rekurzívne
• Vytlačte všetky uzly listov binárneho stromu pomocou iteratívneho prístupu

Metóda 1: Rekurzívne vytlačte všetky listové uzly binárneho stromu zľava doprava

Rekurzívny prístup vyberie všetky uzly v a hĺbkový vyhľadávací algoritmus spôsobom, ktorý najprv prechádza cez celé ľavé bočné uzly, potom stredný uzol a nakoniec pravé bočné uzly. Táto operácia sa vykonáva rekurzívne pre každý uzol a keď už nedochádza k ďalšiemu prechodu cez „ list „identifikujú sa uzly. Ak chcete lepšie porozumieť tomuto konceptu, navštívte nižšie uvedený útržok kódu:

Vysvetlenie vyššie uvedeného bloku kódu je uvedené nižšie:

• Najprv vytvorte triedu s názvom „ uzol “, ktorý vytvorí nový uzol a nastaví jeho hodnotu na „ 0 “. Priložený „ vľavo “ a „ správny “bočné uzly sú nastavené na “ nulový ” štandardne pomocou konštruktora triedy.
• Ďalej definujte „ displayLeafNodes() ” funkcia, ktorá akceptuje jeden parameter „ rootNode “. Táto parametrická hodnota sa považuje za aktuálne vybraný uzol binárneho stromu.
• Vo vnútri funkcie je „ ak “ sa používa na kontrolu, či „ rootNode “ je nulové alebo nie. V prípade ' nulový ” ďalšie vykonávanie sa pre tento uzol zastavilo. V druhom prípade rootNode “ vľavo “ a „ správny ' bočné uzly sú kontrolované na ' nulový “. Ak sú obe nulové, hodnota „ uzol “ sa vytlačí.
• Ak „ vľavo “ alebo „ správny ” uzol nie je “null”, potom odovzdajte túto stranu uzla do “ displayLeafNodes() ” pre rekurzívnu operáciu.
• Definujte novú funkciu s názvom „ provNode() “, ktorý akceptuje jediný parameter „ val “. Vo vnútri funkcie vytvorte novú inštanciu súboru „ Uzol “trieda s názvom “ tempNode “. Priraďte parametrické „ val ” ako hodnotu pre vlastnosť triedy “ obsahu “ a nastavte „ vľavo “ a „ správny “bočné uzly na “ nulový ' predvolene.
• Nakoniec vytvorte objekt s názvom „ rootNode ' pre ' provNode() ” a odovzdať hodnotu uzla ako tento parameter funkcie. Vytvorte ľavý a pravý bočný uzol pridaním „ vľavo “ a „ správny ” kľúčové slová s “rootNode” a priraďte im hodnotu pomocou rovnakej funkcie “ provNode() “.
• ' vľavo “ znamená ľavú pozíciu koreňového uzla a „ vľavo.vľavo “pozícia znamená, že vľavo od ľavej strany sa rovnaký prístup použije v prípade „ správny “ a „ správny “
• Po definovaní stromu odovzdajte „rootNode“ ako argument pre „ displayLeadNodes() ” na výber a tlač všetkých uzlov listov vytvoreného stromu.

Výstup vygenerovaný po kompilácii potvrdzuje, že listový uzol poskytnutého stromu bol načítaný a vytlačený cez konzolu:

Metóda 2: Tlač všetkých listových uzlov binárneho stromu pomocou iteratívneho prístupu

' iteratívny “prístup je najefektívnejší prístup, používa koncept “ TAM “ a „ pop “, aby ste vybrali „ list “uzly. Kľúčové body alebo fungovanie tohto prístupu sú uvedené nižšie:

Vysvetlenie vyššie uvedeného kódu je napísané nižšie:

• Najprv vytvorte „ Uzol ”trieda, ktorá prijíma jeden parameter” hodnotu ” ktorá je nastavená ako hodnota novovytvoreného uzla a ľavá a pravá strana sú nastavené na hodnotu null. Rovnako ako vo vyššie uvedenom príklade.
• Ďalej vytvorte funkciu ' displayLeafNodes() “, ktorý akceptuje jeden parameter „ rootNode “. Tento „rootNode“ sa považuje za binárny strom a najprv sa skontroluje jeho prázdnota.
• Ak uzol nie je prázdny, zobrazí sa prázdny zoznam s názvom „ zoznam “ je vytvorený a “ rootNode “ sa do nej vloží pomocou „ TAM() “.
• Potom ' zatiaľ čo() “, ktorý sa vykonáva do dĺžky „ zoznam “. Vo vnútri slučky sa nachádza prvok nachádzajúci sa v spodnej časti stromu alebo „ zoznam “ sa odstráni pomocou “ pop() “.
• Teraz existencia „ vľavo “ a „ správny ” strany „rootNode“ sú skontrolované a ak obe strany neexistujú, znamená to, že nemá žiadny dcérsky uzol. Potom sa tento uzol zobrazí na obrazovke a identifikuje sa ako listový uzol.
• Ak je uzol na ľavej alebo pravej strane, znamená to, že má deti. Potom to „ vľavo “ a „ správny 'uzol sa vtlačí do ' zoznam ” pre ďalšiu operáciu hľadania listového uzla.
• Nakoniec vytvorte vlastný binárny strom odovzdaním hodnôt uzlov ako parametrov pre „ Uzol “konštruktor triedy. Po vytvorení odovzdajte strom „rootNode“ ako argument pre „ displayLeafNodes() “.

Výstup vygenerovaný po kompilácii ukazuje, že listové uzly poskytnutého stromu sú vytlačené:

Bonusový tip: Tlač listových uzlov binárneho stromu sprava doľava

Ak chcete získať všetky listové uzly, ktoré nemajú žiadne podradené uzly v „ správny “ až “ vľavo “ smer, rekurzívny prístup sa najviac odporúča kvôli jeho jednoduchosti. Napríklad ten istý strom, o ktorom sa hovorí vo vyššie uvedených častiach, sa použije na získanie listového uzla, ale v „ správny “ na “ vľavo “ smer, ako je znázornené nižšie:

Vyššie uvedený kód funguje takto:

• Po prvé, trieda „ Uzol ” je vytvorený, ktorý používa predvolený konštruktor na pridanie nového uzla do stromu len odkaz vykonaný vo vyššie uvedených príkladoch.
• Ďalej, „ displayLeadNodes() “ je vytvorená funkcia, ktorá akceptuje jeden parameter „ rootNode “. Tento parameter sa kontroluje na „ nulový “podmienka cez “ ak “vyhlásenie.
• Ak zadaný uzol nie je pravdivý, potom jeho „ vľavo “ a „ správny 'skontrolujú sa bočné uzly' nulový “podmienka. Ak sú obe nulové, uzol bude identifikovaný ako „ list a vytlačí sa cez webovú stránku.
• Potom prejdite „ správny “ a „ vľavo 'uzly ' rootNode “ na “ displayLeafNodes() “.
• Prideľte polohu každého uzla vytvorením inštancií pomocou „ Nový kľúčové slovo a uzol() ” a špecifikovaním pozície ako parametra konštruktora.
• ' vľavo “ znamená ľavú pozíciu koreňového uzla a „ vľavo.vľavo ” poloha znamená vľavo alebo vľavo. Rovnaký prístup sa uplatňuje v prípade „ správny “ a „ správny “.
• Nakoniec prejdite „ rootNode “ ako argument pre „ displayLeafNode() “.

Vygenerovaný výstup ukazuje, že listové uzly sú vytlačené v smere sprava doľava.

To je všetko o vytlačení všetkých listových uzlov binárneho stromu v akomkoľvek požadovanom smere.

Záver

Ak chcete vytlačiť všetky listové uzly binárneho stromu, vytvorte náhodnú triedu, ktorá vytvorí a priradí hodnoty uzlom stromu. Ďalej vytvorte náhodnú funkciu, ktorá akceptuje jeden uzol stromu v hierarchii zhora nadol. Táto funkcia obsahuje viacero „ ak “ podmienky, ktoré kontrolujú, či „ uzol “nie je prázdne a nemá žiadne uzly v poli “ vľavo “ a „ správny “, potom sa tento uzol považuje za “ list “ a zobrazí sa na konzole. Táto príručka vysvetľuje postup tlače všetkých listových uzlov binárneho stromu zľava doprava alebo sprava doľava.