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?
A TreeMap is always sorted based on keys. The sorting order follows the natural ordering of keys. You may also provide a custom Comparator to the TreeMap at the time of creation to let it sort the keys using the supplied Comparator.
TreeMap is a Red-Black tree based NavigableMap implementation.In other words , it sorts the TreeMap object keys using Red-Black tree algorithm. So we learned that TreeMap uses Red Black tree algorithm internally to sort the elements. Red Black algorithm is a complex algorithm .
To sort keys in TreeMap by using a comparator with user-defined objects in Java we have to create a class that implements the Comparator interface to override the compare method. In the below code, we are passing a custom object as a key in TreeMap i.e Student user-defined class.
By default TreeMap elements in Java are sorted in ascending order of keys. However, we can create the TreeMap in reverse order using Collections. reverseOrder() method in Java and display the elements in descending order of keys.
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.
AFAIK the TreeSet/TreeMap classes don't actually expose any of their internals and merely conform to the Set/Map interface. The iterator is only guaranteed to go in an ascending order.
I am a little perplexed as to why you would want to scan these nodes in an inorder since the goal of these trees is not to represent relations between objects (e.g., math formulae) but rather just to store all of them and retrieve them efficiently.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With