Iteratoren über Versuche in Java - Java, Iterator, Trie

Ich versuche gerade, eine trie-Datenstruktur für Ganzzahltupel zu implementieren. Und wie folgt umgesetzt:

import java.util.ArrayList;

public class TrieNode {

int num;
ArrayList<TrieNode> links;
boolean endOfTuple;

public TrieNode(int num)
{
this.num = num;
links = new ArrayList<TrieNode>();
this.endOfTuple = false;
}

}

Ich habe dann eine Trie-Klasse wie folgt:

public class Trie {

TrieNode root;

public Trie() {
root = new TrieNode(-1);
}
public void insertTuple(int[] tuple)
{
int l = tuple.length;


TrieNode curNode = root;

for (int i = 0; i < l; i++)
{
TrieNode node = new TrieNode(tuple[i]);

if(!curNode.links.contains(node)){
curNode.links.add(node);
}
curNode = curNode.links.get(curNode.links.indexOf(node));
}
curNode.endOfTuple = true;
}
}

Ich kann diesem Trie Werte hinzufügen, aber ich muss es seinin der Lage, darüber zu iterieren und fragte mich, wie ich das tun könnte? Zum Beispiel, wenn ich den Baum mit einem Iterator drucken wollte ... Jede Hilfe wird großartig sein ...

Antworten:

Alles, was Sie für einen Interator brauchen, ist die Implementierung des Iterator Schnittstelle, die nur von Ihnen angegeben werden muss boolean hasNext() und Integer next(). Die Frage ist also: Wie stellen Sie eine Position in Ihrem Trie dar, so dass es möglich ist, (a) den dieser Position zugeordneten Wert abzurufen und (b) die "nächste" Position bei einer aktuellen Position herauszufinden?

Ich werde keine eigentliche Lösung veröffentlichenIch bin nicht sicher, ob dies Hausaufgaben sind. Aber bedenken Sie: Sie können eine "aktuelle Position" in Ihrem Trie darstellen, indem Sie einfach einen bestimmten Trie-Knoten und den Pfad der Trie-Knoten auswählen, die Sie zum Erreichen dieser Position verwendet haben "nächstes" Element rekursiv: Wenn das aktuelle Element ein Knoten ist, der untergeordnete Elemente hat, suchen Sie das erste untergeordnete Element endOfTuple ist true. Wenn das aktuelle Element keine Kinder hat, gehen Sie zu seinem übergeordneten Element und fahren Sie mit dem nächsten untergeordneten Element dieses Elternteils fort. Wenn dieses Elternteil keine nächsten Kinder hat, dann geh los es ist das nächste Kind der Eltern usw.