<

Baum repräsentiert die Knoten, die durch Kanten verbunden sind. Wir werden Binärbaum oder Binärsuchbaum speziell diskutieren.

Binärbaum ist eine spezielle Datenstruktur, die für Datenspeicherzwecke verwendet wird. Ein Binärbaum hat eine spezielle Bedingung, dass jeder Knoten maximal zwei untergeordnete Knoten haben kann., Ein Binärbaum hat die Vorteile eines geordneten Arrays und einer verknüpften Liste, da die Suche so schnell ist wie in einem sortierten Array und das Einfügen oder Löschen so schnell ist wie in einer verknüpften Liste.

Wichtige Begriffe

Im Folgenden sind die wichtigen Begriffe in Bezug auf Baum.

  • Pfad-Pfad bezieht sich auf die Reihenfolge der Knoten entlang der Kanten eines Baums.

  • Root-Der Knoten oben im Baum heißt root. Es gibt nur eine Wurzel pro Baum und einen Pfad vom Wurzelknoten zu einem beliebigen Knoten.,

  • Parent-Jeder Knoten außer dem Wurzelknoten hat eine Kante nach oben zu einem Knoten namens parent.

  • Child-Der Knoten unterhalb eines gegebenen Knotens, der durch seine Kante nach unten verbunden ist, wird als untergeordneter Knoten bezeichnet.

  • Blatt-Der Knoten, der keinen untergeordneten Knoten hat, wird Blattknoten genannt.

  • Teilbaum-Teilbaum repräsentiert die Nachkommen eines Knotens.

  • Visiting-Visiting bezieht sich auf die Überprüfung des Wertes eines Knotens, wenn sich die Steuerung auf dem Knoten befindet.

  • Durchqueren-Durchqueren bedeutet, Knoten in einer bestimmten Reihenfolge zu durchlaufen.,

  • Ebenen-Ebene eines Knotens stellt die Erzeugung eines Knotens dar. Wenn sich der Stammknoten auf Ebene 0 befindet, befindet sich sein nächster untergeordneter Knoten auf Ebene 1, sein Enkelkind auf Ebene 2 usw.

  • keys-Key stellt einen Wert eines Knotens dar, auf dessen Basis eine Suchoperation für einen Knoten ausgeführt werden soll.

Binäre Suchbaumdarstellung

Der binäre Suchbaum weist ein besonderes Verhalten auf. Das linke untergeordnete Element eines Knotens muss einen Wert haben, der unter dem Wert seines übergeordneten Knotens liegt, und das rechte untergeordnete Element des Knotens muss einen Wert haben, der über dem übergeordneten Wert liegt.,

Wir werden den Baum mithilfe des Knotenobjekts implementieren und über Referenzen verbinden.

Baumknoten

Der Code zum Schreiben eines Baumknotens ähnelt dem unten angegebenen. Es hat einen Datenteil und Verweise auf seine linken und rechten untergeordneten Knoten.

struct node { int data; struct node *leftChild; struct node *rightChild;};

In einem Baum teilen sich alle Knoten ein gemeinsames Konstrukt.

BST Grundlegende Operationen

Die grundlegenden Operationen, die an einer binären Suchbaumdatenstruktur ausgeführt werden können, sind die folgenden −

  • Insert − Fügt ein Element in einen Baum ein/erstelle einen Baum.,

  • Suche-Sucht ein Element in einem Baum.

  • Preorder Traversal-Durchquert einen Baum in einer Vorbestellung.

  • Inorder Traversal-Durchquert einen Baum in der Reihenfolge.

  • Postorder Traversal-Durchquert einen Baum in einer Post-Order-Weise.

In diesem Kapitel lernen wir, eine Baumstruktur zu erstellen (in sie einzufügen) und ein Datenelement in einem Baum zu durchsuchen. Wir werden im kommenden Kapitel etwas über Baumdurchquerungsmethoden lernen.

Einfügevorgang

Die allererste Einfügung erzeugt den Baum., Danach, wenn ein Element eingefügt werden soll, suchen Sie zuerst seine richtige Position. Starten Sie die Suche vom Stammknoten aus, und wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie nach der leeren Position im linken Teilbaum und fügen Sie die Daten ein. Suchen Sie andernfalls nach der leeren Position im rechten Teilbaum und fügen Sie die Daten ein.,

Algorithmus

If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If

Implementierung

Die Implementierung der Insert −Funktion sollte folgendermaßen aussehen –

Suchoperation

Wenn ein Element gesucht werden soll, beginnen Sie mit der Suche vom Stammknoten aus, und wenn die Daten kleiner als der Schlüsselwert sind, suchen Sie nach dem Element im linken Teilbaum. Suchen Sie andernfalls nach dem Element im richtigen Teilbaum. Folgen Sie dem gleichen Algorithmus für jeden Knoten.

Algorithmus

If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if

Die Implementierung dieses Algorithmus sollte so Aussehen.,

Um mehr über die Implementierung der binären Suchbaumdatenstruktur zu erfahren, klicken Sie bitte hier.

<