检索java TreeMap的所有叶节点 [英] Retrieve all the leaf nodes of java TreeMap

问题描述

有没有办法检索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 Entryies, 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 Entryies. 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的所有叶节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！