Iteratory over Tries w Javie - java, iterator, trie

Obecnie próbuję zaimplementować strukturę danych trie dla krotek całkowitych. I wdrożyłem w następujący sposób:

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;
}

}

Następnie mam klasę trie w następujący sposób:

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;
}
}

Mogę dodać wartości do tego trie, ale muszęmogłem to powtórzyć i zastanawiałem się, jak to zrobić? Na przykład, jeśli chciałbym wydrukować drzewo za pomocą iteratora ... Każda pomoc będzie świetna ...

Odpowiedzi:

Wszystko czego potrzebujesz dla interatora to wdrożenie Iterator interfejs, który wymaga tylko podania boolean hasNext() i Integer next(). Pytanie, które należy zadać, to: jak reprezentują pozycję w twoim trie, tak że możliwe jest (a) pobranie wartości związanej z tą pozycją i (b) ustalenie „następnej” pozycji, biorąc pod uwagę bieżącą pozycję?

Nie będę publikować rzeczywistego rozwiązaniaponieważ nie jestem pewien, czy jest to praca domowa. Ale zastanów się: możesz przedstawić „aktualną pozycję” w swoim trie, wybierając konkretny węzeł trie i ścieżkę węzłów trie, do których do niego dotarłeś. Następnie możesz obliczyć „następny” element rekurencyjnie: jeśli bieżący element jest węzłem, który ma dzieci, to znajdź pierwsze dziecko, dla którego endOfTuple jest true. Jeśli bieżący element nie ma dzieci, przejdź do jego rodzica i przejdź do następnego dziecka tego rodzica. Jeśli ten rodzic nie ma następnych dzieci, to idź jego następne dziecko rodzica itp.