从另一个 bst 的元素构造二叉搜索树的算法

Question

我正在尝试提出一种算法，使用来自另一棵二叉搜索树的元素来构造一棵二叉搜索树，但由于这些元素必须大于或等于某个给定整数的限制，我们称它为 x。

我想到了递归的方法(使用顺序遍历):

binary_tree (bst tree, int x) {
  if (tree is empty)
    return empty;
  if (tree->element>=x)
    insert tree->element in a new BST;
  else ????
}

我不知道最后一个递归调用是什么，我显然不能像这样写两个返回:

else
  return (tree->left, x)
  return (tree->right, x)

我想不出别的，抱歉，如果这是一个愚蠢的问题!我刚开始接触递归，它真的很令人困惑。

Answer 1

让我们想想我们在这里做什么。我们想从现有的二叉搜索树构建一棵树。因为现有的树是 BST，所以我们得到了一些有用的信息。

对于任何节点 V , 如果 V <= x然后是V -> left指向的子树将有所有小于 x 的节点.所以我们不再需要查看左子树了。但是，如果我们命中一个大于或等于 x 的节点我们需要继续递归。让我们用伪代码把这一切结合起来

newBST(root):
    if root is null 
        return 
    if root.val >= x
        addNewNode(root.val)
        newBST(root.right)
        newBST(root.left)
    else:
        newBST(root.right)