java - java中的二叉搜索树递归子树

Question

任何人都可以指出一个代码示例(最好是 java)或使用递归返回一个子树的伪代码，该子树包含键在 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

子树 不应该返回原始树的副本，而不是从中删除键吗？您的原始递归如何终止？

我会推荐这样的东西:

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 检查您是否真的被禁止使用它。