資料結構
網路
關係資料庫管理系統 (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
