Java TreeMapの並べ替えオプション?
-
22-07-2019 - |
質問
JavaクラスTreeMapはRBツリーの実装を使用すると言われました。この場合、TreeMapでどのようにインオーダー、プレオーダー、ポストオーダーツリーウォークを行うのですか?
またはこれは不可能ですか?
解決
Collectionsライブラリに実装されたTreeMapでこれを行うことはできません。以下に、 Javaの赤黒ツリーをご覧ください。 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つの順序すべてでツリーを走査する独自のメソッドを作成できます。
他のヒント
TreeSet / TreeMapクラスは内部を実際に公開せず、Set / Mapインターフェースに準拠しているだけです。反復子は昇順でのみ保証されます。
これらのツリーの目的はオブジェクト間の関係(数式など)を表すことではなく、単にすべてを保存して取得することであるため、これらのノードを順番にスキャンする理由について少し困惑していますそれらを効率的に。
少なくとも、イテレータと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はツリーメカニズムを公開しないため、このビューでは予約注文または予約注文を行うことはできません。
所属していません StackOverflow