c++ - 最小值不在二叉树中？

Question

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

我是通过遍历左侧来完成的，如果root->data + 1 > left->data，则返回

left->data + 1

，否则向右走。那么如果

root->data + 1 < right->data

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

感谢您的帮助。

编辑:抱歉，这是我昨晚写的，当时我真的很累。我在一个循环中使用它，所以每次都将它放入一个数组中会占用太多时间。我使用的是二叉搜索树，因此每次循环只需进行 1 次插入和删除即可完成此操作，并且花费最少的时间查找不在树中的最小值。

Answer 1

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

• 声明一个大小为 max_int 且类型为 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!
  

完成后。 found[i​​] 为 false 的最低索引 i 就是您要查找的值。也就是说，i 是不在树中的最小值。

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