二分搜索树的floor跟ceil实现，老师看一下对不对
来源：2-1 集合基础和基于二分搜索树的集合实现
学无止境呀呀呀
2020-10-22 19:33:48
# 具体遇到的问题
# 报错信息的截图
# 相关课程内容截图
# 尝试过的解决思路和结果
# 粘贴全部相关代码，切记添加代码注释（请勿截图）
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;
}
1回答
-
不正确。
对于包含有 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 行）
其中的逻辑我添加了必要的注释。
继续加油！：）
1
相似问题