Datenstrukturen in Python – Bäume

Die Baumdatenstruktur in Python ist eine nichtlineare Datenstruktur, in der Elemente (Knoten genannt) durch Kanten verbunden sind und es nur einen Pfad zwischen zwei beliebigen Knoten gibt.

Baumdatenstruktur in Python

Wie alle Programmiersprachen ist ein Baum in Python eine hierarchische Datenstruktur, bei der jeder Knoten durch Kanten verbunden ist. Ein Baum besteht aus mehreren Knoten mit einem eindeutigen Wurzelknoten als Ausgangspunkt. Bäume werden häufig zur Darstellung hierarchischer Organisationen verwendet, beispielsweise in Organigrammen oder Dateisystemen.

Der oberste Knoten des Baums wird als Wurzelknoten bezeichnet, und die Knoten darunter werden als untergeordnete Knoten bezeichnet. Jeder Knoten kann mehrere untergeordnete Knoten haben, und diese untergeordneten Knoten können auch eigene untergeordnete Knoten haben, wodurch eine rekursive Struktur entsteht.

Grundbegriffe für Bäume

• Wurzelknoten: Der oberste Knoten des Baums.

• Übergeordneter Knoten: Ein Knoten mit untergeordneten Knoten.

• Untergeordneter Knoten: Ein Knoten, der ein Nachkomme eines anderen Knotens ist.

• Blattknoten: Ein Knoten ohne untergeordnete Knoten.

• Teilbaum: Ein Baum, der aus einem Knoten und seinen Nachkommen besteht.

• Höhe: Die Anzahl der Kanten im längsten Pfad von einem Knoten zu einem Blattknoten.

• Tiefe: Die Anzahl der Kanten vom Wurzelknoten zum Knoten.

Typ der Baumdatenstruktur

Es gibt drei Arten von Baumdatenstrukturen:

• Binärbaum: Eine Baumdatenstruktur mit höchstens 2 untergeordneten Knoten. Da jedes Element in einem Binärbaum höchstens zwei untergeordnete Knoten hat, nennen wir sie normalerweise linken untergeordneten Knoten und rechten untergeordneten Knoten.

• Trinomialbaum: Eine Baumdatenstruktur mit bis zu drei untergeordneten Knoten pro Knoten, normalerweise als „links“, „Mitte“ bzw. „rechts“ bezeichnet.

• N-ärer Baum: Ein allgemeiner Baum ist eine Sammlung von Knoten, wobei jeder Knoten eine Datenstruktur ist, die aus einer Referenzliste von Datensätzen und ihren untergeordneten Knoten besteht (wiederholte Referenzen sind nicht zulässig). Im Gegensatz zu einer verknüpften Liste speichert jeder Knoten die Adressen mehrerer Knoten.

Klicken Sie hier, um das vollständige Tutorial zu lesen

Das obige ist der detaillierte Inhalt vonDatenstrukturen in Python – Bäume. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!