Es gibt mehrere Möglichkeiten, einen Binärbaum zu implementieren

Es gibt zwei Möglichkeiten, Binärbäume zu implementieren: 1. Sequentielle Speicherung, die sich auf die Verwendung einer Sequenztabelle zum Speichern von Binärbäumen bezieht und nur auf vollständige Binärbäume anwendbar ist; 2. Verkettete Speicherung, wenn Speichern von Binärbäumen im Link-Modus. Zusätzlich zum Speichern der Daten des Knotens selbst sollte ein Knoten auch zwei Zeigerfelder lchild und rchild festlegen.

Binärbaum

Fünf Grundformen: leerer Binärbaum, Binärbaum mit nur Wurzelknoten, Binärbaum mit nur Wurzelknoten Binärbaum mit Knoten und linkem Teilbaum TL, Binärbaum mit nur Wurzelknoten und rechtem Teilbaum TR, Binärbaum mit Wurzelknoten, linkem Teilbaum TL und rechtem Teilbaum TR

Andere Binärbäume: schief Binärbaum, vollständiger Binärbaum, perfekter Binärbaum

Implementierungsmethode: sequentielle Speicherung, verkettete Speicherung

Sequentielle Speicherung von Binärbäumen bezieht sich auf die Verwendung sequentieller Tabellen (Arrays). Binärbäume speichern. Es ist zu beachten, dass die sequentielle Speicherung nur für vollständige Binärbäume gilt. Mit anderen Worten: Mit sequentiellen Tabellen können nur vollständige Binärbäume gespeichert werden. Wenn wir also gewöhnliche Binärbäume sequentiell speichern möchten, müssen wir den gewöhnlichen Binärbaum im Voraus in einen vollständigen Binärbaum umwandeln.

Jeder Knoten eines Binärbaums hat höchstens zwei Kinder. Beim Speichern eines Binärbaums im Link-Modus sollte jeder Knoten zusätzlich zum Speichern der Daten des Knotens selbst auch zwei Zeigerfelder lchild und rchild festlegen, die auf das linke bzw. rechte untergeordnete Element des Knotens zeigen.

Das obige ist der detaillierte Inhalt vonEs gibt mehrere Möglichkeiten, einen Binärbaum zu implementieren. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!