Параметры сортировки Java TreeMap?
-
22-07-2019 - |
Вопрос
Мне сказали, что java-класс TreeMap использует реализацию дерева RB. Если это так, как можно выполнить обход дерева по порядку, порядку и порядку в TreeMap?
Или это невозможно?
Решение
Вы не сможете сделать это с 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 );
}
}
Из этого, возможно, вы можете написать свои собственные методы для обхода дерева во всех трех порядках.
Другие советы
AFAIK классы TreeSet / TreeMap на самом деле не раскрывают ни одного из своих внутренних элементов и просто соответствуют интерфейсу Set / Map. Итератор гарантированно работает только в порядке возрастания.
Я немного озадачен тем, почему вы захотите сканировать эти узлы в порядке, поскольку цель этих деревьев не в том, чтобы представлять отношения между объектами (например, математические формулы), а просто в том, чтобы сохранить их все и получить их эффективно. Р>
Вы можете по крайней мере выполнить обход, используя итератор и 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 не раскрывает никакой древовидной механики, поэтому предзаказ или поступорядочение в этом представлении невозможны.