极客笔记Golang 在二叉搜索树中查找floor和ceil
二叉搜索树（BST）是一种二叉树，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
在这个Golang文章中，我们将学习如何使用递归和迭代方法在二叉搜索树中查找floor和ceil。二叉搜索树是一种有用的数据结构，用于高效地搜索、插入和删除元素。
语法
func ceil(root *Node, val int) int {…}
ceil()函数用于在二叉搜索树中找到向上取整的值。
func floor(root *Node, val int) int {…}
floor()函数用于在二叉搜索树中找到向下取整的值。
func floorCeil(root *Node, key int) (int, int) {…}
The floorCeil()函数是用于在二叉搜索树中递归地查找floor和ceil值的函数。
步骤
- 步骤1 - 首先，我们需要导入fmt包。
-
步骤2 - 然后，初始化一个node结构并在其中分配三个变量。第一个变量存储整数值，而第二和第三个指针变量存储左节点和右节点的地址。
-
步骤3 - 现在，创建一个insert()函数，它接受一个节点和一个要插入的值。该函数将节点值插入到适当的二叉搜索树中。
-
步骤4 - 此函数根据二叉搜索树的属性递归地搜索适当位置以插入新节点。
-
步骤5 - 现在，定义一个名为ceil()的函数。它接受一个节点根和一个值val作为输入，并返回树中大于或等于val的最小值。
-
步骤6 - 然后，定义一个名为floor()的函数。它接受一个节点根和一个值val作为输入，并返回树中小于或等于val的最大值。
-
步骤7 - 启动main()函数。在main()函数内部，向二叉搜索树中插入多个节点。
-
步骤8 - 现在，调用ceil()和floor()函数，并将整数值作为参数传递给函数。
-
步骤9 - 进一步，通过使用fmt.Println()函数将二叉搜索树的ceil和floor值打印到屏幕上。
示例1
在此示例中，我们将迭代地定义一个用于查找二叉搜索树中ceil和floor的ceil()和floor()函数。
package main
import (
"fmt"
)
type Node struct {
val int
left *Node
right *Node
}
func insert(root *Node, val int) *Node {
if root == nil {
root = &Node{val, nil, nil}
return root
}
if val < root.val {
root.left = insert(root.left, val)
} else {
root.right = insert(root.right, val)
}
return root
}
func ceil(root *Node, val int) int {
if root == nil {
return -1
}
if root.val == val {
return root.val
}
if val > root.val {
return ceil(root.right, val)
}
leftCeil := ceil(root.left, val)
if leftCeil >= val {
return leftCeil
}
return root.val
}
func floor(root *Node, val int) int {
if root == nil {
return -1
}
if root.val == val {
return root.val
}
if val < root.val {
return floor(root.left, val)
}
rightFloor := floor(root.right, val)
if rightFloor <= val {
return rightFloor
}
return root.val
}
func main() {
var root *Node
root = insert(root, 10)
insert(root, 5)
insert(root, 15)
insert(root, 1)
insert(root, 8)
insert(root, 12)
insert(root, 18)
fmt.Println("Floor of 9:", floor(root, 9))
fmt.Println("Ceil of 9:", ceil(root, 9))
fmt.Println("Floor of 11:", floor(root, 11))
fmt.Println("Ceil of 11:", ceil(root, 11))
}
输出
Floor of 9: -1
Ceil of 9: 10
Floor of 11: -1
Ceil of 11: 12
示例2
在这个示例中，我们将递归地定义一个floorCeil()函数，用于在二叉搜索树中找到 ceil 和 floor。
package main
import (
"fmt"
)
type Node struct {
val int
left *Node
right *Node
}
func newnode(val int) *Node {
node := &Node{}
node.val = val
node.left = nil
node.right = nil
return node
}
func floorCeil(root *Node, key int) (int, int) {
floor := -1
ceil := -1
if root == nil {
return floor, ceil
}
if root.val == key {
return root.val, root.val
}
if root.val > key {
ceil = root.val
f, c := floorCeil(root.left, key)
if f != -1 {
floor = f
}
if c != -1 && c < ceil {
ceil = c
}
} else {
floor = root.val
f, c := floorCeil(root.right, key)
if f != -1 && f > floor {
floor = f
}
if c != -1 {
ceil = c
}
}
return floor, ceil
}
func main() {
root := newnode(8)
root.left = newnode(4)
root.right = newnode(12)
root.left.left = newnode(2)
root.left.right = newnode(6)
root.right.left = newnode(10)
root.right.right = newnode(14)
key := 14
floor, ceil := floorCeil(root, key)
fmt.Printf("Floor of %d is %d\n", key, floor)
fmt.Printf("Ceil of %d is %d\n", key, ceil)
key = 11
floor, ceil = floorCeil(root, key)
fmt.Printf("Floor of %d is %d\n", key, floor)
fmt.Printf("Ceil of %d is %d\n", key, ceil)
key = 5
floor, ceil = floorCeil(root, key)
fmt.Printf("Floor of %d is %d\n", key, floor)
fmt.Printf("Ceil of %d is %d\n", key, ceil)
}
输出
Floor of 14 is 14
Ceil of 14 is 14
Floor of 11 is 10
Ceil of 11 is 12
Floor of 5 is 4
Ceil of 5 is 6
结论
我们已成功地编译和执行了使用递归和迭代方法在二叉搜索树中找到floor和ceil的go语言程序，并附带两个示例。在第一个示例中，我们使用了迭代方法，在第二个示例中，我们使用了递归方法。