Tùy chọn sắp xếp Java TreeMap?

Question

Tôi đã được thông báo rằng lớp Java TreeMap sử dụng thực thi cây RB. Nếu đây là trường hợp, làm thế nào để làm một inorder, preorder và postorder tree-walk trên TreeMap?

Hoặc điều này là không thể?

Answer 1

Bạn sẽ không thể thực hiện việc này bằng TreeMap được triển khai trong thư viện Bộ sưu tập. Đây là một thực hiện của một Red-Black Tree trong Java mà bạn có thể xem xét mặc dù. Kiểm tra các phương pháp printTree() để xem cách chúng đi bộ theo thứ tự sắp xếp.

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

Từ đó bạn có thể viết phương pháp của riêng bạn để duyệt cây trong cả ba đơn đặt hàng.

Answer 2

AFAIK lớp TreeSet/TreeMap không thực sự phơi bày bất kỳ nội bộ nào của chúng và chỉ phù hợp với giao diện Set/Map. Trình vòng lặp chỉ được đảm bảo để đi theo thứ tự tăng dần.

Tôi hơi lúng túng là lý do tại sao bạn muốn quét các nút này theo thứ tự vì mục tiêu của những cây này không đại diện cho mối quan hệ giữa các đối tượng (ví dụ: công thức toán học) mà là để lưu trữ tất cả chúng lấy chúng hiệu quả.

Answer 3

Bạn ít nhất có thể làm như đi bộ inorder sử dụng iterator và một cho mỗi vòng lặp:

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() 
    } 
} 

Tuy nhiên, các áp phích khác là đúng: Java không tiếp xúc với bất kỳ của các cơ chế cây, do đó, một preorder hoặc postorder là không thể ở chế độ xem này.