Options de tri Java TreeMap?

Question

On m'a dit que la classe java TreeMap utilise une implémentation d'un arbre RB. Si tel est le cas, comment fait-on une marche en ordre, en pré-commande et en post-commande sur une TreeMap?

Ou n'est-ce pas possible?

Answer 1

Vous ne pourriez pas faire cela avec le TreeMap implémenté dans la bibliothèque de collections. Voici une implémentation d'un Arbre Rouge-Noir en Java que vous pouvez consulter. Découvrez les méthodes printTree () pour voir comment elles marchent dans l’arbre dans l’ordre trié.

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

À partir de là, vous pourrez peut-être écrire vos propres méthodes pour parcourir l'arbre dans les trois ordres.

Answer 2

D’après les notes, les classes TreeSet / TreeMap n’exposent en réalité aucun de leurs éléments internes et sont simplement conformes à l’interface Set / Map. L’itérateur n’est garanti que dans un ordre croissant.

Je suis un peu perplexe quant à la raison pour laquelle vous souhaitez analyser ces nœuds dans l’ordre car le but de ces arbres n’est pas de représenter les relations entre les objets (par exemple, des formules mathématiques), mais plutôt de les stocker tous simplement et de les récupérer. les efficacement.

Answer 3

Vous pouvez au moins faire la marche dans l'ordre en utilisant l'itérateur et une boucle pour chaque boucle:

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

Cependant, les autres affiches sont correctes: Java n'expose aucune des mécaniques des arbres, il est donc impossible d'effectuer une pré-commande ou un post-commande dans cette vue.