二分搜索树的floor跟ceil实现，老师看一下对不对

# 具体遇到的问题

# 报错信息的截图

# 相关课程内容截图

# 尝试过的解决思路和结果

# 粘贴全部相关代码，切记添加代码注释（请勿截图）

public E floor(E e){
return floor(root,e).data;
}
private Node floor(Node node,E e){
if (node.data.compareTo(e)<0){
node=floor(node.right,e);
}else if(node.data.compareTo(e)>0){
node=floor(node.left,e);
}else{
return node.left;
}
return node;
}
public E ceil(E e){
return ceil(root,e).data;
}
private Node ceil(Node node,E e){
if (node.data.compareTo(e)<0){
node=ceil(node.right,e);
}else if(node.data.compareTo(e)>0){
node=ceil(node.left,e);
}else{
return node.right;
}
return node;
}

学无止境呀呀呀 2020-10-22

源自：二分搜索树 2-1 集合基础和基于二分搜索树的集合实现

收起

1回答

liuyubobobo 回答被采纳获得+3积分 2020-10-23 05:55:32

不正确。

对于包含有 1 3 5 7 9 五个节点的 BST，

0 1 2 3 4 5 6 7 8 9 10 所对应的 floor 值应该是：null 1 1 3 3 5 5 7 7 9 9

0 1 2 3 4 5 6 7 8 9 10 所对应的 ceil 值应该是：1 1 3 3 5 5 7 7 9 9 null

整体测试方式和之前我们学习二分搜素测试 floor 和 ceil 的方式是一致的。你可以据此再自己涉及其他的测试用例。

对于这是我给出的测试代码（你的代码会报空指针异常）：

public static void main(String[] args) {

    BST<Integer> bst = new BST<>();
    for(int i = 1; i < 10; i += 2)
        bst.add(i);
 
    System.out.print("floor : ");
    for(int i = 0; i <= 10; i ++)
        System.out.print(bst.floor(i) + " ");
    System.out.println();
    
    System.out.print("ceil  : ");
    for(int i = 0; i <= 10; i ++)
        System.out.print(bst.ceil(i) + " ");
    System.out.println();
}

对于 BST 中求解 floor 和 ceil，我的参考代码见这里：https://git.imooc.com/class-105/Play-Algorithms-and-Data-Structures/src/master/15-Binary-Search-Tree/Optional-01-Floor-and-Ceil-in-BST/src/BST.java （316 行 - 407 行）

其中的逻辑我添加了必要的注释。

继续加油！：）

收起回答