Wie drucke ich alle Blattknoten eines Binärbaums von links nach rechts in JavaScript?

Die visuelle Darstellung der diskutierten Konzepte ist in der folgenden Abbildung dargestellt:

In dieser Anleitung wird der Prozess des Druckens aller Blattknoten eines Binärbaums anhand der folgenden Abschnitte erläutert:

• Wie identifiziere ich Blattknoten?
• Wie drucke ich alle Blattknoten eines Binärbaums von links nach rechts in JavaScript?
• Bonus-Tipp: Blattknoten eines Binärbaums von rechts nach links drucken
• Abschluss

Wie identifiziere ich Blattknoten?

Der ' Blatt „Knoten sind diejenigen, die keine untergeordneten Knoten haben, oder genauer gesagt, die das „ Höhe ' von ' 0 “. Wenn der Knoten ein „ Höhe ' größer als ' 0 ” Dann kann dieser Knoten der innere Knoten oder der Wurzelknoten sein. Der ' Blatt „Knoten werden normalerweise zurückverfolgt, um die ursprüngliche Quelle zu identifizieren, aus der dieser Knoten generiert wurde. Es wird hauptsächlich in Such- oder Fehlersuchalgorithmen verwendet, um die Ursache eines Fehlers oder Problems zu finden.

Wie drucke ich alle Blattknoten eines Binärbaums von links nach rechts in JavaScript?

Es gibt zwei Ansätze“ rekursiv ' Und ' iterativ ” um alle Blattknoten auszuwählen, die im bereitgestellten Binärbaum im gewünschten Bereich verfügbar sind. links ' Zu ' Rechts ” Richtung. Die praktische Umsetzung dieser Ansätze wird in den folgenden Abschnitten demonstriert:

• Alle Blattknoten eines Binärbaums rekursiv von links nach rechts drucken
• Drucken Sie alle Blattknoten eines Binärbaums mithilfe des iterativen Ansatzes

Methode 1: Alle Blattknoten eines Binärbaums rekursiv von links nach rechts drucken

Der rekursive Ansatz wählt alle Knoten in a aus Tiefensuchalgorithmus Dabei werden zuerst die gesamten Knoten auf der linken Seite, dann der mittlere Knoten und am Ende die Knoten auf der rechten Seite durchquert. Diese Operation wird rekursiv für jeden Knoten ausgeführt und wenn keine weitere Durchquerung des „ Blatt „Knoten werden identifiziert. Um dieses Konzept besser zu verstehen, sehen Sie sich den folgenden Codeausschnitt an:

Die Erklärung des obigen Codeblocks ist unten angegeben:

• Erstellen Sie zunächst eine Klasse mit dem Namen „ Knoten “, das einen neuen Knoten erstellt und seinen Wert auf „ setzt 0 “. Der Anhang ' links ' Und ' Rechts „Seitenknoten sind auf „ gesetzt Null ” standardmäßig mit dem Klassenkonstruktor.
• Als nächstes definieren Sie ein „ displayLeafNodes() ” Funktion, die einen einzelnen Parameter von „ akzeptiert Wurzelknoten “. Dieser Parameterwert wird als aktuell ausgewählter Knoten eines Binärbaums betrachtet.
• Innerhalb der Funktion ist das „ Wenn Die Anweisung wird verwendet, um zu überprüfen, ob die „ Wurzelknoten ” ist null oder nicht. Im Fall von ' Null ” Die weitere Ausführung wurde für diesen Knoten gestoppt. Im anderen Fall ist der rootNode „ links ' Und ' Rechts „Seitenknoten werden auf „geprüft“ Null “. Wenn beide null sind, ist der Wert von „ Knoten ” wird gedruckt.
• Wenn das „ links ' oder ' Rechts „Knoten ist nicht „null“, dann übergeben Sie diese Seite des Knotens an „ displayLeafNodes() ”-Funktion für die rekursive Operation.
• Definieren Sie eine neue Funktion mit dem Namen „ provNode() “, das den einzelnen Parameter „ akzeptiert val “. Erstellen Sie innerhalb der Funktion eine neue Instanz von „ Knoten „Klasse mit dem Namen“ tempNode “. Weisen Sie den Parameter „ val ” als Wert für die Klasseneigenschaft „ Inhalt “ und stellen Sie „ links ' Und ' Rechts ” Seitenknoten zu „ Null ' standardmäßig.
• Erstellen Sie abschließend ein Objekt mit dem Namen „ Wurzelknoten ” für die „ provNode() ”-Funktion und übergeben Sie den Knotenwert als diesen Funktionsparameter. Erstellen Sie die Knoten auf der linken und rechten Seite, indem Sie „ links ' Und ' Rechts ” Schlüsselwörter mit dem „rootNode“ und weisen Sie ihnen mit derselben Funktion einen Wert zu „ provNode() “.
• Der ' links „bedeutet die linke Position des Wurzelknotens und die „ links Links „Position bedeutet links von links“. Derselbe Ansatz wird im Fall von „ angewendet. Rechts ' Und ' Rechts ”
• Übergeben Sie nach der Definition des Baums den „rootNode“ als Argument für „ displayLeadNodes() ”-Funktion zum Auswählen und Drucken aller Blattknoten des erstellten Baums.

Die nach der Kompilierung generierte Ausgabe bestätigt, dass der Blattknoten des bereitgestellten Baums abgerufen und über die Konsole gedruckt wurde:

Methode 2: Drucken Sie alle Blattknoten eines Binärbaums mithilfe des iterativen Ansatzes

