Параметры сортировки Java TreeMap?

Question

Мне сказали, что java-класс TreeMap использует реализацию дерева RB. Если это так, то как можно выполнить обход дерева по порядку, порядку и порядку в TreeMap?

Или это невозможно?

Answer 1

Вы не сможете сделать это с TreeMap, реализованным в библиотеке коллекций. Вот реализация Красно-черного дерева в Java, на которую вы можете посмотреть. Проверьте методы printTree(), чтобы увидеть, как они обходят дерево в отсортированном порядке.

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

Исходя из этого, вы можете написать свои собственные методы для обхода дерева во всех трех порядках.

Answer 2

Вы можете по крайней мере выполнить обход, используя итератор и a для каждого цикла:

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

Тем не менее, другие постеры правы: Java не раскрывает никакой древовидной механики, поэтому предзаказ или поступорядочение в этом представлении невозможны.

Answer 3

AFAIK классы TreeSet / TreeMap на самом деле не предоставляют каких-либо своих внутренних функций и просто соответствуют интерфейсу Set / Map. Итератор гарантированно работает только в порядке возрастания.

Я немного озадачен тем, почему вы захотите сканировать эти узлы в порядке, поскольку цель этих деревьев не в том, чтобы представлять отношения между объектами (например, математические формулы), а просто в том, чтобы сохранить все их и извлечь их эффективно.