是否在二进制搜索树中查找最接近的值？
我有这个算法结构问题；编写一个函数，它接受一个BST和一个目标Interget值，并将最接近的值返回给包含在BST中的目标值。
这个算法站点给了我一个可以使用的东西；
function findClosestValueInBst(tree, target) {
// Write your code here.
}
// This is the class of the input tree. Do not edit.
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}我不是在问答案，但是我如何在我本地的visual studio代码中进行测试呢？我需要在函数的树/目标参数参数中传递什么值才能测试或console.log出东西？
我猜他们是在给我一个示例输入，但是..我怎么才能将它记录到我的函数中来测试它呢？
{
"tree": {
"nodes": [
{"id": "10", "left": "5", "right": "15", "value": 10},
{"id": "15", "left": "13", "right": "22", "value": 15},
{"id": "22", "left": null, "right": null, "value": 22},
{"id": "13", "left": null, "right": "14", "value": 13},
{"id": "14", "left": null, "right": null, "value": 14},
{"id": "5", "left": "2", "right": "5-2", "value": 5},
{"id": "5-2", "left": null, "right": null, "value": 5},
{"id": "2", "left": "1", "right": null, "value": 2},
{"id": "1", "left": null, "right": null, "value": 1}
],
"root": "10"
},
"target": 12
}回答 3
Stack Overflow用户
发布于 2021-11-19 08:16:27
您需要构建有效的搜索树。
首先实现操作Add(root, value)
然后使操作Find以寻找精确重合，并使Successor和Predecessor获得比当前值更大和更小的最接近值。
然后提供值序列来创建树(示例：6,3,9,0,15,5,7,14)并测试上述函数。
要实现findClosestValueInBst，您可以修改Find的代码，但是当您发现元素缺失(站在最后一个树叶)时，调用Successor或Predecessor函数之一来检查邻居，找出哪个值接近目标。
Stack Overflow用户
发布于 2021-11-19 08:19:45
您可能希望构建自己的BST (或几个)来测试您的代码。您可以手动构建它们，只需一个接一个地创建一组节点并将它们链接在一起，或者编写一个插入函数来将值传递给并构建您的树。如果愿意，您可以使用一个值数组并在其上进行映射以构建节点。只需跟踪BST的根节点即可。
然后使用您创建的BST的根和几个不同的目标值调用您的函数。查看您的函数是否返回预期的值。尝试涵盖所有常见和边缘情况：
目标恰好在树中:作为根节点、内部节点或叶节点；
target不在树中，但在两个值之间(请注意返回更接近的值)；
目标不在树中，并且比树中的所有内容都大或小(请参见返回树中实际的最大或最小值)；
处理在空BST、只有一个节点的BST、具有和不具有重复值的BST中的搜索
编辑:添加了一些样板代码，以便从值列表构建BST，然后是如何将树传递给函数并记录输出的示例。还有一个将树打印到控制台的功能。它是独立的，你必须想象它的链接，但它可能是有帮助的。祝好运
// This is the class of the input tree. Do not edit.
class BST {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
function findClosestValueInBst(tree, target) {
// Write your code here.
}
// build a BST from an array of values and return the root
function buildTree(values) {
let root = null
for (let value of values) root = insert(root, value)
return root;
}
// insert a value into a BST
function insert(root, value) {
if (!root) return new BST(value)
if (value < root.value)
root.left = insert(root.left, value)
else
root.right = insert(root.right, value)
return root
}
// display a binary tree
function display(root, depth = 0) {
if (!root) return;
display(root.right, depth+1)
console.log(`${'\t'.repeat(depth)}${root.value}`)
display(root.left, depth+1)
}
const T1 = buildTree([
10, 7, 2, 13, 10, 3,
5, 12, 16, 23, 1, 20
])
display(T1)
// console.log(findClosestValueInBst(T1, 12)) // should return 12, because 12 is in T1
// console.log(findClosestValueInBst(T1, 14)) // should return 13, as it's the closest to 14
Stack Overflow用户
发布于 2021-11-19 08:25:54
提示：
想一想事情怎么会出错。典型的错误是
- 严重编程错误(二进制搜索完全错误，拼写错误)；
- 微妙的限制情况(空树，单个节点的树，两个节点；相等的节点；目标等于一个节点，目标在中间；几个节点上的二进制搜索错误...)。
对于上述每一种情况，如何检查？
与其只尝试几个测试用例，我建议用断言来装备代码，你知道这些断言必须在关键的地方持有。例如，检查是否仍然在您考虑的子树中找到解决方案。
还要确保实现一个在所有情况下都能返回正确答案的防弹函数(效率无关紧要)。
由于练习似乎不是关于如何构建BST，因此可以为该任务的这一部分复制现有代码。确保来源是可靠的。(为了双重安全，您可以验证构建的树。)
https://stackoverflow.com/questions/70031500
复制相似问题
腾讯云开发者
