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;

    ....

ルートに到達する直接的な方法はないようです。ただし、これらのEntryies の 1 つを取得できる場合は、親をルートまでトラバースし、ツリーを任意の方法でトラバースして葉 ( Entrywhereleft == nullおよびright == null) を取得できます。インオーダートラバーサルは、ソートされた順序を保持します。

しかし、繰り返しますが、これを行う正当な理由は見当たりません。また、それらのiesjava.utilを調査できるようにするには、パッケージでそれを行う必要があります。Entryしかし、ここにコードがあります。(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 に答える