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

二叉搜索树（BST）是一种二叉树，其中每个节点最多有两个孩子，通常称为左孩子和右孩子。

在这篇 Golang 文章中，我们将学习如何使用递归和迭代的方法在二叉搜索树中查找 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 - 然后，初始化一个 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

结论

我们已经成功地编译并执行了一个Go语言程序，使用递归和迭代方法在二叉搜索树中查找floor和ceil，并给出了两个例子。第一个例子中，我们使用了迭代方法，在第二个例子中，我们使用了递归方法。