Sådan udskrives alle bladknuder i et binært træ fra venstre mod højre i JavaScript?

Den visuelle repræsentation af de diskuterede begreber er vist i nedenstående figur:

Denne vejledning forklarer processen med at udskrive alle bladknuder i et binært træ ved at dække nedenstående afsnit:

• Hvordan identificerer man bladknuder?
• Sådan udskrives alle bladknuder i et binært træ fra venstre mod højre i JavaScript?
• Bonustip: Udskrivning af bladknuder af et binært træ fra højre til venstre retning
• Konklusion

Hvordan identificerer man bladknuder?

Det ' blad ' noder er dem, der ikke har nogen underordnede noder, eller for at være specifik, som har ' højde ' af ' 0 ”. Hvis noden har en ' højde ' bedre end ' 0 ” så kan den node være den indre node eller rodnode. Det ' blad ” noder er normalt tilbagesporet for at identificere den oprindelige kilde, hvorfra denne node er genereret. Det bruges mest i søge- eller fejlfindingsalgoritmer for at finde årsagen til en fejl eller et problem.

Sådan udskrives alle bladknuder i et binært træ fra venstre mod højre i JavaScript?

Der er to tilgange ' rekursive ' og ' iterativ ” for at vælge alle tilgængelige bladknuder i det angivne binære træ i det ønskede ” venstre ' til ' højre ” retning. Den praktiske implementering af disse tilgange er demonstreret i nedenstående angivne afsnit:

• Udskriv alle bladknuder i et binært træ fra venstre til højre rekursivt
• Udskriv alle bladknuder i et binært træ ved hjælp af den iterative tilgang

Metode 1: Udskriv alle bladknuder i et binært træ fra venstre mod højre rekursivt

Den rekursive tilgang vælger alle noder i en dybde-først søgealgoritme måde, som først krydser hele venstre sideknudepunkt, derefter midterknudepunktet og højre sideknudepunkter til sidst. Denne operation udføres rekursivt for hver knude, og når der ikke længere er traversering af ' blad ” noder bliver identificeret. For bedre at forstå dette koncept, besøg nedenstående kodestykke:

Forklaringen af ​​ovenstående kodeblok er angivet nedenfor:

• Først skal du oprette en klasse med navnet ' node ', der opretter en ny node og sætter dens værdi til ' 0 ”. Den vedhæftede ' venstre ' og ' højre ' sideknuder er sat til ' nul ” som standard ved hjælp af klassekonstruktøren.
• Dernæst skal du definere en ' displayLeafNodes() ' funktion, der accepterer en enkelt parameter af ' rootNode ”. Denne parametriske værdi betragtes som den aktuelt valgte node i et binært træ.
• Inde i funktionen er ' hvis '-erklæring bruges til at kontrollere, om ' rootNode ” er nul eller ej. I tilfælde af ' nul ” den videre udførelse stoppede for den node. I det andet tilfælde er rootNode ' venstre ' og ' højre ' sideknuder er markeret for ' nul ”. Hvis begge er nul, værdien af ​​' node ” bliver udskrevet.
• Hvis ' venstre ' eller ' højre ”-knuden er ikke ”nul”, så send den side af knudepunktet til ” displayLeafNodes() ” funktion til den rekursive operation.
• Definer en ny funktion med navnet ' provNode() ', der accepterer den enkelte parameter af ' val ”. Inde i funktionen skal du oprette en ny forekomst af ' Node ' klasse med navnet ' tempNode ”. Tildel parameteren ' val ' som værdi for klasseejendom ' indhold ' og indstil ' venstre ' og ' højre ' sideknuder til ' nul ' som standard.
• Til sidst skal du oprette et objekt med navnet ' rootNode ' for ' provNode() ” funktion og videregive nodeværdien som denne funktionsparameter. Opret venstre og højre side noder ved at tilføje ' venstre ' og ' højre ' nøgleord med 'rootNode' og tildel dem værdi ved hjælp af den samme funktion ' provNode() ”.
• Det ' venstre ' betyder den venstre position af rodnoden og ' venstre.venstre ' position betyder venstre fra venstre samme tilgang anvendes i tilfælde af ' højre ' og ' højre ”
• Efter at have defineret træet, skal du sende 'rootNode' som et argument for ' displayLeadNodes() ” funktion til at vælge og udskrive alle bladknuder i det oprettede træ.

Det output, der genereres efter kompileringen, bekræfter, at bladknuden i det angivne træ er blevet hentet og udskrevet over konsollen:

Metode 2: Udskriv alle bladknuder i et binært træ ved hjælp af den iterative tilgang