Der ' iterativ Der „Ansatz“ ist der effizienteste Ansatz, er verwendet das Konzept „ drücken ' Und ' Pop ”, um die Option „ Blatt ”Knoten. Die wichtigsten Punkte bzw. die Funktionsweise dieses Ansatzes sind nachstehend aufgeführt:

Die Erklärung des obigen Codes ist unten aufgeführt:

• Erstellen Sie zunächst ein „ Knoten „Klasse, die einen einzelnen Parameter empfängt“ Wert ” wird als Wert des neu erstellten Knotens festgelegt und die linke und rechte Seite werden auf Null gesetzt. Genau wie im obigen Beispiel.
• Als nächstes erstellen Sie eine Funktion „ displayLeafNodes() ” das einen einzelnen Parameter von „ akzeptiert Wurzelknoten “. Dieser „rootNode“ wird als Binärbaum betrachtet und zunächst auf seine Leere überprüft.
• Wenn der Knoten nicht leer ist, wird eine leere Liste mit dem Namen „ Liste ” wird erstellt und das „ Wurzelknoten Der Parameter „“ wird mit dem Befehl „“ eingefügt. drücken() ' Methode.
• Dann ist die ' während() ” wird verwendet, das bis zur Länge eines „ ausgeführt wird Liste “. Innerhalb der Schleife befindet sich das Element am Ende eines Baums oder „ Liste „wird mit dem „“ entfernt Pop() ' Methode.
• Nun ist die Existenz des „ links ' Und ' Rechts Die Seiten von „rootNode“ werden überprüft. Wenn beide Seiten nicht vorhanden sind, bedeutet dies, dass es keinen untergeordneten Knoten gibt. Anschließend wird dieser Knoten auf dem Bildschirm angezeigt und als Blattknoten identifiziert.
• Wenn sich auf der linken oder rechten Seite ein Knoten befindet, bedeutet dies, dass er untergeordnete Knoten hat. Dann ist das „ links ' Und ' Rechts ”-Knoten wird in den „ Liste ” für die weitere Suche nach dem Blattknoten.
• Erstellen Sie am Ende einen benutzerdefinierten Binärbaum, indem Sie die Knotenwerte als Parameter für „ Knoten ” Klassenkonstruktor. Übergeben Sie nach der Erstellung den Baum „rootNode“ als Argument für „ displayLeafNodes() ” Funktion.

Die nach der Kompilierung generierte Ausgabe zeigt, dass die Blattknoten des bereitgestellten Baums gedruckt werden:

Bonus-Tipp: Blattknoten eines Binärbaums von rechts nach links drucken

Um alle Blattknoten abzurufen, die keine untergeordneten Knoten im „ Rechts ' Zu ' links ”-Richtung wird der rekursive Ansatz aufgrund seiner Einfachheit am meisten empfohlen. Zum Beispiel wird derselbe Baum, der in den obigen Abschnitten besprochen wurde, zum Abrufen des Blattknotens verwendet, jedoch im „ Rechts ' zum ' links ” Richtung, wie unten gezeigt:

Der oben genannte Code funktioniert folgendermaßen:

• Zuerst die Klasse „ Knoten ” wird erstellt, der den Standardkonstruktor verwendet, um einen neuen Knoten im Baum hinzuzufügen, genau wie die in den obigen Beispielen erstellte Verknüpfung.
• Als nächstes wird das „ displayLeadNodes() Es wird eine Funktion erstellt, die einen einzelnen Parameter von „ akzeptiert. Wurzelknoten “. Dieser Parameter wird auf „ Null ” Bedingung über die „ Wenn ' Stellungnahme.
• Wenn der angegebene Knoten nicht wahr ist, dann ist es „ links ' Und ' Rechts „Seitenknoten werden auf „geprüft“ Null ' Zustand. Wenn beide null sind, wird der Knoten als „ Blatt ”-Knoten und über die Webseite gedruckt.
• Übergeben Sie danach die „ Rechts ' Und ' links ” Knoten der „ Wurzelknoten ' zum ' displayLeafNodes() ” Funktion.
• Ordnen Sie die Position jedes Knotens zu, indem Sie die Instanzen mithilfe des „ neu ” Schlüsselwort und das „ Knoten() ”-Konstruktor und Angabe der Position als Konstruktorparameter.
• Der ' links „bedeutet die linke Position des Wurzelknotens und die „ links Links „Position bedeutet links oder links.“ Der gleiche Ansatz wird im Fall von „ Rechts ' Und ' Rechts “.
• Übergeben Sie abschließend die „ Wurzelknoten “ als Argument für die „ displayLeafNode() ” Funktion.

Die generierte Ausgabe zeigt, dass Blattknoten von rechts nach links gedruckt werden.

Dabei geht es darum, alle Blattknoten eines Binärbaums in jede gewünschte Richtung zu drucken.

Abschluss

Um alle Blattknoten eines Binärbaums zu drucken, erstellen Sie eine Zufallsklasse, die die Baumknoten erstellt und ihnen Werte zuweist. Erstellen Sie als Nächstes eine Zufallsfunktion, die einen einzelnen Knoten des Baums in einer Hierarchie von oben nach unten akzeptiert. Diese Funktion enthält mehrere „ Wenn ” Bedingungen, die prüfen, ob die „ Knoten ” ist nicht leer und hat keine Knoten im „ links ' Und ' Rechts ”-Richtung, dann wird dieser Knoten als „ Blatt ”-Knoten und wird auf der Konsole angezeigt. In dieser Anleitung wurde das Verfahren zum Drucken aller Blattknoten eines Binärbaums von links nach rechts oder von rechts nach links erläutert.