() translation by (you can also view the original English article)
Bäume sind eine der am meisten verwendeten Datenstrukturen in der web-Entwicklung. Diese Aussage gilt sowohl für Entwickler und Anwender. Jeder web-Entwickler, der geschrieben hat, HTML-und lud Sie in einem web-browser geschaffen hat, ein Baum, die so genannte Document Object Model (DOM). Jeder Benutzer des Internets, die im Gegenzug Informationen über das Internet verbraucht hat, hat es in der Form eines Baumes erhalten – Dom.
Nun, hier ist der Höhepunkt: der Artikel, die Sie in diesem Moment lesen wird in Ihrem Browser als Baum dargestellt! Der Absatz, den Sie Lesen, wird dargestellt als text in einem element, das - element geschachtelt innerhalb von element, und das - element geschachtelt innerhalb eines - element.
Die Verschachtelung der Daten ist ähnlich wie ein Stammbaum. Die<html>Element ist ein Elternteil die<body>Element ist ein Kind, und die<p>Element ist ein untergeordnetes Element der<body>Element.</body></body></html> Wenn diese Analogie des Baumes scheint nützlich für Sie, dann finden Sie Trost in dem wissen, dass mehr Analogien werden verwendet, während unserer Implementierung von einem Baum.
In diesem Artikel erstellen wir eine Struktur mit zwei verschiedenen Methoden der tree-traversal: Depth-First-Search (DFS) und Breadth-First-Search (BFS). (Wenn das Wort traversal ist ungewohnt für Sie ist, sollten Sie es zu bedeuten, mit dem Besuch aller Knoten des Baums.) Diese beiden Arten der Durchquerung highlight verschiedene Möglichkeiten der Interaktion mit einem Baum; beide Reisen, darüber hinaus beinhalten die Verwendung von Datenstrukturen, die wir abgedeckt haben in dieser Serie. DFS verwendet einen Stapel und BFS eine Warteschlange, um Knoten zu besuchen. Das ist cool!
Baum (Depth-First Search und Breadth-First-Search)
In der informatik eine Baum ist eine Datenstruktur, die die Simulation von hierarchischen Daten mit den Knoten. Jeder Knoten des Baumes besitzt seine eigenen Daten und Zeiger auf andere Knoten.
Die Begriffe der Knoten und Zeiger vielleicht einige Leser, so lassen Sie Sie uns beschreiben weitere mit einer Analogie. Vergleichen wir einen Baum, um ein Organigramm. Die Karte hat eine top-level-position (root-Knoten), wie CEO. Direkt unter dieser position sind andere Positionen als vice president (VP).
Zur Darstellung dieser Beziehung, verwenden wir Pfeile, die Punkt, der CEO, ein VP. Eine position, wie der CEO, ist ein Knoten; die Beziehung, die wir erstellen, von ein CEO, ein VP ist ein Zeiger. Erstellen Sie weitere Beziehungen, die in unserem Organigramm, wir wiederholen Sie einfach diesen Vorgang—wir haben einen Knoten auf einen anderen Knoten.
Auf der konzeptionellen Ebene, ich hoffe, dass Knoten und Zeiger Sinn. Auf einer praktischen Ebene, wir können Sie nutzen-mit einem technischen Beispiel. Wir betrachten den DOM. Ein DOM ist ein - element als top-level-position (root-Knoten). Dieser Knoten verweist auf ein element und ein - element. Dieser Vorgang wird wiederholt für alle Knoten im Dom.
Eine der Schönheiten dieser Konstruktion ist die Möglichkeit der Schachtelung von Knoten: ein - element, zum Beispiel, kann viele - Elemente geschachtelt innerhalb es; darüber hinaus enthält jedes - element können Geschwister - Knoten. Das ist komisch, noch lustig und wahr!
Operationen von einem Baum
Da jeder Baum-Knoten, die einen separaten Konstruktor von einem Baum sein kann enthält, beschreiben wir den Betrieb der beiden Konstruktoren: Knoten und Baum.
Knoten
- Daten speichert einen Wert.
- parent verweist auf einen übergeordneten Knoten.
- Kinder verweist auf den nächsten Knoten in der Liste.
Baum
- _root Punkte auf der root-Knoten des Baumes.
- traverseDF(callback) durchläuft die Knoten eines Baumes mit DFS.
- traverseBF(callback) durchläuft die Knoten eines Baumes mit dem BFS.
- enthält(Daten, "traversal") sucht nach einem Knoten in einem Baum.
- add(data, toData, traverse) fügt einen Knoten zu einem Baum.
- entfernen von(Kind, Elternteil) entfernt einen Knoten in einem Baum.
Implementierung des Baumes
Nun schreiben wir den code für einen Baum!
Eigenschaften eines Knotens
Für unsere Implementierung werden wir zunächst definieren Sie eine Funktion mit dem Namen Knoten und dann einen Konstruktor namens Baum.
1 |
function Node(data) { |
2 |
this.data = data; |
3 |
this.parent = null; |
4 |
this.children = []; |
5 |
}
|
Jede Instanz von Knoten enthält drei Eigenschaften: Daten, Eltern und Kinder. Die erste Eigenschaft enthält Daten, die im Zusammenhang mit einem Knoten. Die zweite Eigenschaft, Punkte zu einem Knoten. Die Dritte Eigenschaft verweist auf viele Kinder Knoten.
Eigenschaften des Baumes
Nun definieren wir unsere Konstruktor für Baum, enthält die Node-Konstruktor in der definition:
1 |
function Tree(data) { |
2 |
var node = new Node(data); |
3 |
this._root = node; |
4 |
}
|
Baum enthält zwei Zeilen code. Die erste Zeile erzeugt eine neue Instanz von Knoten; die zweite Zeile weist die Knoten als Wurzel des Baumes.
Die Definitionen von Baum und Knoten erfordert nur wenige Zeilen code. Diese Linien sind jedoch genug, um uns zu helfen simulieren hierarchische Daten. Um diesen Punkt zu beweisen, verwenden wir einige Beispiel-Daten, die zum erstellen einer Instanz des Baumes (und, indirekt, Knoten).
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
// {data: 'CEO', parent: null, children: []}
|
4 |
tree._root; |
Dank der Existenz von Eltern und Kindern, können wir hinzufügen von Knoten als Kinder von _root und auch zuweisen _root als die Eltern von diesen Knoten. In anderen Worten, wir können simulieren die Erstellung von hierarchischen Daten.
Methoden des Baumes
Als Nächstes werden wir die folgenden fünf Methoden:
Baum
traverseDF(Rückruf)traverseBF(Rückruf)enthält(Daten, traversal)hinzufügen von(Kind, Elternteil)remove(node, parent)
Da jede Methode einen Baum, der von uns verlangt, durchqueren einen Baum, wir implementieren Sie zunächst die Methoden, die definieren, die verschiedenen Arten von Baum-traversal. (Traversierung eines Baumes ist eine formale Art zu sagen: Besuch aller Knoten eines Baumes.)
1 von 5: traverseDF(Rückruf)
Diese Methode durchläuft den Baum mit Tiefe-zuerst-Suche.
1 |
Tree.prototype.traverseDF = function(callback) { |
2 |
|
3 |
// this is a recurse and immediately-invoking function
|
4 |
(function recurse(currentNode) { |
5 |
// step 2
|
6 |
for (var i = 0, length = currentNode.children.length; i < length; i++) { |
7 |
// step 3
|
8 |
recurse(currentNode.children[i]); |
9 |
}
|
10 |
|
11 |
// step 4
|
12 |
callback(currentNode); |
13 |
|
14 |
// step 1
|
15 |
})(this._root); |
16 |
|
17 |
};
|
traverseDF(callback) hat einen parameter namens callback. Wenn es nicht klar aus dem Namen, callback wird davon ausgegangen, dass eine Funktion, welche aufgerufen wird später in traverseDF(callback).
Der Körper traverseDF(callback) enthält noch eine Funktion namens Rekursion. Diese Funktion ist eine rekursive Funktion! In anderen Worten, es ist selbst aufrufen und selbst beendet. Mit Hilfe der genannten Schritte in die Kommentare recurse, ich werde beschreiben den Allgemeinen Prozess, der Rekursion verwendet, um die traverse die gesamte Struktur.
Hier sind die Schritte:
- Sofort aufrufen Rekursion mit den Stammknoten einer Struktur als argument. In diesem moment, currentNode Punkte auf den aktuellen Knoten.
- Geben Sie eine for-Schleife und Durchlaufen einmal für jedes Kind von currentNode, beginnend mit dem ersten Kind.
- Im Rumpf der for-Schleife aufrufen, recurse, die ein Kind currentNode. Die genaue Kindes hängt von der aktuellen iteration der for-Schleife.
- Wenn currentNode nicht mehr Kinder hat, verlassen wir die for-Schleife und ruft die callback-wir übergeben bei der Anrufung der traverseDF(callback).
Die Schritte 2 (self-terminating), 3 (selbst-aufrufen), und 4 (callback) wiederholen, bis wir Durchlaufen jeden Knoten des Baumes.
Rekursion ist ein sehr hartes Thema, um zu lehren, und erfordert einen ganzen Artikel angemessen zu erklären. Seit der Erklärung der Rekursion ist nicht der Fokus dieses Artikels liegt der Schwerpunkt der Implementierung einer Baum—ich werde vorschlagen, dass jeder Leser fehlt ein gutes Verständnis der Rekursion die folgenden zwei Dinge.
Zuerst, experimentieren Sie mit unseren aktuellen Implementierung von traverseDF(callback) und versuchen Sie, zu einem gewissen Grad verstehen wie es funktioniert. Zweitens, wenn Sie wollen, dass ich einen Artikel schreiben über Rekursion, dann bitte in die Kommentare dieses Artikels.
Das folgende Beispiel veranschaulicht, wie ein Baum traversiert werden mit traverseDF(callback). Zum traversieren eines Baumes, ich werde eines erstellen in dem folgenden Beispiel. Der Ansatz, dass ich in diesem moment nicht ideal, aber es funktioniert. Ein besserer Ansatz wäre die Verwendung von add(value), mit denen wir die Umsetzung in Schritt 4 von 5.
1 |
var tree = new Tree('one'); |
2 |
|
3 |
tree._root.children.push(new Node('two')); |
4 |
tree._root.children[0].parent = tree; |
5 |
|
6 |
tree._root.children.push(new Node('three')); |
7 |
tree._root.children[1].parent = tree; |
8 |
|
9 |
tree._root.children.push(new Node('four')); |
10 |
tree._root.children[2].parent = tree; |
11 |
|
12 |
tree._root.children[0].children.push(new Node('five')); |
13 |
tree._root.children[0].children[0].parent = tree._root.children[0]; |
14 |
|
15 |
tree._root.children[0].children.push(new Node('six')); |
16 |
tree._root.children[0].children[1].parent = tree._root.children[0]; |
17 |
|
18 |
tree._root.children[2].children.push(new Node('seven')); |
19 |
tree._root.children[2].children[0].parent = tree._root.children[2]; |
20 |
|
21 |
/*
|
22 |
|
23 |
creates this tree
|
24 |
|
25 |
one
|
26 |
├── two
|
27 |
│ ├── five
|
28 |
│ └── six
|
29 |
├── three
|
30 |
└── four
|
31 |
└── seven
|
32 |
|
33 |
*/
|
Nun, lassen Sie uns invoke traverseDF(callback).
1 |
tree.traverseDF(function(node) { |
2 |
console.log(node.data) |
3 |
});
|
4 |
|
5 |
/*
|
6 |
|
7 |
logs the following strings to the console
|
8 |
|
9 |
'five'
|
10 |
'six'
|
11 |
'two'
|
12 |
'three'
|
13 |
'seven'
|
14 |
'four'
|
15 |
'one'
|
16 |
|
17 |
*/
|
2 von 5: traverseBF(Rückruf)
Diese Methode verwendet der Breite-zuerst-Suche zum traversieren eines Baumes.
Der Unterschied zwischen depth-first search und breadth-first-Suche beinhaltet die Sequenz, die Knoten des Baumes besuchen. Um diesen Punkt zu veranschaulichen, lassen Sie uns die Struktur, die wir geschaffen aus traverseDF(callback).
1 |
/*
|
2 |
|
3 |
tree
|
4 |
|
5 |
one (depth: 0)
|
6 |
├── two (depth: 1)
|
7 |
│ ├── five (depth: 2)
|
8 |
│ └── six (depth: 2)
|
9 |
├── three (depth: 1)
|
10 |
└── four (depth: 1)
|
11 |
└── seven (depth: 2)
|
12 |
|
13 |
*/
|
Nun, lassen Sie uns passieren traverseBF(callback) die gleichen callback, die wir für traverseDF(callback).
1 |
tree.traverseBF(function(node) { |
2 |
console.log(node.data) |
3 |
});
|
4 |
|
5 |
/*
|
6 |
|
7 |
logs the following strings to the console
|
8 |
|
9 |
'one'
|
10 |
'two'
|
11 |
'three'
|
12 |
'four'
|
13 |
'five'
|
14 |
'six'
|
15 |
'seven'
|
16 |
|
17 |
*/
|
Die logs von der Konsole und der Grafik von unserem Baum zeigen ein Muster über die Breite-zuerst-Suche. Beginnen Sie mit dem root-Knoten; dann fahren Sie eine Tiefe und besuchen jeden Knoten in die Tiefe von Links nach rechts. Wiederholen Sie diesen Vorgang, bis es keine mehr Tiefe zu Reisen.
Da haben wir ein konzeptionelles Modell der Breite-zuerst-Suche, lassen Sie uns jetzt implementieren Sie den code, das würde unserem Beispiel der Arbeit.
1 |
Tree.prototype.traverseBF = function(callback) { |
2 |
var queue = new Queue(); |
3 |
|
4 |
queue.enqueue(this._root); |
5 |
|
6 |
currentTree = queue.dequeue(); |
7 |
|
8 |
while(currentTree){ |
9 |
for (var i = 0, length = currentTree.children.length; i < length; i++) { |
10 |
queue.enqueue(currentTree.children[i]); |
11 |
}
|
12 |
|
13 |
callback(currentTree); |
14 |
currentTree = queue.dequeue(); |
15 |
}
|
16 |
};
|
Unsere definition von traverseBF(callback) enthält eine Menge von Logik. Aus diesem Grund werde ich erklären, die Logik in überschaubaren Schritten:
- Erstellen Sie eine Instanz von Queue.
- Fügen Sie die Knoten, die Sie aufgerufen traverseBF(callback) auf die Instanz der Warteschlange.
- Deklarieren Sie eine variable namens currentNode und initialisieren Sie es auf den Knoten, die wir gerade Hinzugefügt haben, um unsere Warteschlange.
- Während currentNode Punkte zu einem Knoten ausführen, wird der code innerhalb der while-Schleife.
- Verwenden Sie eine for-Schleife für die Iteration auf die Kinder von currentNode.
- Im Rumpf der for-Schleife, fügen Sie jedes Kind in der Warteschlange.
- Nehmen currentNode und übergeben Sie Sie als argument an den callback.
- Zuweisen currentNode zu den Knoten aus der Warteschlange entfernt.
- Bis currentNode nicht zeigen Sie auf einen Knoten—jeder Knoten im Baum besucht wurde—wiederholen Sie die Schritte 4 bis 8.
3 von 5: enthält(callback-traversal)
Definieren wir eine Methode, die es uns ermöglichen, nach einem bestimmten Wert in den Baum. Verwenden Sie unsere Methoden der tree-traversal habe ich definiert enthält(callback", "traversal") übernimmt zwei Argumente: die Daten zu suchen und die Art der Traversierung.
1 |
Tree.prototype.contains = function(callback, traversal) { |
2 |
traversal.call(this, callback); |
3 |
};
|
Im Körper enthält(callback", "traversal"), verwenden wir eine Methode namens Aufruf zu gehen und Rückruf. Das erste argument bindet traversal zu dem Baum, der aufgerufen wird, enthält(callback", "traversal"); das zweite argument ist eine Funktion, die aufgerufen wird, auf jedem Knoten in unserem Baum.
Stell dir vor, wir wollen log auf der Konsole alle Knoten, die Daten enthalten, die mit einer ungeraden Zahl und Durchlaufen jeden Knoten in unserem Baum mit dem BFS. Dies ist der code, den wir schreiben würden:
1 |
// tree is an example of a root node
|
2 |
tree.contains(function(node){ |
3 |
if (node.data === 'two') { |
4 |
console.log(node); |
5 |
}
|
6 |
}, tree.traverseBF); |
4 von 5: - add(data, toData, traversal)
Wir haben nun eine Methode für die Suche nach einem bestimmten Knoten in unserem Baum. Lassen Sie uns nun eine Methode definieren, die uns ermöglichen wird, fügen Sie einen Knoten zu einem bestimmten Knoten.
1 |
Tree.prototype.add = function(data, toData, traversal) { |
2 |
var child = new Node(data), |
3 |
parent = null, |
4 |
callback = function(node) { |
5 |
if (node.data === toData) { |
6 |
parent = node; |
7 |
}
|
8 |
};
|
9 |
|
10 |
this.contains(callback, traversal); |
11 |
|
12 |
if (parent) { |
13 |
parent.children.push(child); |
14 |
child.parent = parent; |
15 |
} else { |
16 |
throw new Error('Cannot add node to a non-existent parent.'); |
17 |
}
|
18 |
};
|
add(data, toData", "traversal") definiert drei Parameter. Der erste parameter, der Daten, wird verwendet, um erstellen Sie eine neue Instanz von Knoten. Der zweite parameter, toData, vergleichen Sie gegen jeden Knoten in einem Baum. Der Dritte parameter traversal, ist die Art der Baum-Traversierung in dieser Methode verwendet.
Im Körper von add(data, toData, traversal), deklarieren wir drei Variablen. Die erste variable, Kind, initialisiert eine neue Instanz von Knoten. Die zweite variable, ein Elternteil, wird mit null initialisiert, aber es wird sich später zeigen Sie auf einen beliebigen Knoten in einem Baum, der mit dem Wert von toData. Die Umverteilung von Eltern geschieht, in der die Dritte variable, die wir erklären, was ist Rückruf.
callback ist eine Funktion, vergleicht toData zu jedem Knoten der data-Eigenschaft. Wenn die if-Anweisung als true ausgewertet wird, dann Elternteil zugeordnet, der Knoten abgestimmt, dass der Vergleich in der if-Anweisung.
Der eigentliche Vergleich von jedem Knoten zu toData tritt in enthält(callback", "traversal"). Die Art der Traversierung und callback übergeben werden müssen als Argumente enthält(callback", "traversal").
Schließlich, wenn der Elternteil existiert in dem Baum, wir schieben Kind zu Elternteil.Kinder; wir vergeben auch Eltern der Elternteil des Kindes. Sonst werfen wir einen Fehler aus.
Wir verwenden Sie(Daten, toData", "traversal") in einem Beispiel:
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
tree.add('VP of Happiness', 'CEO', tree.traverseBF); |
4 |
|
5 |
/*
|
6 |
|
7 |
our tree
|
8 |
|
9 |
'CEO'
|
10 |
└── 'VP of Happiness'
|
11 |
|
12 |
*/
|
Hier ist ein komplexeres Beispiel für das hinzufügen(addData, toData", "traversal"):
1 |
var tree = new Tree('CEO'); |
2 |
|
3 |
tree.add('VP of Happiness', 'CEO', tree.traverseBF); |
4 |
tree.add('VP of Finance', 'CEO', tree.traverseBF); |
5 |
tree.add('VP of Sadness', 'CEO', tree.traverseBF); |
6 |
|
7 |
tree.add('Director of Puppies', 'VP of Finance', tree.traverseBF); |
8 |
tree.add('Manager of Puppies', 'Director of Puppies', tree.traverseBF); |
9 |
|
10 |
/*
|
11 |
|
12 |
tree
|
13 |
|
14 |
'CEO'
|
15 |
├── 'VP of Happiness'
|
16 |
├── 'VP of Finance'
|
17 |
│ ├── 'Director of Puppies'
|
18 |
│ └── 'Manager of Puppies'
|
19 |
└── 'VP of Sadness'
|
20 |
|
21 |
*/
|
5 von 5: entfernen(Daten, fromData, traversal)
Zu einer vollständigen Umsetzung von Baum -, wir fügen Sie eine Methode namens remove(Daten, fromData, traversal). Ähnlich wie das entfernen eines Knotens aus dem DOM, wird diese Methode das entfernen eines Knotens und all seiner Kinder.
1 |
Tree.prototype.remove = function(data, fromData, traversal) { |
2 |
var tree = this, |
3 |
parent = null, |
4 |
childToRemove = null, |
5 |
index; |
6 |
|
7 |
var callback = function(node) { |
8 |
if (node.data === fromData) { |
9 |
parent = node; |
10 |
}
|
11 |
};
|
12 |
|
13 |
this.contains(callback, traversal); |
14 |
|
15 |
if (parent) { |
16 |
index = findIndex(parent.children, data); |
17 |
|
18 |
if (index === undefined) { |
19 |
throw new Error('Node to remove does not exist.'); |
20 |
} else { |
21 |
childToRemove = parent.children.splice(index, 1); |
22 |
}
|
23 |
} else { |
24 |
throw new Error('Parent does not exist.'); |
25 |
}
|
26 |
|
27 |
return childToRemove; |
28 |
};
|
Ähnlich wie add(data, toData, traversal), entfernen durchsucht einen Baum zu finden, ein Knoten, enthält das zweite argument, das ist jetzt fromData aufbewahrt. Wenn dieser Knoten gefunden wird, dann die übergeordneten Punkte.
In diesem moment erreichen wir unseren ersten if-Anweisung. Wenn der Elternteil nicht vorhanden ist, werfen wir einen Fehler aus. Wenn der Elternteil vorhanden ist, rufen wir findIndex() mit Elternteil.Kinder-und die Daten, die wir entfernen wollen, aus der Kinder-Knoten des übergeordneten. (findIndex() ist eine Hilfsmethode, die ich unten definiert.)
1 |
function findIndex(arr, data) { |
2 |
var index; |
3 |
|
4 |
for (var i = 0; i < arr.length; i++) { |
5 |
if (arr[i].data === data) { |
6 |
index = i; |
7 |
}
|
8 |
}
|
9 |
|
10 |
return index; |
11 |
}
|
Innerhalb findIndex(), die folgende Logik Auftritt. Wenn einer der Knoten im übergeordneten.Kinder enthalten, die Daten entsprechen Daten, die variable index zugeordnet ist, eine ganze Zahl. Wenn keines der Kinder die Daten Eigenschaften übereinstimmen, die Daten, dann index behält seinen default-Wert undefined. In der letzten Zeile von findIndex(), wir-return-index.
Wir kehren nun zu entfernen(Daten, fromData, traversal). Wenn der index nicht definiert ist, wird ein Fehler geworfen. Wenn der index definiert ist, verwenden wir es, um splice die Knoten, die wir entfernen wollen aus den Kindern von Eltern, die wir auch zuordnen entfernt Kind childToRemove.
Schließlich kehren wir childToRemove.
Vollständige Implementierung des Baumes
Unsere Implementierung des Baumes abgeschlossen ist. Werfen Sie einen Blick—wir haben viel geschafft:
1 |
function Node(data) { |
2 |
this.data = data; |
3 |
this.parent = null; |
4 |
this.children = []; |
5 |
}
|
6 |
|
7 |
function Tree(data) { |
8 |
var node = new Node(data); |
9 |
this._root = node; |
10 |
}
|
11 |
|
12 |
Tree.prototype.traverseDF = function(callback) { |
13 |
|
14 |
// this is a recurse and immediately-invoking function
|
15 |
(function recurse(currentNode) { |
16 |
// step 2
|
17 |
for (var i = 0, length = currentNode.children.length; i < length; i++) { |
18 |
// step 3
|
19 |
recurse(currentNode.children[i]); |
20 |
}
|
21 |
|
22 |
// step 4
|
23 |
callback(currentNode); |
24 |
|
25 |
// step 1
|
26 |
})(this._root); |
27 |
|
28 |
};
|
29 |
|
30 |
Tree.prototype.traverseBF = function(callback) { |
31 |
var queue = new Queue(); |
32 |
|
33 |
queue.enqueue(this._root); |
34 |
|
35 |
currentTree = queue.dequeue(); |
36 |
|
37 |
while(currentTree){ |
38 |
for (var i = 0, length = currentTree.children.length; i < length; i++) { |
39 |
queue.enqueue(currentTree.children[i]); |
40 |
}
|
41 |
|
42 |
callback(currentTree); |
43 |
currentTree = queue.dequeue(); |
44 |
}
|
45 |
};
|
46 |
|
47 |
Tree.prototype.contains = function(callback, traversal) { |
48 |
traversal.call(this, callback); |
49 |
};
|
50 |
|
51 |
Tree.prototype.add = function(data, toData, traversal) { |
52 |
var child = new Node(data), |
53 |
parent = null, |
54 |
callback = function(node) { |
55 |
if (node.data === toData) { |
56 |
parent = node; |
57 |
}
|
58 |
};
|
59 |
|
60 |
this.contains(callback, traversal); |
61 |
|
62 |
if (parent) { |
63 |
parent.children.push(child); |
64 |
child.parent = parent; |
65 |
} else { |
66 |
throw new Error('Cannot add node to a non-existent parent.'); |
67 |
}
|
68 |
};
|
69 |
|
70 |
Tree.prototype.remove = function(data, fromData, traversal) { |
71 |
var tree = this, |
72 |
parent = null, |
73 |
childToRemove = null, |
74 |
index; |
75 |
|
76 |
var callback = function(node) { |
77 |
if (node.data === fromData) { |
78 |
parent = node; |
79 |
}
|
80 |
};
|
81 |
|
82 |
this.contains(callback, traversal); |
83 |
|
84 |
if (parent) { |
85 |
index = findIndex(parent.children, data); |
86 |
|
87 |
if (index === undefined) { |
88 |
throw new Error('Node to remove does not exist.'); |
89 |
} else { |
90 |
childToRemove = parent.children.splice(index, 1); |
91 |
}
|
92 |
} else { |
93 |
throw new Error('Parent does not exist.'); |
94 |
}
|
95 |
|
96 |
return childToRemove; |
97 |
};
|
98 |
|
99 |
function findIndex(arr, data) { |
100 |
var index; |
101 |
|
102 |
for (var i = 0; i < arr.length; i++) { |
103 |
if (arr[i].data === data) { |
104 |
index = i; |
105 |
}
|
106 |
}
|
107 |
|
108 |
return index; |
109 |
}
|
Fazit
Bäume simulieren, hierarchische Daten. Viel von der Welt um uns herum ähnelt diese Art der Hierarchie, wie web-Seiten und unsere Familien. Jedes mal, wenn Sie sich in der Notwendigkeit der Strukturierung von Daten mit der Hierarchie, sollten Sie erwägen, ein Baum.
