BST golang搜索函数

二叉搜索树（Binary Search Tree，简称BST）是一种特殊的二叉树，其中每个节点的值都大于其左子树中的所有节点的值，并且小于其右子树中的所有节点的值。这种性质使得搜索操作非常高效。

基础概念

节点：树的基本单元，包含一个值和两个指向子节点的指针。
根节点：树的起始节点。
左子树：所有值小于当前节点值的子树。
右子树：所有值大于当前节点值的子树。

优势

搜索效率高：平均时间复杂度为O(log n)。
插入和删除操作相对较快：同样平均时间复杂度为O(log n)。
有序性：可以方便地进行范围查询。

类型

普通二叉搜索树
平衡二叉搜索树（如AVL树、红黑树）

应用场景

快速查找、插入和删除操作。
实现关联数组。
数据库索引。

Golang 实现搜索函数

以下是一个简单的二叉搜索树结构和搜索函数的Golang实现：

package main

import "fmt"

// TreeNode 定义树节点结构
type TreeNode struct {
    Value int
    Left  *TreeNode
    Right *TreeNode
}

// Search 在BST中搜索特定值
func Search(root *TreeNode, value int) bool {
    if root == nil {
        return false
    }
    if root.Value == value {
        return true
    } else if root.Value > value {
        return Search(root.Left, value)
    } else {
        return Search(root.Right, value)
    }
}

func main() {
    // 构建一个简单的BST
    root := &TreeNode{Value: 10}
    root.Left = &TreeNode{Value: 5}
    root.Right = &TreeNode{Value: 15}
    root.Left.Left = &TreeNode{Value: 3}
    root.Left.Right = &TreeNode{Value: 7}

    // 测试搜索函数
    fmt.Println(Search(root, 7))  // 输出: true
    fmt.Println(Search(root, 8))  // 输出: false
}