如何找到最接近的元素给定的键值中的二叉搜索树？ [英] How to find the closest element to a given key value in a binary search tree?

问题描述

考虑到与整型值的BST作为钥匙我怎么找到最近的节点在一个BST的关键？ 该BST重新presented使用节点的对象（JAVA）。最近的将是如4,5,9，如果关键是6将返回5。

Given a bst with integer values as keys how do I find the closest node to that key in a bst ? The BST is represented using a object of nodes (Java). Closest will be for eg 4,5,9 and if the key is 6 it will return 5 ..

推荐答案

遍历树，你会找到的元素。当你这样做的记录最接近你的键的值。现在，当你没找到钥匙本身返回的记录值的节点。

Traverse the tree as you would to find the element. While you do that record the value that is closest to your key. Now when you didn't find a node for the key itself return the recorded value.

所以，如果你正在寻找 3 在下面的树中的关键，你最终会在节点上 6 没有找到比赛，但你的入账价值应为 2 ，因为这是你曾经走过的所有节点（最接近的关键 2 ， 7 ， 6 ）。

So if you were looking for the key 3 in the following tree you would end up on the node 6 without finding a match but your recorded value would be 2 since this was the closest key of all nodes that you had traversed (2,7,6).

                 2
              1      7
                   6   8

这篇关于如何找到最接近的元素给定的键值中的二叉搜索树？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！