[JAVA] Halbierungsbaum-Memorandum für Anfänger (1)

Ich habe einen Kommentar zum Halbbaum für einen bestimmten Job geschrieben, aber es wurde aus verschiedenen Gründen beschlossen, ihn nicht zu verwenden. Es ist ein kindischer Artikel, aber ich habe ihn sorgfältig geschrieben. Bitte lassen Sie mich hier einen Gedenkgottesdienst abhalten.

Alle diese Artikel heißen "Digital Series 10-Algorithmen und Datenstrukturen, die mit der Zukunft verbunden sind" (Betreuer: Shojiro Nishio, Autoren: Takahiro Hara, Satoshi Mizuta, Takenao Okawa Herausgeber: Mitsuaki Nanjo Herausgeber: Kyoritsu Publishing Co., Ltd.) Ich beziehe mich auf das Buch. Es ist ein gutes Buch für Anfänger mit zahlreichen Abbildungen und Pseudocodes. Bitte lesen Sie es, wenn Sie interessiert sind.

Obwohl es als "für Anfänger" gekennzeichnet ist, ist dieser Artikel ein unfreundlicher Artikel ohne Illustrationen. Wenn Sie also wirklich eine erfrischende Vorstellung von Gabelung haben, können Sie ihn lesen. Wenn Sie diesen Artikel lesen und nicht verstehen, was er bedeutet, ist es nicht Ihre Schuld, sondern die Schuld des Autors.

Was ist ein gegabelter Baum?

Eine Baumstruktur ist eine der gleichen Datenstrukturen wie ein Stapel oder eine Warteschlange. Zum Beispiel hat das Organigramm eines Unternehmens eine feine Holzstruktur. Die Positionen des Präsidenten, des Designmanagers, des Serveringenieurs usw. werden als Knoten bezeichnet. Die Linie, die jeden Knoten verbindet, wird als Kante bezeichnet. Die Knoten an beiden Enden der Seite werden oben als Eltern und unten als Kind bezeichnet. Mit anderen Worten, der Designmanager ist das übergeordnete Element des Designers, und der Designer ist das untergeordnete Element des Designmanagers. Wie der Präsident wird der oberste Knoten als Wurzel bezeichnet. Ein Knoten, der keine untergeordneten Knoten hat, z. B. ein Designer oder Ingenieur, wird als Blatt bezeichnet. Eine Baumstruktur, in der jeder Knoten zwei oder weniger untergeordnete Knoten hat, wird als dichotomisierter Baum bezeichnet. Mit anderen Worten, ein dichotomisierter Baum besteht aus einer Kombination von Knoten und Seiten.

Implementierungsbeispiel

C++

BinaryTree.cpp

#include <iostream>
using namespace std;

int main()
{
	string binaryTree[7] = {"Präsident", "Design Manager", "Ingenieur-Manager",
												  "Designer", "", "Serveringenieur", "Infrastrukturingenieur"};

	//Elternteil ist 0
	cout << binaryTree[0] << endl;
	//Die Kinder des Engineer Managers (Index 2) sind Server- und Infrastrukturingenieure.
	cout << binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2] << endl;
}

Java

BinaryTree.java

public class BinaryTree {
	public static void main(String[] args) {
		String[] binaryTree = {"Präsident", "Design Manager", "Ingenieur-Manager",
													 "Designer", "", "Serveringenieur", "Infrastrukturingenieur"};

		//Elternteil ist 0
		System.out.println(binaryTree[0]);
		//Die Kinder des Engineer Managers (Index 2) sind Server- und Infrastrukturingenieure.
		System.out.println(binaryTree[2 * 2 + 1] + ", " + binaryTree[2 * 2 + 2]);
	}
}

Erläuterung zur Implementierung

Eine Dichotomie kann durch Verwendung eines Arrays erreicht werden. Formal wird der Stammindex zuerst auf 0 gesetzt. Wenn für andere Knoten als die Wurzel der übergeordnete Index k ist, beträgt der linke untergeordnete Index 2k + 1 und der rechte untergeordnete Index 2k + 2. Wenn Sie ein Kind haben, machen Sie es zum linken und zum rechten Kind leer. Nachdem jedem Knoten ein Index zugewiesen wurde, werden die Daten des Kontakts gemäß dem Index im Array gespeichert.

Anwendungsbeispiel

Die Baumstruktur ist eine Datenstruktur, die geeignet ist, wenn eine Ordnungsbeziehung wie Hierarchie und Größe zwischen Daten besteht. Da die Daten regelmäßig angeordnet werden, können Sie schnell suchen, wenn Sie im Voraus entscheiden, wie sie angeordnet werden sollen. Es gibt Haufenbäume und dichotomisierte Bäume als Dichotomien, die diese Eigenschaft nutzen.

Vorsichtsmaßnahmen für die Anwendung

Wie ich bereits erwähnt habe, funktioniert es gut für geordnete Daten, aber umgekehrt ist es für ungeordnete Daten machtlos. Selbst wenn eine Ordnungsbeziehung besteht und die Eingaben in dieser Reihenfolge erfolgen, wird ein baumförmiger Baum mit nur dem linken oder rechten Kind erstellt. Wenn Sie die Implementierung mit dem zuvor beschriebenen Array verwenden, müssen Sie außerdem leeren Kindern untergeordneten Speicher zuweisen, was verschwenderisch ist. Es ist ein Merkmal von Arrays, dass Speicher für spärliche Daten verschwendet wird. Mit anderen Worten, die Array-basierte Implementierung eignet sich für dichte Dichotomien ohne leere untergeordnete Elemente in der Mitte. Ein dichter gegabelter Baum wird insbesondere als vollständig dichotomisierter Baum bezeichnet. Um genau zu sein, wird ein dichotomisierter Baum, bei dem alle Blätter linksbündig sind, ohne Leerzeichen an den Knoten, die keine Blätter sind, als vollständiger dichotomisierter Baum bezeichnet. Eine Dichotomie, die keine vollständige Dichotomie ist, kann mithilfe von Klassen realisiert werden, um Speicherverschwendung zu vermeiden.

Teil 2 ist hier