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检查。