Java二叉搜索樹 - 計算到節點的路徑長度

Question

使用Java的TreeMap實現，如何計算樹中指定節點的路徑長度？通過這個我的意思是計算在搜索二叉搜索樹中的節點時進行的比較次數。

Answer 1

TreeMap has a constructor以Comparator作爲參數。比較器用於對存儲在地圖中的鍵進行排序。如果你真的想「計算進行比較的次數」，你可以編寫一個儀表比較器來計算它被調用的次數。

public class StringComparator implements Comparator<String> { 
    private int count = 0; 

    @Override 
    public int compare(String o1, String o2) { 
     ++count; 
     return o1.compareTo(o2); 
    } 

    public int getCount() { return count; } 
    public void reset() { count = 0; } 

    public static void main(String[] args) { 
     StringComparator sc = new StringComparator(); 
     TreeMap<String, String> map = new TreeMap<>(sc); 
     map.put("foo", "one"); 
     System.out.println("foo took " + sc.getCount() + " comparisons"); 
     sc.reset(); 
     map.put("bar", "two"); 
     System.out.println("bar took " + sc.getCount() + " comparisons"); 
    } 
}