数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学Go语言程序：在二叉搜索树中查找floor和ceil值
二叉搜索树 (BST) 是一种二叉树，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
在这篇Go语言文章中，我们将学习如何使用递归和迭代方法在二叉搜索树中查找floor和ceil值。二叉搜索树是一种用于高效搜索、插入和删除元素的有用数据结构。
语法
func ceil(root *Node, val int) int {…}
ceil()函数用于在二叉搜索树中查找ceil值。
func floor(root *Node, val int) int {…}
floor()函数用于在二叉搜索树中查找floor值。
func floorCeil(root *Node, key int) (int, int) {…}
floorCeil()函数用于递归地在二叉搜索树中查找floor和ceil值。
算法
步骤1 - 首先，我们需要导入fmt包。
步骤2 - 然后，初始化一个节点结构体并在其中分配三个变量。第一个变量存储整数值，而第二个和第三个指针变量分别存储指向左节点和右节点的地址。
步骤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
结论
我们已经成功地编译并执行了一个Go语言程序，该程序使用递归和迭代方法在二叉搜索树中查找floor和ceil值，并附带两个示例。在第一个示例中，我们使用了迭代方法，在第二个示例中，我们使用了递归方法。
浏览量：172
