Opciones de ordenación Java TreeMap?

Question

Me han dicho que la clase Java TreeMap usa una implementación de un árbol RB. Si este es el caso, ¿cómo hace uno inorder, preorder y postorder tree-walk en un TreeMap?

¿O no es esto posible?

Answer 1

No podría hacer esto con el TreeMap implementado en la biblioteca de colecciones. Aquí hay una implementación de Red-Black Tree en Java que puedes ver sin embargo. Consulte los métodos printTree() para ver cómo recorren el árbol en orden ordenado.

/** 
* 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 eso, tal vez pueda escribir sus propios métodos para recorrer el árbol en los tres órdenes.

Answer 2

AFAIK las clases TreeSet/TreeMap realmente no exponen ninguna de sus partes internas y simplemente se ajustan a la interfaz Set/Map. El iterador solo está garantizado para ir en orden ascendente.

Estoy un poco perplejo sobre por qué querría escanear estos nodos en orden porque el objetivo de estos árboles no es representar las relaciones entre objetos (por ejemplo, fórmulas matemáticas), sino simplemente almacenarlos todos y recuperarlos de manera eficiente.

Answer 3

al menos se puede hacer el paseo a finde utilizando el iterador y una para cada bucle:

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() 
    } 
} 

Sin embargo, los otros críticos tienen razón: Java no expone cualquiera de los mecanismos de árboles, por lo que un orden previo o postorder no es posible en esta vista.