java - Java TreeMap の並べ替えオプション?

Question

Java クラス TreeMap は RB ツリーの実装を使用していると聞いています。この場合、TreeMap で順序、事前順序、および事後順序のツリー ウォークを行うにはどうすればよいでしょうか。

それとも、これは不可能ですか？

Answer 1

Collections ライブラリに実装されている TreeMap では、これを行うことはできません。Java でのRed-Black Treeの実装を次に示します。メソッドをチェックしてprintTree()、ソートされた順序でツリーをたどる方法を確認してください。

/**
 * Print all items.
 */
public void printTree( ) {
    printTree( header.right );
}

/**
 * Internal method to print a subtree in sorted order.
 * @param t the node that roots the tree.
 */
private void printTree( RedBlackNode t ) {
    if( t != nullNode ) {
        printTree( t.left );
        System.out.println( t.element );
        printTree( t.right );
    }
}

そこから、3 つの順序すべてでツリーをたどる独自のメソッドを作成できるかもしれません。

Answer 2

私の知る限り、TreeSet/TreeMap クラスは実際には内部を公開しておらず、単に Set/Map インターフェースに準拠しています。イテレータは昇順であることが保証されています。

これらのツリーの目的は、オブジェクト間の関係 (数式など) を表すことではなく、単にそれらすべてを格納して効率的に取得することであるため、これらのノードを順番にスキャンする理由について少し困惑しています。

Answer 3

少なくとも、反復子と for each ループを使用してインオーダー ウォークを実行できます。

void inOrderWalk(TreeMap<K,V> treeMap) {
   //this will loop through the values in the map in sorted order (inorder traversal)
   for (Map.Entry<K,V> entry : treeMap.entrySet() {
        V value = entry.getValue();
        K key = entry.getKey()
   }
}

ただし、他のポスターは正しいです。Java はツリーの仕組みをまったく公開していないため、このビューでは事前注文または事後注文はできません。