有没有办法检索 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));
}
});
如何获取这棵树的所有叶节点?
最佳答案
这对我来说没有多大意义。存储在叶子中的元素取决于 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
包中执行此操作,以便能够调查这些 Entry
ies。但这里是代码,仅供娱乐。 (如果不覆盖 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));
}
}
关于java - 检索java TreeMap的所有叶子节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15563133/