java中的二叉查找樹遞歸子樹

Question

任何人都可以指向一個代碼示例（java優先）或psuedocode，它使用遞歸來返回一個包含fromKey和toKey之間的鍵的所有節點的子樹。因此，如果我要調用Tree.subtree（5,10），它應該返回BST中所有包含5和10之間的鍵的節點 - 但我不能使用循環或輔助方法...只能遞歸調用以fromKey和toKey作爲參數的子樹方法。

謝謝！

更新：

我已經儘量不工作的情況如下：

public Tree subtree(int from, int to) { 
    left.subtree(from, to); 
    right.subtree(from, to); 
    if (this.key < from || this.key > to) { 
     this.delete(this.key); 
    } 
    return this; 
} 

我覺得這個問題是，它返回爲時尚早。我想要做的是遍歷樹上的每個節點，並刪除任何不在範圍內的節點。我在正確的軌道上嗎？

Answer 1

不應該subtree返回原始樹的副本，而不是從中刪除密鑰？你的原始遞歸如何終止？

我建議是這樣的：

public static Tree subtreeNullSafe(Tree t, int from, int to) { 
    return t == null ? null : t.subtree(from, to); 
} 

public Tree subtree(int from, int to) { 
    if (this.key > to) { 
    return subtreeNullSafe(this.left, from, to); 
    } else if (this.key < from) { 
    return subtreeNullSafe(this.right, from, to); 
    } else { 
    // we know that this.key <= to and this.key >= from 
    return new Tree(
     this.key, 
     subtreeNullSafe(this.left, from, to), 
     subtreeNullSafe(this.right, from, to) 
    ); 
    } 
} 

這確實使用一個輔助方法，以減少重複。如果你真的被禁止使用，你可以直接插入null檢查。