сортировка дерева по ключу, где ключ является переменной - PullRequest
Новая
       23

сортировка дерева по ключу, где ключ является переменной

8 голосов
/ 03 августа 2011

Я хочу отсортировать древовидную карту по ключу, где ключ является переменной, поэтому сортировка должна основываться на значении переменной. Как мы можем этого добиться? Я хочу использовать встроенный метод сортировки rathar, реализуя его через код, любой ответ с примером очень помогает.

Ответы [ 3 ]

20 голосов
/ 03 августа 2011

TreeMap (который реализует SortedMap) автоматически сохраняет ключи в правильном порядке: 

Map<Integer, String> map = new TreeMap<Integer, String>();
map.put(1, "one");
map.put(3, "three");
map.put(2, "two"); 
// prints one two three   
for(Integer key : map.keySet()) {
    System.out.println(map.get(key));
}

как тип ключа (в этомcase Integer) вы можете использовать любой класс, который реализует Comparable (или вы можете указать Comparator при создании TreeMap)

Edit: Хорошо, вот предложение, как изменить карту вашей карты. 

Map<Integer, String> oldMap; // get oldMap from somewhere
// Prepare remapping
Map<Integer, String> newMap = new TreeMap<Integer, String>();
Map<Integer, Integer> keyMap = new HashMap<Integer, Integer>();
// Store a new key for each old key
keyMap.put(oldKey, newKey);
// fill the newMap
for(Integer oldKey : keyMap.keySet()) {
    newMap.put(keyMap.get(oldKey), oldMap.get(oldKey));
}
oldMap = newMap; // if needed
0 голосов
/ 03 августа 2011

A treemap - красно-черное дерево, представляющее собой сбалансированное дерево двоичного поиска . Другими словами, дерево уже отсортировано (или, скорее, упорядочено согласно правилам бинарного дерева поиска) с его сбалансированной высотой, так что операции дерева имеют сложность O (lg n). Тем не менее, я думаю, что вы хотите, чтобы напечатать все ключи в отсортированном порядке. Это так же просто, как реализация обхода inorder на древовидной карте, или вы можете использовать метод keySet () для получения Set и перебора значений.

например. прохождения порядка 

void inorderTraversal( Node root ){
    if( root == null ) return;
    inorderTraversal( root.getLeft() );
    root.printValue();
    inorderTraversal( root.getRight() );
}

EDIT :

Хорошо, я почти уверен, что это то, что вы хотите. Вы хотите отсортировать по значениям: 

        Map<String, Integer> map = new TreeMap<String, Integer>();
        map.put("one", 8);
        map.put("two", 10);
        map.put("three", 9);
        map.put("hundred", 1);
        System.out.println(map.values());

Выход: 

[1, 8, 9, 10]

Так что это работает даже для сортировки строковых значений: 

    Map<Integer, String> map = new TreeMap<Integer, String>();
        map.put(8, "one");
        map.put(10, "two");
        map.put(9, "three");
        map.put(1, "hundred");
        System.out.println(map.values());

Выход: 

[hundred, one, three, two]

Кроме того, sachin учтите, что наличие «ключей переменных» и значений переменных - это совершенно разные вещи.

0 голосов
/ 03 августа 2011

TreeMap реализует интерфейс SortedMap и сортируется по его ключу без необходимости что-либо делать:

Карта сортируется в соответствии с естественным порядком ее ключей или Comparator предоставляется во время создания карты, в зависимости от того, какой используется конструктор.

...