1

有没有办法检索 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));
  }
});

如何获取这棵树的所有叶子节点？

4

1 回答 1

2

这对我来说没有多大意义。存储在叶子上的元素取决于 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（ whereleft == 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));
    }

}
于 2013-03-22T05:35:24.780 回答