二叉搜索树中求得给定元素的下界

public static BianrySearchTreeNode FloorInBST(BianrySearchTreeNode root,int data){ if(root==null) return null; if(root.getData()==data) return root; if(data<root.getData()){ //查询值小于当前节点的值 if(data<FindMin(root).getData())//小于整个树的最小值 return null; if(data>=FindMax(root.getLeft()).getData()) return FindMax(root.getLeft()); else return FloorInBST(root.getLeft(),data); } if(root.getData()<data){ //查询值大于当前节点的值 if(data>=FindMax(root.getRight()).getData())// 大于整棵树的最大值 return FindMax(root); if(data<FindMin(root.getRight()).getData())//小于右子树的最小值 return root; else return FloorInBST(root.getRight(),data); } return null; }

顺便记录一下FindMax与FindMin的函数如下：

//搜索最小元素 public static BianrySearchTreeNode FindMin(BianrySearchTreeNode root){ if(root==null) return null; while(root.getLeft()!=null) root = root.getLeft(); return root; } //搜索最大元素 public static BianrySearchTreeNode FindMax(BianrySearchTreeNode root){ if(root==null) return null; while(root.getRight()!=null) root = root.getRight(); return root; }