Det ' iterativ ' tilgang er den mest effektive tilgang, den bruger konceptet ' skubbe ' og ' pop ' for at vælge ' blad ” noder. Nøglepunkterne eller virkningen af ​​denne tilgang er angivet nedenfor:

Forklaringen af ​​ovenstående kode er skrevet nedenfor:

• Først skal du oprette en ' Node ' klasse, der modtager en enkelt parameter ' værdi ” som er sat som værdien af ​​den nyoprettede node, og venstre og højre side er sat til null. Præcis som i ovenstående eksempel.
• Opret derefter en funktion ' displayLeafNodes() ', der accepterer en enkelt parameter af ' rootNode ”. Denne 'rootNode' betragtes som det binære træ, og dets tomhed kontrolleres først.
• Hvis noden ikke er tom, så er en tom liste med navnet ' liste ' oprettes og ' rootNode parameter indsættes i den ved hjælp af ' skubbe() ” metode.
• Derefter ' mens() ' bruges, som udføres indtil længden af ​​en ' liste ”. Inde i løkken, elementet, der findes i bunden af ​​et træ eller ' liste ' bliver fjernet ved hjælp af ' pop() ” metode.
• Nu, eksistensen af ​​' venstre ' og ' højre ” sider af “rootNode” er markeret, og hvis begge sider ikke findes, betyder det, at den ikke har nogen underordnet node. Derefter bliver denne node vist over skærmen og identificeret som en bladknude.
• Hvis der er en knude på venstre eller højre side, betyder det, at den har børn. Så at ' venstre ' og ' højre ' node bliver skubbet ind i ' liste ” for videre betjening af at finde bladknuden.
• Til sidst skal du oprette et brugerdefineret binært træ ved at overføre nodeværdierne som parametrene for ' Node ” klasse konstruktør. Efter oprettelsen skal du sende træet 'rootNode' som et argument for ' displayLeafNodes() ' funktion.

Output genereret efter kompileringen viser, at bladknuderne i det medfølgende træ er udskrevet:

Bonustip: Udskrivning af bladknuder af et binært træ fra højre til venstre retning

For at hente alle bladknuder, der ikke har nogen underordnede noder i ' højre ' til ' venstre ” retning, er den rekursive tilgang den mest anbefalede på grund af dens lethed. For eksempel vil det samme træ, der er diskuteret i ovenstående afsnit, blive brugt til at hente bladknuden, men i ' højre ' til ' venstre ” retning, som vist nedenfor:

Ovennævnte kode fungerer således:

• Først klassen ' Node ” oprettes, der bruger standardkonstruktøren til at tilføje en ny node i træet bare linket i ovenstående eksempler.
• Dernæst ' displayLeadNodes() ' funktion oprettes, der accepterer en enkelt parameter af ' rootNode ”. Denne parameter kontrolleres for ' nul ' tilstand via ' hvis ' udmelding.
• Hvis den angivne node ikke er sand, så er dens ' venstre ' og ' højre ' sideknuder er markeret for ' nul ' tilstand. Hvis begge er nul, vil noden blive identificeret som en ' blad ” node og udskrevet over websiden.
• Derefter skal du videregive ' højre ' og ' venstre ' noder af ' rootNode ' til ' displayLeafNodes() ' funktion.
• Tildel positionen for hver node ved at oprette forekomsterne ved hjælp af ' ny ' søgeord og ' Node() ” konstruktør og angiver positionen som konstruktørparameter.
• Det ' venstre ' betyder den venstre position af rodnoden og ' venstre.venstre ” position betyder venstre eller venstre. Den samme tilgang anvendes i tilfælde af ' højre ' og ' højre ”.
• Bestå endelig ' rootNode ' som argument for ' displayLeafNode() ' funktion.

Det genererede output viser, at bladknuder udskrives i højre-til-venstre retning.

Det handler om at udskrive alle bladknuder i et binært træ i enhver ønsket retning.

Konklusion

For at udskrive alle bladknuder i et binært træ skal du oprette en tilfældig klasse, der opretter og tildeler værdier til træknuderne. Derefter skal du oprette en tilfældig funktion, der accepterer en enkelt knude i træet i et top-til-bund-hierarki. Denne funktion indeholder flere ' hvis ' betingelser, der kontrollerer, om ' node ' er ikke tom, og den har ingen noder i ' venstre ' og ' højre ' retning, så betragtes den node som en ' blad ” node og vises på konsollen. Denne vejledning har forklaret proceduren for udskrivning af alle bladknuder i et binært træ fra venstre mod højre eller højre mod venstre retning.