Eine kurze Diskussion über einen effizienten Algorithmus zum Erstellen von Baumstrukturen in JavaScript

Einführung

Wir stoßen häufig auf baumartige Datenstrukturen, beispielsweise bei Organisationshierarchien, Provinzen, Städten, Landkreisen oder Tier- und Pflanzenklassifikationen. Nachfolgend sehen Sie ein Beispiel für eine Baumstruktur:

In praktischen Anwendungen ist es üblich, diese Informationen in der folgenden Struktur zu speichern, insbesondere wenn eine Eins-zu-viele-Beziehung zwischen übergeordneten und untergeordneten Knoten besteht:

const Daten = [
  { id: 56, parentId: 62 },
  { id: 81, parentId: 80 },
  { id: 74, parentId: null },
  { id: 76, parentId: 80 },
  { id: 63, parentId: 62 },
  { id: 80, parentId: 86 },
  { id: 87, parentId: 86 },
  { id: 62, parentId: 74 },
  { id: 86, parentId: 74 },
];

Wie konvertieren wir also dieses Objektarrayformat in ein hierarchisches Baumformat? Tatsächlich ist die Implementierung sehr einfach, wenn man die Eigenschaften von JavaScript-Objektreferenzen nutzt. Dies kann in O(n) Zeit ohne Rekursion durchgeführt werden.

der Begriff

Der Einfachheit halber definieren wir zunächst einige Begriffe. Wir nennen jedes Element im Array (also jeden Kreis im Baumdiagramm) einen „Knoten“. Ein Knoten kann der „übergeordnete Knoten“ mehrerer Knoten oder der „untergeordnete Knoten“ eines bestimmten Knotens sein. In der obigen Abbildung ist Knoten 86 der „übergeordnete Knoten“ von Knoten 80 und Knoten 87, und Knoten 86 ist der untergeordnete Knoten von Knoten 74. Der oberste Knoten des Baums wird als „Wurzelknoten“ bezeichnet.

Ideen

Um die Baumstruktur aufzubauen, benötigen wir:

• Durchlaufen des Datenarrays
• Suchen Sie das übergeordnete Element des aktuellen Elements
• Fügen Sie im übergeordneten Elementobjekt einen Verweis auf das untergeordnete Element hinzu
• Wenn ein Element keinen übergeordneten Knoten hat, betrachten wir es als den Stammknoten des Baums.

Wir können sehen, dass Referenzen im Objektbaum gespeichert sind, weshalb wir diese Aufgabe in O(n) Zeit erledigen können!

Erstellen einer ID-Array-Indexzuordnungsbeziehung

Obwohl dies nicht erforderlich ist, kann uns diese Zuordnungsbeziehung dabei helfen, den Speicherort des Elements schnell zu finden und das Auffinden des Verweises auf das übergeordnete Element zu erleichtern.

const idMapping = data.reduce((acc, el, i) => {
  acc[el.id] = i;
  Rückgabe gem.
}, {});

Die Zuordnungsergebnisse sind wie folgt und Sie werden später sehen, wie nützlich sie sind:

{

56: 0,

62: 7,

63: 4,

74: 2,

76: 3,

80: 5,

81: 1,

86: 8,

87: 6,

};

Aufbau einer Baumstruktur

Jetzt beginnen wir mit dem Aufbau dieser Baumstruktur. Iterieren Sie durch das Objekt-Array, suchen Sie das übergeordnete Objekt jedes Elements und fügen Sie dann eine Referenz auf das Element hinzu. Jetzt sollten Sie sehen, wie praktisch dieses idMapping zum Lokalisieren von Elementen ist (konstante Zeit).

wurzeln lassen;
data.forEach(el => {
  // Bestimme den Stammknoten, wenn (el.parentId === null) {
    Wurzel = el;
    zurückkehren;
  }
  //Verwende die Zuordnungstabelle, um das übergeordnete Element zu finden const parentEl = data[idMapping[el.parentId]];
  // Füge das aktuelle Element dem „children“-Array des übergeordneten Elements hinzu parentEl.children = [...(parentEl.children || []), el];
});

Erledigt! Verwenden Sie console.log, um root auszudrucken und Folgendes anzuzeigen:

Konsole.log(Root);

{

ID: 74,

parentId: null,

Kinder: [

{

ID: 62,

Eltern-ID: 74,

Kinder: [{ id: 56, parentId: 62 }, { id: 63, parentId: 62 }],

},

{

ID: 86,

Eltern-ID: 74,

Kinder: [

{

ID: 80,

übergeordnete ID: 86,

Kinder: [{ id: 81, parentId: 80 }, { id: 76, parentId: 80 }],

},

{ id: 87, parentId: 86 },

],

},

],

};

Prinzip

Warum ist das möglich? Dies liegt daran, dass jedes Element im Datenarray ein Verweis auf ein Objekt im Speicher ist, die Variable el in der forEach-Schleife tatsächlich auf ein Objekt im Speicher verweist und parentEl ebenfalls auf ein Objekt verweist.

Wenn ein Objekt im Speicher auf ein untergeordnetes Array verweist, können diese untergeordneten Elemente auch auf ihre eigenen untergeordneten Elementarrays verweisen. Diese Zuordnungen werden alle durch Referenzen vervollständigt.

Zusammenfassen

Objektreferenzen sind eines der grundlegendsten Konzepte in JavaScript und erfordern mehr Lernen und Verständnis. Wenn Sie dieses Konzept wirklich verstanden haben, können Sie knifflige Fehler vermeiden und relativ einfache Lösungen für scheinbar komplexe Probleme finden.

Oben finden Sie eine kurze Erläuterung der Details eines effizienten Algorithmus zum Erstellen von Baumstrukturen in JavaScript. Weitere Informationen zu JavaScript-Algorithmen zum Erstellen von Baumstrukturen finden Sie in den anderen verwandten Artikeln auf 123WORDPRESS.COM!