关于floor与ceil递归终止条件判断的优化

Question

老师好，我再看了这一章之后，自己实现这个二分搜索树的floor与ceil方法，但在做条件判断的时候，发现很麻烦，代码写得也比较繁琐，也没有想到简化的思路。但我觉得不应该这么复杂，所以想请老师帮我看看这两个地方的代码应该怎么优化
floor:

// 查找二分搜索树指定元素floor
func (tree *BasicTree) floor(node *Node, e interface{}) *Node {
	if node == nil {
		return nil
	}
	// 判断，如果e<node.element，则其floor肯定在node的左子树中
	// 递归退出条件：找到floor则退出，这里退出有两种情况
	// 1. e < node.element的情况下，node.left==nil，说明没有floor节点，最小的节点元素都比e大
	if interfaces.Compare(e, node.Element) == -1 && node.Left == nil {
		return nil
	}
	// 2. e > node.element的情况下，e<node.right.element或者node.right==nil,此时当前node就是e的floor节点
	if interfaces.Compare(e, node.Element) == 1 && (node.Right == nil || (interfaces.Compare(e, node.Right.Element) == -1 &&((node.Right.Left == nil) || interfaces.Compare(node.Right.Left.Element, e)== 1))) {
	// 写法太麻烦，需要优化
		return node
	}
	// 3. e等于node.element，e的节点就是其本身
	if interfaces.Compare(e, node.Element) == 0 {
		return node
	}
	// 4. 递归调用
	if interfaces.Compare(e, node.Element) == 1 {
		return tree.floor(node.Right, e)
	} else {
		return tree.floor(node.Left, e)
	}
}

ceil:

// 查找二分搜索树指定元素(FN)的ceil节点
func (tree *BasicTree) ceil(node *Node, e interface{}) *Node {
	if node == nil {
		return nil
	}
	// 递归终止条件
	// 1. FN > node.element 分情况判断
		// 1. node.Right == nil, 表示没有满足条件的ceil，因为整个二分搜索树都比该节点小
	if interfaces.Compare(e, node.Element) == 1 && node.Right == nil {
		return nil
	}else if (interfaces.Compare(e, node.Element) == -1 && (node.Left == nil || (interfaces.Compare(e, node.Left.Element) == 1 && (node.Left.Right == nil || interfaces.Compare(node.Left.Right.Element, e) == -1)))){
		// 写法太麻烦，需要优化
		return node
	}
	// 3. FN = node.element, node就是FN的ceil
	if interfaces.Compare(e, node.Element) == 0 {
		return node
	}
	// 4. 递归调用(缩减规模)
	if interfaces.Compare(e, node.Element) == 1 {
		return tree.ceil(node.Right, e)
	} else {
		// FN(e)<node.Element
		return tree.ceil(node.Left, e)
	}
}

代码是用go实现的，就是我在代码中标注写法太麻烦的地方

1. floor：比指定元素小的最大的元素

1. floor与前驱节点的主要区别在于floor不一定在我们的二分搜索树里面，而前驱节点一定包含在二分搜索树中,但如果指定元素存在于二分搜索树中，那么这个元素的floor就是其本身
2. 具体思路如下
3. 设要查询的元素为节点FN
4. 如果FN的值小于当前node的值，那么FN的floor节点一定在当前node节点的左子树中
5. 如果FN的值大于当前node的值，那么node的值可能是FN的floor节点，但也可能不是
   1. 需要和当前node的右子树进行比较
      1. 如果FN小于右子节点，分以下情况
         1. 该右子节点没有左子树，则node就是FN的floor节点
         2. 该右子节点有左子树，但其左子节点比FN要大，则node就是FN的floor节点
         3. 该右子节点有左子树，且其左子节点比FN小，此时该左子节点的值一定会大于node，所以应该传入以node的右子节点为根的新的二叉树，也就是缩减规模
      2. 如果FN大于右子节点，则以右子节点为根的二叉树进行传递，缩减规模
6. ceil：比指定元素大的最小的元素
   1. ceil查找与floor查找思路类似
      1. 设要查询的元素为节点FN
      2. 如果FN大于当前节点的值，则FN与当前节点的右子树再进行比较
         1. 如果右子树为空，则说明找不到FN的ceil节点
         2. 如果右子树不为空
            1. FN>右子节点的值，继续找右子节点的右子树
            2. FN<右子节点的值，则进行第2大步
      3. 如果FN的节点小于当前node的值，node的值可能是FN的ceil节点，但也可能不是
         1. 需要用FN和当前节点的左子树进行比较。如果当前节点没有左子树，则当前node就是FN的ceil
         2. 如果当前左子节点的值大于FN，则需要继续向后面的左子树比较，同样采用递归的方式
         3. 如果FN大于当前节点左子节点，则需要将FN与当前节点的左子节点的右子树进行比较
            1. 如果没有右子树，则当前node就是FN的ceil
            2. 如果右子节点的值小于FN，则当前node就是FN的ceil
            3. 如果右子节点的值大于FN，则继续以当前节点的左子节点为根的二分搜索树进行查找

这个是我的判断思路，老师能不能帮忙看一下，谢谢啦

Answer 1

liuyubobobo 2019-06-19 13:16:38

抱歉，我不是特别了解go语言。不过在我之前的课程《数据结构和算法》中，我曾经补充了二分搜索树的floor和ceil的实现。可以参考一下。在补充代码中，我写了详细的注释：）

C++版：https://github.com/liuyubobobo/Play-with-Algorithms/blob/master/05-Binary-Search-Tree/Course%20Code%20(C%2B%2B)/Optional-05-Floor-and-Ceil-in-BST/main.cpp

Java版：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

继续加油！：）

• 提问者 残天一月 #1

  老师您好，在《数据结构与算法》中是第5章对么？具体是哪一节呢？正好我也买了，我去看一下

• liuyubobobo 回复 提问者 残天一月 #2

  课程中这个算法我没有讲。是在课程的补充代码中。看一下代码中，有详细的注释。Java代码在我给的文件330-381行：）

• 提问者 残天一月 回复 liuyubobobo #3

  好的，已经在看了，对比了一下，我可能想得太复杂化了！谢谢老师

点开查看后面2条评论