问题描述
有没有办法检索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
。
在做了一些挖掘之后,我发现JDK中的默认树实现是一个红黑树,它的条目
实现如下所示:
static final class Entry< K ,V>实现Map.Entry< K,V> {
K key;
V值;
条目< K,V> left = null;
条目< K,V> right = null;
条目< K,V>父母;
boolean color = BLACK;
....
似乎没有任何直接获得根的方式但是,如果您可以抓住其中一个条目
,那么您可以将父代一直遍历根,然后执行任何你想要获取树叶的方式( Entry
where left == null
和 right == null
)。不顺序遍历将保留排序顺序。
但是,要重申,我没有看到任何好的理由,为什么要这样做。您还需要在 java.util
软件包中执行此操作,才能调查那些 Entry
。但这里的代码,为了好玩。 (您将无法执行此操作,而不会覆盖JVM上的安全限制。)
package java.util;
import java.util.TreeMap.Entry;
public class TreeMapHax {
static< K,V>列表<条目< K,V>> getLeafEntries(TreeMap< K,V> map){
条目< K,V> root = map.getFirstEntry();
while(root.parent!= null)root = root.parent;
列表<条目< K,V>> l = new LinkedList< Entry< K,V>();
visitInOrderLeaves(root,l);
return l;
}
static< K,V> void visitInOrderLeaves(Entry< K,V> node,List< K>>> 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>(); (int i = 0; i< 10; i ++)
map.put(Integer.toString(i),i);
System.out.println(getLeafEntries(map));
}
}
Is there a way to retrieve all the leaf nodes of a Java TreeMap
?
I have a TreeMap
like this
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));
}
});
How do I get all the leaf nodes of this tree?
This doesn't make much sense to me. The elements stored at the leaves are dependent on how the implementation of TreeMap balances the tree.
But, let's say you needed to do this for some reason. To actually do this, you would need to do a bit of a hack: write a class packaged in java.util
that can access the package private methods of TreeMap
.
After doing some more digging, I found that the default tree implementation in the JDK is a red-black tree, and its Entry
implementation look like the following:
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;
....
There doesn't seem to be any direct way to get at the root. But, if you can grab one of these Entry
ies, though, you can traverse the parent all the way up to the root, then do a traversal of the tree any way you want to get the leaves (Entry
where left == null
and right == null
). An inorder traversal would preserve the sorted ordering.
But, to reiterate, I don't see any good reason why you'd want to do this. You'd also need to do it in the java.util
package to be able to investigate those Entry
ies. But here's code, for fun. (You won't be able to execute this without overriding the security restrictions on the 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 TreeMap的所有叶节点的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!