Search code examples
javabinary-treered-black-tree

Java TreeMap sorting options?

I've been told that the java class TreeMap uses an implementation of a RB tree. If this is the case, how does one do an inorder, preorder and postorder tree-walk on a TreeMap?

Or is this not possible?

Solution

  • You wouldn't be able to do this with the TreeMap implemented in the Collections library. Here's an implementation of a Red-Black Tree in Java that you can look at though. Check out the printTree() methods to see how they walk the tree in sorted order. 

    /**
 * 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 );
    }
}

    From that maybe you can write your own methods to traverse the tree in all three orders.