对于floor的实现
来源：1-15 更多二分搜索树相关话题
warren_au
2020-10-07 19:39:04
public E floor(E e) {
if (e.compareTo(minimum()) < 0) {
return null;
}
Node floorNode = floor(root, e);
return floorNode.e;
}
private Node floor(Node node, E e) {
if (node == null) {
return null;
}
if (e.compareTo(node.e) < 0) {
return floor(node.left, e);
}
else {//e.compareTo(node.e) > 0
Node tempNode = floor(node.right, e);
if (tempNode != null) {
return tempNode;
}
return node;
}
}
对加了下划线的那段代码不太明白，这里递归终止的条件只能是当node==null才会终止，如果是这样那么tempNode永远都不可能部位空啊，这样的话要这个判断是否失去了意义？
1回答
-
我假设你看的是我的《C++ 算法与数据结构》这个课程的这个代码：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(Java)/Optional-05-Floor-and-Ceil-in-BST/src/bobo/algo/BST.java
以下测试用例，在程序运行过程中，tempNode 不为空。
public static void main(String[] args) { BST<Integer, Integer> bst = new BST<Integer, Integer>(); bst.insert(8, null); bst.insert(2, null); bst.insert(4, null); bst.insert(3, null); bst.insert(5, null); System.out.println(bst.floor(6)); }你可以在 if(tempNode != null) 中做一个打印，来验证这一点：
if(tempNode != null){ System.out.println("!!!"); return tempNode; }看看 ！！！ 能不能被打印出来？
我强烈建议你先使用纸笔，把这个测试用例画出来，然后手动使用这个算法走一遍，看看结果是怎样的？再使用这个测试用例，实际的跟踪一下程序，看一下程序为什么会在某些节点返回一个不为空的 tempNode？你的思考到底哪里是错误的？进步就在这个过程中哦。
于此同时，我强烈建议你从递归算法的宏观语义的角度，再仔细理解一下，这个代码的意思。
P.S.
如果你需要更小的测试用例，如下的包含三个节点的树，就可以打出！！！：
BST<Integer, Integer> bst = new BST<Integer, Integer>(); bst.insert(8, null); bst.insert(2, null); bst.insert(4, null); System.out.println(bst.floor(6));
加油！：）
1
相似问题
回答 2
回答 2