首页 > 代码库 > 在二叉查找树中查找不小于某个值的最小数值
在二叉查找树中查找不小于某个值的最小数值
给定一颗二叉查找树，给定一个值value，求该二叉查找树中不小于某个值value的最小数值。
思考：二叉查找树的特征就是左子节点比父节点值小，右子节点比父节点值大。在获得该二叉查找树根节点的情况下，想要得到该二叉查找树中不小于某个值得最小数值，分以下几点考虑：
1.如果currentNode.getData() == value , 则currentNode节点即为所求节点。
2.如果currentNode.getData() < value , 则当前节点的左子树所有节点的值均小于value, 所
以不需要在左子树中考虑，将搜索范围缩小在右子树中查找。
3.如果currentNode.getData() > value , 则将搜索范围缩小在当前节点和其左子树中查找。更细点讲，如果当前节点的左子树中最大节点值小于value，那么当前节点即为所求，如果当前节点的左子树中最大节点值不小于value，那么将搜索范围缩小在左子树中。
所以，我们采用递归来实现。
节点类：
public class Node { int data; Node left; Node right; public Node(){} public Node(int data) { this.data=http://www.mamicode.com/data;>搜索树类：
public class SearchTree { Node root; public Node createTree() { Scanner scan=new Scanner(System.in); int number=scan.nextInt(); if(number==0) { return null; } Node node=new Node(number); node.setLeft(createTree()); node.setRight(createTree()); root=node; return node; } public Node findTree(Node root, int value) { if(root==null) { return null; } Node iter=root; if(iter.data<value) { return findTree(iter.right,value); } else if(iter.data=http://www.mamicode.com/=value)>测试类：
public class Test { public static void main(String [] args) { SearchTree searchTree=new SearchTree(); Node root=searchTree.createTree(); //System.out.println("success"); int value=http://www.mamicode.com/98;">="+value+": "+searchTree.findTree(root, value).getData()); value=http://www.mamicode.com/99;">="+value+": "+searchTree.findTree(root, value).getData()); value=http://www.mamicode.com/106;">="+value+": "+searchTree.findTree(root, value).getData()); value=http://www.mamicode.com/108;">="+value+": "+searchTree.findTree(root, value).getData()); value=http://www.mamicode.com/115;">="+value+": "+searchTree.findTree(root, value).getData()); }}输入：100 90 70 60 0 0 85 0 0 95 92 0 0 98 0 0 110 105 0 107 0 0 125 0 0
测试结果：
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。