Получить все листовые узлы Java TreeMap

Question

Есть ли способ получить все конечные узлы Java TreeMap?

у меня есть TreeMap как это

TreeMap<String, FooBar> myTree = new TreeMap<String, FooBar>(new Comparator<String>() {
  public int compare(String o1, String o2)
  {
    int b1 = Integer.parseInt(o1, 2);
    int b2 = Integer.parseInt(o2, 2);
    return (b1 > b2 ? 1 : (b1 == b2 ? 0 : -2));
  }
});

Как мне получить все листовые узлы этого дерева?

Answer 1

Это не имеет большого смысла для меня. Элементы, хранящиеся на листьях, зависят от того, как реализация TreeMap уравновешивает дерево.

Но, скажем, вам нужно было сделать это по какой-то причине. Чтобы на самом деле сделать это, вам нужно будет немного взломать: написать класс, упакованный в java.util которые могут получить доступ к частным методам пакета TreeMap,

После еще нескольких копаний я обнаружил, что реализация дерева по умолчанию в JDK - это красно-черное дерево, и его Entry реализация выглядит следующим образом:

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;
    V value;
    Entry<K,V> left = null;
    Entry<K,V> right = null;
    Entry<K,V> parent;
    boolean color = BLACK;

    ....

Кажется, что нет прямого способа получить корень. Но если вы можете взять один из них EntryТем не менее, вы можете пройти родительский путь до корня, а затем выполнить обход дерева любым способом, каким хотите получить листья (Entry где left == null а также right == null). Обход по порядку следования сохранит отсортированный порядок.

Но, повторюсь, я не вижу веских причин, почему вы хотели бы сделать это. Вам также нужно сделать это в java.util пакет, чтобы иметь возможность исследовать эти Entryх годов. Но вот код, для развлечения. (Вы не сможете выполнить это без переопределения ограничений безопасности на JVM.)

package java.util;

import java.util.TreeMap.Entry;

public class TreeMapHax {

    static <K,V> List<Entry<K, V>> getLeafEntries(TreeMap<K, V> map) {      
        Entry<K, V> root = map.getFirstEntry();
        while( root.parent != null ) root = root.parent;

        List<Entry<K,V>> l = new LinkedList<Entry<K,V>>();
        visitInOrderLeaves(root, l);
        return l;
    }

    static <K,V> void visitInOrderLeaves(Entry<K, V> node, List<Entry<K, V>> accum) {       
        if( node.left != null ) visitInOrderLeaves(node.left, accum);       
        if( node.left == null && node.right == null ) accum.add(node);      
        if( node.right != null ) visitInOrderLeaves(node.right, accum);
    }

    public static void main(String[] args) {
        TreeMap<String, Integer> map = new TreeMap<String, Integer>();

        for( int i = 0; i < 10; i++ )
            map.put(Integer.toString(i), i);

        System.out.println(getLeafEntries(map));
    }

}