Java TreeMap opções de classificação?

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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