检索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，其中left == null和right == null）做一个traversal of the tree。顺序遍历将保留排序顺序。

但是，重申一下，我没有看到有什么好的理由说明你想这样做。您还需要在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)); 
    } 

}