1

我试图找到一种方法来找到不在二叉搜索树中的最小正 ([0, INT_MAX)) (最大整数) 值。树具有所有正整数。我正在考虑沿着树的左侧向下移动。然后创建一个 struct value ，如果它是最小值struct { int data; bool found; };，我会返回。t/f

我通过遍历左侧来做到这一点，如果 root->data + 1 > left->data，则返回

左->数据+ 1

, 否则向右。那么如果

根-> 数据 + 1 < 右-> 数据

, 那么return root->data + 1. 否则root->data or right->data，如果 right 不为 null，则返回，找到的值为 false。我还必须考虑树中的最小值是否不为 0，然后返回 0。我不确定这是否是最好的方法。

谢谢你的帮助。

编辑：对不起，我昨晚写的，当时我真的很累。我在循环中使用它，因此每次将其放入数组中会占用太多时间。我正在使用二叉搜索树，因此每次通过循环我只需插入和删除 1 次即可完成，用最少的时间来查找不在树中的最小值。

4

2 回答 2

4

以下是您可以遵循的步骤：

  • max_int声明一个大小为 type的数组bool并用 初始化所有元素false。

    bool found[max_int] = {}; //it initializes the array with false!
//assumming `max_int` is a constant expression.
//else you can use `std::vector<bool>` or `std::vector<char>`.

  • 使用BFS或DFS或任何适合您的方式遍历树。对于树中的每个值v，将索引处的数组更新v为：

    found[v] = true; //it means value `v` is found in the tree!

一旦你完成了。最低索引i是您found[i]正在false寻找的值。也就是说，i是不在树中的最小值。

请注意，二叉树和二叉搜索树之间是有区别的。我的解决方案适用于二叉树，尽管它也适用于二叉搜索树。只是在二叉搜索树的情况下，您可以找到更优的解决方案，例如在遍历时您可以忽略具有更大值的分支。我希望你自己能做到。

于 2013-01-28T07:07:54.153 回答
3

假设您的树不包含重复值，您可以按顺序遍历您的树。第一个访问节点的期望值为0。每个后续访问节点的期望值都比最后一个访问节点大1。如果您遇到与预期值不同的节点，那么预期值就是您查询的答案。

我假设由于您描述遍历的方式，您的树是有序的。如果您的树没有排序，您将需要访问每个节点以确定答案，但您可以忽略任何高于树中节点数的值。

虽然以上为 BST 提供了线性解决方案，但您可以更多地利用该结构来获得平均对数解决方案。假设左右节点是真正的子树，那么算法将是：

MinMissingValue(BST t, integer b = 0):
    if (t is empty) return b;
    if (t.root.value - b) > t.root.left.count
        return MinMissingValue(t.root.left, b)
    else
        return MinMissingValue(t.root.right, t.root.value + 1)

该算法依赖于每个子树都知道它包含多少个节点的概念。

于 2013-01-28T07:10:50.983 回答