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"); 
    } 
}