Iterators over Tries en Java - java, iterator, trie

Actualmente estoy tratando de implementar una estructura de datos trie para tuplas enteras. Y se han implementado de la siguiente manera:

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

}

Entonces tengo una clase de trie como sigue:

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

Puedo agregar valores a este trie, pero necesito sercapaz de iterar sobre esto y me preguntaba cómo podría hacer esto? Por ejemplo, si quisiera imprimir el árbol usando un iterador ... Cualquier ayuda será excelente ...

Respuestas

Todo lo que necesitas para un interator es implementar el Iterator interfaz, que solo requiere que usted suministre boolean hasNext() y Integer next(). Así que la pregunta a hacer es: ¿Cómo representar una posición en su lista, de modo que sea posible (a) obtener el valor asociado con esa posición, y (b) averiguar la "siguiente" posición dada una actual?

Me abstendré de publicar una solución realya que no estoy seguro de si esto es tarea, pero considere: puede representar una "posición actual" en su trie simplemente seleccionando un nodo trie particular y la ruta de los nodos trie que usó para alcanzarlo. Luego puede calcular el "siguiente" elemento recursivamente: si el elemento actual es un nodo que tiene hijos, busque el primer hijo para el que endOfTuple es true. Si el elemento actual no tiene hijos, vaya a su padre y avance al siguiente hijo de ese padre. Si ese padre no tiene hijos próximos, entonces ve sus el próximo hijo de los padres, etc.