BinarySearchTree查找特定值之间的最接近值

Question

我有一个Binary Search Tree，我需要得到最接近的较高和最接近的较低，最接近的较低必须介于5和9之间（意味着高于5或低于9）。

假设我有一个ID为125的Node，最接近该节点的数字是127，但它也必须在5到9之间，因此ID为130的“Node”将是我正在寻找的那个。

这是我正在使用的二叉树：

这就是我现在找到最接近的更高的方式：

Node currentNode = null;
int currentNodeID;
double min = Double.MAX_VALUE;    

public Node closestHigherValue(Node root, double target, int low, int high) {
    min = Double.MAX_VALUE;
    closestHigherHelper(root, target, low, high);

    if(currentNodeID < (int) target) return null;
    return currentNode;
}

public void closestHigherHelper(Node root, double target, int low, int high){
    if(root==null)
        return;

    if(Math.abs(root.ID - target) < min && root.ID >target){
        min = Math.abs(root.ID-target);
        currentNodeID = root.ID;
        //If between numbers
        if(root.ID >= low && root.ID <= high) currentNode = root;
    }

    if(target < root.ID){
        closestHigherHelper(root.leftChild, target, low, high);
    } else {
        closestHigherHelper(root.rightChild, target, low, high);
    }
}

这可以工作到某个点。在这里，我添加了可以在Binary Tree picture上看到的所有节点，并开始找到最接近某些值的点，然后一旦找到，删除它们。 （删除工作正常）。

BinaryTree binaryTree = new BinaryTree();
binaryTree.add(130);
...

int[] IDArray = new int[]{125, 100, 120, 130};
for (int i = 0; i < IDArray.length; i++) {
    Node closestHigher = binaryTree.closestHigherValue(binaryTree.root, IDArray[i], IDArray[i]+4, IDArray[i]+9);
    System.out.println("Searching for" + IDArray[i] + " and Closest Value = "+ closestHigher.getID());
    binaryTree.deleteNode(binaryTree.root, IDArray[i]);
        }

这让我回报：

Searching for 125 and Closest value = 130   //Should be 130
Searching for 100 and Closest value = null   //Should be null
Searching for 120 and Closest value = 125   //Should be 125
Searching for 130 and Closest value = 125   //Should be 135 -- This one goes wrong

由于最接近的下部是相似的，因此无需显示该代码，并且我可以在以后修复此代码时进行修复。

有任何想法吗？

Answer 1

我认为你应该只在“边界”内更新min，所以这个：

 min = Math.abs(root.ID-target);
 currentNodeID = root.ID;
 //If between numbers
 if(root.ID >= low && root.ID <= high) currentNode = root;

应该

 //If between numbers
 if(root.ID >= low && root.ID <= high){
    currentNode = root; 
    min = Math.abs(root.ID-target);
    currentNodeID = root.ID;
 }