Java BST遞歸變量設置

Question

我有一個正常的二叉搜索樹，用數據的字符串值和左右節點實現。樹工作正常，但我有我的rankOf函數的麻煩。我使用遞歸來查找節點，並且當元素存在時方法成功，但是當不存在的值不起作用時，我無法弄清楚如何設置布爾值來幫助解決這個問題。下面是代碼：

private int rankOf(String s, Node n){ 
    if (n != null){ 

     //check root 
     if (s.compareTo(n.value) == 0){ 
      if (n.left != null){ 
       return size(n.left); 
      } 
      return 0; 
     } 
     // only worry about left tree, easy 
     if (s.compareTo(n.value) < 0){ 
      return rankOf(s, n.left); 
     } else { 
      // must count entire left tree plus root node 
      return rankOf(s, n.right) + size(n.left) + 1; 
     } 

    } 
    //null or not found 
    return 0; 
} 

當根等於我所知道的元素在樹這樣的東西應該在那裏，但不知道該如何處理這個值。

Answer 1

這種檢查是無用的：

if (n.left != null){ 
    return size(n.left); 
} 

無論如何，你可以做這樣的事情：

static int rankOf(String s, Node root) { 
    if(root == null) { 
     return -1; 
    } 

    if(root.value.equals(s)) { 
     return size(root); 
    } 

    int result; 
    if(s.compareTo(root.value) > 0) { 
     result = rankOf(s, root.right); 
    } else { 
     result = rankOf(s, root.left); 
    } 
    return result; 
} 

而且你size()方法：

static int size(Node root) { 
    if(root == null) return 0; 
    return size(root.left) + size(root.right) + 1; 
} 

萬一String不發現，-1將被退回。