Java TreeMap Sortieroptionen?

Question

Mir wurde gesagt, dass die Java-Klasse TreeMap eine Implementierung eines RB-Baumes verwendet. Wenn dies der Fall ist, wie macht man einen Tree-Walk auf einer TreeMap in order, preorder und postorder?

Oder ist das nicht möglich?

Answer 1

Sie können dies nicht mit der TreeMap, die in der Bibliothek Sammlungen implementiert ist. Hier ist eine Implementierung eines Red-Black Tree in Java, die Sie jedoch betrachten können. Sehen Sie sich die Methoden printTree() an, um zu sehen, wie sie den Baum in sortierter Reihenfolge durchlaufen.

/** 
* 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äge zu durchqueren.

Answer 2

AFAIK die TreeSet/TreeMap-Klassen stellen tatsächlich keine ihrer Interna bloß und entsprechen lediglich der Set/Map-Schnittstelle. Der Iterator wird nur in aufsteigender Reihenfolge garantiert.

Ich bin ein wenig perplex darüber, warum Sie diese Knoten in einem Inorder scannen sollten, da das Ziel dieser Bäume nicht darin besteht, Beziehungen zwischen Objekten darzustellen (zB mathematische Formeln), sondern einfach alle zu speichern und sie effizient abrufen.

Answer 3

Sie können die Inorder Fuß zumindest tun den Iterator und eine Verwendung für jede Schleife:

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 eine der Baummechanik aussetzen nicht, so ein Preorder oder Nachorder ist in dieser Ansicht nicht möglich.