java - 检索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 的包私有(private)方法。

经过进一步挖掘，我发现 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 中的一个，则可以将父级一直遍历到根，然后执行 traversal of the tree您想要获取叶子的任何方式(Entry，其中left == null 和right == null)。中序遍历将保留排序顺序。

但是，重申一下，我没有看到您想要这样做的任何充分理由。您还需要在 java.util 包中执行此操作，以便能够调查这些 Entryies。但这里是代码，仅供娱乐。 (如果不覆盖 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));
    }

}