Python-Datenstrukturen: Der Giving Tree

Python-Bäume ähneln stark verknüpften Listen, haben jedoch eine hierarchische Reihenfolge. Bäume bestehen aus Knoten, die mit anderen Knoten verknüpft sind. Der untere Knoten ohne Link wird als Leaves bezeichnet . Der Knoten, der mit einem anderen Knoten verknüpft ist, wird als übergeordneter Knoten bezeichnet, und der verknüpfte Knoten sind die untergeordneten Knoten .

Ein Baum wird normalerweise mit einer Vielzahl von Knoten oder einer kaskadierenden tiefen Struktur erstellt. Man kann also sagen, dass ein Baum entweder breit oder tief ist .

Eine effiziente Version einer Baumstruktur wird als binärer Suchbaum bezeichnet. Dort darf ein übergeordneter Knoten nur zwei untergeordnete Knoten haben. Der Knoten links hat einen kleineren Wert als der Knoten rechts. Wenn Sie einen solchen Baum bauen, ist es sehr effizient, ihn zu durchqueren und einen bestimmten Wert zu finden.

Wenn ich im obigen Beispiel den Wert 98 von 39 ermitteln wollte, bewegte ich mich nach rechts als 98> 39 - von 70 wieder nach rechts - von 97 nach rechts und in drei Zügen habe ich meinen gewünschten Knoten gefunden.

Erstellen wir also einen Baumknoten in Python und sehen einen in Aktion. Alles, was wir brauchen, um einen Baumknoten zu initiieren, ist ein Name. Wir weisen ihm automatisch eine leere Liste zu, in der alle künftigen untergeordneten Knoten gespeichert werden.

Wenn Sie meine früheren Artikel zur Python-Datenstruktur gelesen haben, sollte Ihnen dies bekannt vorkommen.

Wie bei jeder Datenstruktur müssen wir jetzt die praktischen Funktionen berücksichtigen, die unser Baum haben soll. Das Hinzufügen eines Knotens und das Entfernen eines Knotens liegen auf der Hand und sind auch einfach zu implementieren.

Zum Hinzufügen verwende ich die Methode append () , und zum Entfernen durchlaufe ich einfach die Liste self.children und füge alle Knoten mit Ausnahme des Knotens, den ich entfernen möchte, erneut hinzu.

Als nächstes wollen wir den Baum durchlaufen, um die gewünschten Informationen zu finden. Um diese Methode zu erstellen, beginnen wir mit einer leeren Liste, die mit jedem zu besuchenden Knoten gefüllt wird. Während dieser Knoten untergeordnete Knoten hat, werden wir ihn herausspringen lassen und zur Liste der zu besuchenden Knoten hinzufügen.

Wo würde eine solche Datenstruktur Ihrer Meinung nach am besten genutzt? Wenn wir eine Logik für den Zugriff auf die Knoten hinzufügen, könnten wir möglicherweise viele Berechtigungen, die ein Benutzer haben könnte, unterteilen.

Datenbäume sind ein großartiges und weit verbreitetes Werkzeug in der Codierungswelt. Ich hoffe, diese kurze Einführung hat zumindest einen wertvollen Einblick gegeben, warum Sie etwas über diese Strukturen wissen möchten.