Ti serve una struttura di tipo map? Cioe' devi anche accedere ai valori per chiave oltre che averli ordinati? Se la risposta e' no usa TreeSet e non TreeMap.
Se ti serve una mappa, ma non ti serve di ordinarla per chiave, puoi anche non usare una TreeMap e optare per un HashMap che generalmente e' piu' veloce.
Per l'ordinamento: il metodo values() su qualunque map restituisce una Collection contenente tutti i valori, una volta ottenuta la Collection. la puoi ordinare attraverso il metodo Collections.sort. Qui puoi seguire due strade, ordine naturale (cioe' quello di default oppure quello che decidi tu facendo estendere alla classe Comparable e sovrascrivendo opportunamente il metodo CompareTo) oppure attraverso una tua classe che implementa l'interfaccia Comparator.
codice:
Map mappa = new HashMap() //O TreeMap se preferisci
//ALTRO CODICE
Collection collezione = mappa.values();
Collections.sort(collezione); 
//Secondo ordine naturale;
codice:
Map mappa = new HashMap() //O TreeMap se preferisci
//ALTRO CODICE
Collection collezione = mappa.values();
Comparator c = new tuoComparator();
Collections.sort(collezione, c); 
//Secondo Comparator;
P.s. Non so se esistono metodi piu' furbi, questo comunque dovrebbe andare.