Go的数据结构与实现【Binary Search Tree】

介绍

本文用Go将实现二叉搜索树数据结构,以及常见的一些方法

二叉树

二叉树是一种递归数据结构,其中每个节点最多可以有两个子节点。

二叉树的一种常见类型是二叉搜索树,其中每个节点的值都大于或等于左子树中的节点值,并且小于或等于右子树中的节点值。

这是这种二叉树的直观表示:
在这里插入图片描述
实现细节方面,我们将使用一个辅助Node结构体来存储值,并保留对每个孩子的引用:

type T inttype Node struct {val   Tleft  *Noderight *Node
}

然后我们将添加树的起始节点,通常称为根:

type BinSearchTree struct {sync.RWMutexroot *Node
}

常见操作

现在让我们看看我们可以在二叉树上执行的最常见的操作。

插入

我们要介绍的第一个操作是插入新节点。
首先,我们必须找到要添加新节点的位置,以保持树的排序。我们将从根节点开始寻找,遵循这些规则:

  • 如果新节点的值小于当前节点的值,我们去左孩子
  • 如果新节点的值大于当前节点的值,我们去右孩子
  • 如果当前节点为空时,我们到达了一个叶节点,我们可以在该位置插入新节点

然后我们将创建一个递归方法来进行插入:

// insert internal function to find the correct place for a node in a tree
func insert(root, node *Node) {if node.val < root.val {if root.left == nil {root.left = node} else {insert(root.left, node)}} else {if root.right == nil {root.right = node} else {insert(root.right, node)}}
}

接下来我们将创建从根节点开始递归的公共方法:

// Insert inserts the val in the tree
func (bst *BinSearchTree) Insert(val T) {bst.Lock()defer bst.Unlock()node := NewTree(val)if bst.root == nil {bst.root = node} else {insert(bst.root, node)}
}

搜索

现在让我们添加一个方法来检查树是否包含特定值。

和以前一样,我们将首先创建一个遍历树的递归方法:

// search internal recursive function to search t in the tree
func search(root *Node, t T) bool {if root == nil {return false}if root.val == t {return true}if root.val > t {return search(root.left, t)} else {return search(root.right, t)}
}

在这里,我们通过将其与当前节点中的值进行比较来搜索该值;然后,我们将根据结果继续左或右孩子。

接下来我们将创建从根开始的公共方法:

// Search returns true if the t exists in the tree
func (bst *BinSearchTree) Search(t T) bool {bst.RLock()defer bst.RUnlock()return search(bst.root, t)
}

删除

另一种常见的操作是从树中删除一个节点。

首先,我们必须以与之前类似的方式找到要删除的节点:

