二叉搜索树（BST）Go实现

王致列

于 2021-12-05 22:40:25 发布

阅读量1k

点赞数

分类专栏： Golang学习笔记文章标签： golang 深度优先数据结构搜索二叉树 BST

本文链接：https://blog.csdn.net/star_of_science/article/details/121737125

版权

这篇博客介绍了二叉搜索树（BST）的基本概念，包括其定义、插入操作的实现、中序遍历的递归和迭代方法，以及验证BST合法性的递归算法。此外，还讨论了如何在BST中删除节点，并实现了一个二叉搜索树的迭代器类。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

BST定义

二叉搜索树是二叉树的一种特殊表示形式，它满足如下特性：

每个节点中的值必须大于（或等于）存储在其左侧子树中的任何值。
每个节点中的值必须小于（或等于）存储在其右子树中的任何值。

//定义二叉树节点
type TreeNode struct {    
	Val int    
	Left *TreeNode    
	Right *TreeNode
}
//定义二叉树
type BinareSearchTree struct {    
	Root *TreeNode
}

二叉搜索树中的插入操作

给定二叉搜索树（BST）的根节点和要插入树中的值，将值插入二叉搜索树。返回插入后二叉搜索树的根节点。输入数据保证，新值和原始二叉搜索树中的任意节点值都不同。

注意，可能存在多种有效的插入方式，只要树在插入后仍保持为二叉搜索树即可。你可以返回任意有效的结果。

示例：
输入：root = [4,2,7,1,3], val = 5
输出：[4,2,7,1,3,5]

BST插入的实现

func insertIntoBST(root *TreeNode, val int) *TreeNode {
    if root == nil {
        return &TreeNode{Val: val}
    }
    p := root
    for p != nil {
        if val < p.Val {
            if p.Left == nil {
                p.Left = &Tre

最低0.47元/天解锁文章