Java TreeMap opções de classificação?
-
22-07-2019 - |
Pergunta
Eu tenho dito que o TreeMap classe java usa uma implementação de uma árvore RB. Se este for o caso, como se faz um inorder, pré-venda e pós-ordem de árvores caminhada em um TreeMap?
Ou isso é não é possível?
Solução
Você não seria capaz de fazer isso com o TreeMap implementada na biblioteca de coleções. Aqui está uma implementação de um Red-Black Tree em Java que você pode olhar embora. Confira os métodos printTree()
para ver como eles percorrer a árvore na ordem de classificação.
/**
* Print all items.
*/
public void printTree( ) {
printTree( header.right );
}
/**
* Internal method to print a subtree in sorted order.
* @param t the node that roots the tree.
*/
private void printTree( RedBlackNode t ) {
if( t != nullNode ) {
printTree( t.left );
System.out.println( t.element );
printTree( t.right );
}
}
De que talvez você pode escrever seus próprios métodos para percorrer a árvore em todas as três ordens.
Outras dicas
AFAIK as classes TreeSet / treemap realmente não expor qualquer de suas partes internas e apenas em conformidade com a interface Set / Mapa. O iterador é garantido apenas para ir em uma ordem crescente.
Estou um pouco perplexo por que motivo você gostaria de digitalizar esses nós em um inorder desde que o objetivo dessas árvores não é representar as relações entre objetos (por exemplo, fórmulas matemáticas), mas sim apenas para armazenar todos eles e recuperar -los de forma eficiente.
Você pode, pelo menos, fazer a caminhada inorder usando o iterador e um para cada loop:
void inOrderWalk(TreeMap<K,V> treeMap) {
//this will loop through the values in the map in sorted order (inorder traversal)
for (Map.Entry<K,V> entry : treeMap.entrySet() {
V value = entry.getValue();
K key = entry.getKey()
}
}
No entanto, os outros cartazes têm razão:. Java não expõe qualquer um dos mecânicos da árvore, portanto, um pré-venda ou pós-ordem não é possível neste vista ??p>