// remove internal recursive function to remove t
func remove(root *Node, t T) {if root == nil {return}if root.val > t {remove(root.left, t)} else if root.val < t {remove(root.right, t)} else {if root.left == nil && root.right == nil {root = nilreturn} else if root.left == nil {root = root.rightreturn} else if root.right == nil {root = root.leftreturn} else {leftMostRightSide := root.rightfor {//find the smallest value on the right sideif leftMostRightSide != nil && leftMostRightSide.left != nil {leftMostRightSide = leftMostRightSide.left} else {break}}root.val = leftMostRightSide.valremove(root.right, root.val)return}}
}

一旦我们找到要删除的节点,主要有 3 种不同的情况:

  • 没有孩子:这是最简单的情况;我们只需要在它的父节点中用nil替换这个节点
  • 只有一个孩子:在父节点中,我们用它唯一的孩子替换这个节点。
  • 有两个孩子:这是最复杂的情况,因为它需要树重组

最后,我们将创建从根开始删除的公共方法:

// Remove removes the t from the tree
func (bst *BinSearchTree) Remove(t T) {bst.Lock()defer bst.Unlock()remove(bst.root, t)
}

遍历树

在本节中,我们将探索遍历树的不同方法,前序、中序和后序遍历,这里暂时只实现递归的方法。

前序

// PreOrder visits all nodes with pre-order traversing
func (bst *BinSearchTree) PreOrder(f func(T)) {bst.Lock()defer bst.Unlock()preOrder(bst.root, f)
}// preOrder internal recursive function to traverse pre-order
func preOrder(root *Node, f func(T)) {if root != nil {f(root.val)inOrder(root.left, f)inOrder(root.right, f)}
}

中序

// InOrder visits all nodes with in-order traversing
func (bst *BinSearchTree) InOrder(f func(T)) {bst.Lock()defer bst.Unlock()inOrder(bst.root, f)
}// inOrder internal recursive function to traverse in-order
func inOrder(root *Node, f func(T)) {if root != nil {inOrder(root.left, f)f(root.val)inOrder(root.right, f)}
}

后序

// PreOrder visits all nodes with pre-order traversing
func (bst *BinSearchTree) PreOrder(f func(T)) {bst.Lock()defer bst.Unlock()preOrder(bst.root, f)
}// preOrder internal recursive function to traverse pre-order
func preOrder(root *Node, f func(T)) {if root != nil {f(root.val)inOrder(root.left, f)inOrder(root.right, f)}
}

其他

本文还提供了一些其他方法,如:

  • Max()、Min():获取二叉搜索树中最大或最小值
  • Print():打印二叉搜索树
// Min returns the minimal value stored in the tree
func (bst *BinSearchTree) Min() *T {bst.RLock()defer bst.RUnlock()root := bst.rootif root == nil {return nil}for {if root.left == nil {return &root.val}root = root.left}
}// Max returns the maximal value stored in the tree
func (bst *BinSearchTree) Max() *T {bst.RLock()defer bst.RUnlock()root := bst.rootif root == nil {return nil}for {if root.right == nil {return &root.val}root = root.right}
}func (bst *BinSearchTree) Print() {bst.Lock()defer bst.Unlock()fmt.Println("------------------------------------------------")stringify(bst.root, 0)fmt.Println("------------------------------------------------")
}func stringify(root *Node, level int) {if root != nil {format := ""for i := 0; i < level; i++ {format += "       "}format += "---[ "level++stringify(root.left, level)fmt.Printf(format+"%d\n", root.val)stringify(root.right, level)}
}

单元测试

import ("testing"
)const (t1 T = iota + 1t2t3t4t5t6t7t8t9t10t11
)func InitTree() *BinSearchTree {bst := NewBinSearchTree()bst.Insert(t3)bst.Insert(t2)bst.Insert(t4)bst.Insert(t9)bst.Insert(t5)bst.Insert(t6)bst.Insert(t10)bst.Insert(t1)bst.Insert(t7)bst.Insert(t8)return bst
}func TestBinSearchTree_Insert(t *testing.T) {bst := InitTree()bst.Print()bst.Insert(t11)bst.Print()
}func TestBinSearchTree_InOrder(t *testing.T) {var ret []Tbst := InitTree()bst.InOrder(func(t T) {ret = append(ret, t)})expected := []T{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}if !isSameSlice(ret, expected) {t.Errorf("Traversal order incorrect, got %v", ret)}
}// isSameSlice returns true if the 2 slices are identical
func isSameSlice(a, b []T) bool {if a == nil && b == nil {return true}if a == nil || b == nil {return false}if len(a) != len(b) {return false}for i := range a {if a[i] != b[i] {return false}}return true
}

部分测试结果:

=== RUN   TestBinSearchTree_Insert
---------------------------------------------------[ 1---[ 2
---[ 3---[ 4---[ 5---[ 6---[ 7---[ 8---[ 9---[ 10
------------------------------------------------
---------------------------------------------------[ 1---[ 2
---[ 3---[ 4---[ 5---[ 6---[ 7---[ 8---[ 9---[ 10---[ 11
------------------------------------------------
--- PASS: TestBinSearchTree_Insert (0.00s)
PASS

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/293473.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

脑机辅助推导算法

目录 一&#xff0c;背景 二&#xff0c;华容道中道 1&#xff0c;问题 2&#xff0c;告诉脑机如何编码一个正方形格子 3&#xff0c;让脑机汇总信息 4&#xff0c;观察图&#xff0c;得到启发式算法 5&#xff0c;根据启发式算法求出具体解 6&#xff0c;可视化 一&am…

centos7.5安装gitlab-runner,配置CI/CD流水线

一般不建议gitlab-server和gitlab-runner装在同一台服务器 第一步&#xff1a;安装gitlab-runner,最好和gitlab实例版本一致 # 下载官方gitlab-runner安装脚本 curl -L "https://packages.gitlab.com/install/repositories/runner/gitlab-runner/script.rpm.sh" | s…

时序预测 | Python实现VMD-CNN-LSTM时间序列预测

时序预测 | Python实现VMD-CNN-LSTM时间序列预测 目录 时序预测 | Python实现VMD-CNN-LSTM时间序列预测预测效果基本介绍模型描述代码设计预测效果 基本介绍 VMD-CNN-LSTM 是一种混合深度学习模型,结合了变分模态分解(VMD)、卷积神经网络(CNN)和长短期记忆网络(LSTM)的…

【spring】@Autowired注解学习

Autowired介绍 Spring框架是Java领域中一个非常重要的企业级应用开发框架&#xff0c;它提供了全面的编程和配置模型&#xff0c;旨在帮助开发者更快速、更简单地创建应用程序。在Spring框架中&#xff0c;Autowired是一个非常重要的注解&#xff0c;它用于实现依赖注入&#…

Chatopera 云服务的智能问答引擎实现原理,如何融合 #聊天机器人 技术 #Chatbot #AI #NLP

观看视频 Bilibili: https://www.bilibili.com/video/BV1pZ421q7EH/YouTube: https://www.youtube.com/watch?vx0d1_0HQa8o 内容大纲 提前在浏览器打开网址&#xff1a; Chatopera 云服务&#xff1a;https://bot.chatopera.comChatopera 入门教程&#xff1a;https://dwz…

Web应急响应

2024年护网将至&#xff0c;最近我将分享一些红蓝对抗的一些技巧&#xff0c;应急响应、信息收集相关的知识概念以及相关技巧。 目录 1. 黑客攻击流程 2. webshell流量特征 1.1.菜刀特征 1.2.冰蝎3.0 &#xff1a; 1.3.冰蝎2.0&#xff1a; 1.4.冰蝎3.11流量特征 1.5.蚁…

LeetCode-56. 合并区间【数组 排序】

LeetCode-56. 合并区间【数组 排序】 题目描述&#xff1a;解题思路一&#xff1a;排序&#xff1f;怎么排&#xff1f;当然是排各个区间的左边界&#xff0c;然后判断下一个边界的左边界与结果数组里面的右边界是否重叠。解题思路二&#xff1a;优化解题思路三&#xff1a;0 题…

MongoDB Atlas维护指南:常见类型、注意事项与窗口设置

为了给Atlas用户更好的产品体验&#xff0c;MongoDB产品团队会进行定期维护。 本文将会介绍&#xff1a; 常见维护项目种类及频率&#xff0c;注意事项维护期间的影响及建议维护窗口设置说明维护告警设置和邮件通知范例 维护窗口常见项目 定期SSL证书轮换软件升级&#xff…

基于单片机16位智能抢答器设计

**单片机设计介绍&#xff0c;基于单片机16位智能抢答器设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 基于单片机16位智能抢答器设计是一个结合了单片机技术、显示技术、按键输入技术以及声音提示技术的综合性项目。其设计…

【QT】setContextMenuPolicy()函数用法

在Qt中&#xff0c;setContextMenuPolicy() 是一个相当通用的方法&#xff0c;几乎所有的继承自 QWidget 或其派生类的图形用户界面控件都可以使用该方法来设置它们的上下文菜单策略。这意味着&#xff0c;包括但不限于以下常见的Qt GUI控件都能使用 setContextMenuPolicy() 来…

ssm 科研奖励申报管理系统开发mysql数据库web结构java编程计算机网页源码eclipse项目

一、源码特点 ssm 科研奖励申报管理系统是一套完善的信息系统&#xff0c;结合springMVC框架完成本系统&#xff0c;对理解JSP java编程开发语言有帮助系统采用SSM框架&#xff08;MVC模式开发&#xff09;&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用…

Python数据分析与可视化笔记 七 Numpy ndarray

多维数组对象ndarray&#xff0c;常用属性如下所示 import numpy as nparr np.array([[1,2,3],[4,5,6]]) print(arr.shape) #ndarray各维度的长度 print(arr.ndim) #ndarray的维度 print(arr.size) #ndarray中元素的个数&#xff0c;相当于各维度长度的乘积 print(arr.dtyp…

iOS问题记录 - App Store审核新政策:隐私清单 SDK签名(持续更新)

文章目录 前言开发环境问题描述问题分析1. 隐私清单 & SDK签名1.1. 隐私清单 - 数据使用声明1.2. 隐私清单 - 所用API原因描述1.3. SDK签名 2. 即将发布的第三方SDK要求 解决方案最后 前言 前段时间用Flutter开发的iOS App提交了新版本&#xff0c;结果刚过两分钟就收到了…

智慧公厕四大核心能力,赋能城市公共厕所智能化升级

公共厕所是城市基础设施中不可或缺的一部分&#xff0c;但由于传统的公共厕所在建设与规划上&#xff0c;存在一定的局限性&#xff0c;导致环境卫生差、管理难度大、使用体验不佳等问题&#xff0c;给市民带来了很多不便。而智慧公厕作为城市智能化建设的重要组成部分&#xf…

【Linux多线程】生产者消费者模型

【Linux多线程】生产者消费者模型 目录 【Linux多线程】生产者消费者模型生产者消费者模型为何要使用生产者消费者模型生产者消费者的三种关系生产者消费者模型优点基于BlockingQueue的生产者消费者模型C queue模拟阻塞队列的生产消费模型 伪唤醒情况&#xff08;多生产多消费的…

RUST使用crates.io上的依赖完整教程

1.打开crates.io 2.搜索要使用的依赖,如rand 点击包名,进入包详情页面: 添加依赖方法有两种 1.使用cargo命令 2.直接修改Cargo.toml 使用cargo命令操作如下: 在工程目录执行如下命令: cargo add rand 执行完成后如自动向Cargo.toml中添加依赖如下: 手动修改Cargo.toml是…

STM32使用USART发送数据包指令点亮板载LED灯

电路连接&#xff1a; 连接显示屏模块&#xff0c;显示屏的SCL在B10&#xff0c;SDA在B11。 程序目的&#xff1a; 发送LED_ON指令打开板载LED灯&#xff0c;发送LED_OFF关闭板载LED灯&#xff0c;与上一个博客不同&#xff0c;这个实际上是实现串口收发文本数据包。 …

前端学习<二>CSS基础——14-CSS3属性详解:Web字体

前言 开发人员可以为自已的网页指定特殊的字体&#xff08;将指定字体提前下载到站点中&#xff09;&#xff0c;无需考虑用户电脑上是否安装了此特殊字体。从此&#xff0c;把特殊字体处理成图片的方式便成为了过去。 支持程度比较好&#xff0c;甚至 IE 低版本的浏览器也能…

【手册】——mq延迟队列

目录 一、背景介绍二、思路&方案三、过程1.项目为啥用延迟队列&#xff1f;2.项目为啥用三方延迟队列&#xff1f;3.项目中为啥用rabbitmq延迟队列&#xff1f;4.rabbitmq延迟队列的安装5.rabbitmq的延迟队列配置方式5.1.exchange配置5.2.queues配置5.3.exchange和queues的…

企业招聘,应用MBTI来做人才测评招聘测评

每年的校招季都是企业争抢优秀应届毕业生人才的忙碌季。只有精准识人用人&#xff0c;才能不断为企业注入新鲜活力和青春智慧。但是随着毕业生数量越来越多&#xff0c;企业如何在招聘中精准发现自己最需要的人才&#xff0c;成为摆在人力资源部门的大难题。人才测评是各企业都…