Java TreeMap Sortieroptionen?

Question

Ich habe gesagt, dass die Java-Klasse TreeMap eine Implementierung eines RB Baum verwendet. Wenn dies der Fall ist, wie macht man eine inorder, vorbestellbar und Postorder-Baum-Spaziergang auf einem TreeMap?

Oder ist dies nicht möglich?

Answer 1

Sie würden nicht in der Lage sein, dies in der Sammlungen-Bibliothek implementiert mit dem TreeMap zu tun. Hier ist eine Implementierung eines Red-Black Tree in Java, die Sie können allerdings aussehen. Überprüfen Sie die printTree() Methoden zu sehen, wie sie den Baum in sortierter Reihenfolge zu Fuß.

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

Von dass vielleicht können Sie Ihre eigenen Methoden schreiben, den Baum in allen drei Aufträgen zu durchqueren.

Answer 2

AFAIK der TreeSet / TreeMap Klassen aussetzen nicht wirklich alle ihre Interna und lediglich auf die Set / Map-Schnittstelle entsprechen. Der Iterator ist nur in aufsteigender Reihenfolge gehen garantiert.

Ich bin ein wenig verwirrt, warum Sie wollen würde diese Knoten in einem inorder scannen, da das Ziel dieser Bäume ist nicht die Beziehungen zwischen Objekten darzustellen (zB mathematische Formeln), sondern nur um sie alle zu speichern und abzurufen sie effizient.

Answer 3

Sie können zumindest tun das inorder zu Fuß den Iterator und einen für jede Schleife mit:

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

Allerdings sind die anderen Plakate rechts: Java belichten nicht jede der Baummechanik, so ein Preorder oder Postorder ist in dieser Ansicht nicht möglich

.