Opciones de ordenación de 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 se hace un recorrido de árbol de orden, preorden y postorder 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 un Árbol Rojo-Negro en Java que puedes ver. 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 );
    }
}

A partir de eso, tal vez pueda escribir sus propios métodos para atravesar el árbol en los tres órdenes.

Answer 2

AFAIK las clases TreeSet / TreeMap en realidad no exponen ninguno de sus componentes internos y simplemente se ajustan a la interfaz Set / Map. El iterador solo se garantiza que vaya en orden ascendente.

Estoy un poco perplejo en cuanto a por qué querrías escanear estos nodos en un orden dado que el objetivo de estos árboles no es representar las relaciones entre los objetos (por ejemplo, fórmulas matemáticas) sino simplemente almacenarlos y recuperarlos ellos eficientemente.

Answer 3

Al menos puede hacer el recorrido en orden usando el iterador y una para cada ciclo:

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 carteles tienen razón: Java no expone ninguna de las mecánicas del árbol, por lo que no es posible realizar un pedido anticipado o un postorder en esta vista.