在二叉搜索树中查找 floor 和 ceil 的 Golang 程序

二叉搜索树（Binary Search Tree，简称 BST）是一种二叉树结构，它的每个节点都比它的左子树中的所有节点大，比它的右子树中的所有节点小。我们可以通过这种特性来实现在 BST 中查找 floor 和 ceil 的值。

刚才提到过，BST 中每个节点都比它的左子树中的节点大，比它的右子树中的节点小。因此，我们可以使用递归方法来查找 floor 和 ceil 的节点。

查找 floor

假设要在 BST 中查找某个值 x 的 floor 的节点。我们可以从根节点开始遍历 BST，如果当前节点的值大于 x，那么我们往当前节点的左子树中继续查找；如果当前节点的值小于或等于 x，那么它可能是 x 的 floor 的节点，我们记录下来并往右子树中查找。如果右子树中没有比 x 更靠近的节点，那么当前节点就是 x 的 floor 的节点。

示例代码如下：

func floor(root *TreeNode, x int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == x {
        return root
    }
    if root.Val > x {
        return floor(root.Left, x)
    }
    rightFloor := floor(root.Right, x)
    if rightFloor != nil {
        return rightFloor
    }
    return root
}

查找 ceil

现在假设要查找某个值 x 的 ceil 的节点。同样，我们可以从根节点开始遍历 BST，如果当前节点的值小于 x，那么我们往当前节点的右子树中继续查找；如果当前节点的值大于或等于 x，那么它可能是 x 的 ceil 的节点，我们记录下来并往左子树中查找。如果左子树中没有比 x 更靠近的节点，那么当前节点就是 x 的 ceil 的节点。

示例代码如下：

func ceil(root *TreeNode, x int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == x {
        return root
    }
    if root.Val < x {
        return ceil(root.Right, x)
    }
    leftCeil := ceil(root.Left, x)
    if leftCeil != nil {
        return leftCeil
    }
    return root
}

完整示例代码

下面是一个完整的示例程序，它可以读入一个数组并构建成一个 BST。然后，程序提示输入一个值，输出该值的 floor 和 ceil 的节点。

package main

import (
    "fmt"
)

type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func insert(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    if root.Val > val {
        root.Left = insert(root.Left, val)
    } else {
        root.Right = insert(root.Right, val)
    }
    return root
}

func floor(root *TreeNode, x int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == x {
        return root
    }
    if root.Val > x {
        return floor(root.Left, x)
    }
    rightFloor := floor(root.Right, x)
    if rightFloor != nil {
        return rightFloor
    }
    return root
}

func ceil(root *TreeNode, x int) *TreeNode {
    if root == nil {
        return nil
    }
    if root.Val == x {
        return root
    }
    if root.Val < x {
        return ceil(root.Right, x)
    }
    leftCeil := ceil(root.Left, x)
    if leftCeil != nil {
        return leftCeil
    }
    return root
}

func main() {
    vals := []int{8, 4, 12, 2, 6, 10,14, 1, 3, 5, 7, 9, 11, 13, 15}
    var root *TreeNode
    for _, val := range vals {
        root = insert(root, val)
    }
    var x int
    fmt.Print("请输入一个整数：")
    _, err := fmt.Scanf("%d", &x)
    if err != nil {
        panic(err)
    }
    f := floor(root, x)
    if f == nil {
        fmt.Println("floor 的节点不存在")
    } else {
        fmt.Println("floor 的节点是", f.Val)
    }
    c := ceil(root, x)
    if c == nil {
        fmt.Println("ceil 的节点不存在")
    } else {
        fmt.Println("ceil 的节点是", c.Val)
    }
}

结论

在 BST 中查找某个值 x 的 floor 和 ceil 的节点，可以使用递归方法。当查找到某个节点时，如果该节点的值小于等于 x，那么它可能是 x 的 floor 的节点，往右子树中查找；如果该节点的值大于等于 x，那么它可能是 x 的 ceil 的节点，往左子树中查找。如果左子树或右子树中没有比 x 更靠近的节点，那么当前节点就是 x 的 floor 或 ceil 的节点。