Java TreeMap opzioni di ordinamento?

Question

Mi è stato detto che la classe java TreeMap utilizza un'implementazione di un albero RB. In questo caso, come si fa un albero in ordine, preordine e postordine a camminare su una TreeMap?

O questo non è possibile?

Answer 1

Non saresti in grado di farlo con la TreeMap implementata nella libreria Collezioni. Ecco un'implementazione di un Albero rosso-nero in Java che puoi comunque vedere. Dai un'occhiata ai metodi printTree () per vedere come camminano sull'albero in ordine.

/**
 * 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 );
    }
}

Da questo forse puoi scrivere i tuoi metodi per attraversare l'albero in tutti e tre gli ordini.

Answer 2

AFAIK le classi TreeSet / TreeMap in realtà non espongono nessuno dei loro interni e si limitano a conformarsi all'interfaccia Set / Map. L'iteratore è garantito solo per un ordine crescente.

Sono un po 'perplesso sul motivo per cui vorresti scansionare questi nodi in un ordine poiché l'obiettivo di questi alberi non è quello di rappresentare le relazioni tra gli oggetti (ad esempio, le formule matematiche) ma piuttosto solo di memorizzarli tutti e recuperarli loro in modo efficiente.

Answer 3

Puoi almeno fare la camminata inorder usando l'iteratore e un per ogni 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()
   }
}

Tuttavia, gli altri poster hanno ragione: Java non espone nessuna delle meccaniche dell'albero, quindi un preordine o postorder non è possibile in questa vista.