从另一个 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)

Answer 2

递归执行此操作有点棘手，因为您拥有的树中的子树和您想要的树中的子树之间没有 1-1 的对应关系。

最简单的方法是按顺序将值>= x 复制到列表中，然后从列表中递归构建树。