java - Java TreeMap 排序选项？

Question

有人告诉我，Java 类 TreeMap 使用了 RB 树的实现。如果是这种情况，如何在 TreeMap 上进行中序、前序和后序树遍历？

或者这是不可能的？

Answer 1

使用 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 );
    }
}

从那里也许您可以编写自己的方法以所有三个顺序遍历树。

Answer 2

AFAIK 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 没有公开任何树机制，因此在此视图中不可能进行预排序或后排序。