二叉树Golang
二叉树
前言
- 完全二叉树
- 最底层节点按顺序从左到右排列。
- 满二叉树
- 一颗二叉树只有0度和2度的节点。
- 二叉搜索树
- 左子树上的所有节点的值均小于根节点的值。
- 右子树上的所有节点的值均大于根节点的值。
- 平衡二叉搜索树
- 左右两个子树的高度差的绝对值不超过1 。
二叉树的存储方式有链式存储和数组存储。(线索二叉树、红黑树等)
1、链表存储方式
type TreeNode struct {Val intLeft *TreeNodeRight *TreeNode
}func NewTreeNode(val int) *TreeNode {return &TreeNode{Val: val}
}
2、数组存储方式
// 完全二叉树: 1// / \// 2 3// / \ / \// 4 5 6 7// 以下为前中后序遍历,以下例子也是这个结果// 1245367 // 4251637// 4526731
左子树:2 * i + 1
右子树:2 * i + 2
(i是数组的下标),元素值为arr[ 2 * i + 1 ]或arr[ 2 * i + 2 ]
接下来将讲解二叉树的几种遍历方式,我全篇使用链式存储结构。
一、深度优先遍历
1、前序遍历
1、递归遍历
// 前序遍历:根 -> 左 -> 右
func preorderTraversal(root *TreeNode) {if root != nil {fmt.Println(root.Val) // 访问根节点preorderTraversal(root.Left) // 递归遍历左子树preorderTraversal(root.Right) // 递归遍历右子树}
}
2、迭代遍历
深度优先遍历的递归版本都是简洁易读的,相较于迭代版本,更直观。迭代版本使用到了一种数据结构栈,以下我使用的栈是自己封装的库函数,如果有感兴趣的朋友,可以看shard库介绍,写shard库主要还是由于Golang没提供更多的数据结构模版。
// 前序遍历:根 -> 左 -> 右(迭代实现)
func preorderTraversal(root *TreeNode) {if root == nil {return}// 栈存放的全是 *TreeNodes := shard.NewStackArray[*TreeNode]()s.Push(root)for s.Len() > 0 {// 栈顶弹出并删除node, _ := s.Pop()fmt.Println(node.Val)// 先压右子节点,再压左子节点,因为栈是后进先出(LIFO)if node.Right != nil {s.Push(node.Right)}if node.Left != nil {s.Push(node.Left)}}
}
2、中序遍历
1、递归遍历
// 中序遍历:左 -> 根 -> 右
func inorderTraversal(root *TreeNode) {if root != nil {inorderTraversal(root.Left) // 递归遍历左子树fmt.Println(root.Val) // 访问根节点inorderTraversal(root.Right) // 递归遍历右子树}
}
2、迭代遍历
// 中序遍历:左 -> 根 -> 右(迭代实现)
func inorderTraversal(root *TreeNode) {if root == nil {return}// 栈存放的全是 *TreeNodes := shard.NewStackArray[*TreeNode]()cur := rootfor cur != nil || !s.IsEmpty() {for cur != nil {s.Push(cur)cur = cur.Left}node, _ := s.Pop()fmt.Println(node.Val)cur = node.Right}
}
3、后序遍历
1、递归遍历
// 后序遍历:左 -> 右 -> 根
func postorderTraversal(root *TreeNode) {if root != nil {postorderTraversal(root.Left) // 递归遍历左子树postorderTraversal(root.Right) // 递归遍历右子树fmt.Println(root.Val) // 访问根节点}
}
2、迭代遍历
// 后序遍历:左 -> 右 -> 根(迭代实现)
func postorderTraversal(root *TreeNode) {if root == nil {return}// 栈存放的全是 *TreeNodes1 := shard.NewStackArray[*TreeNode]()s1.Push(root)s2 := shard.NewStackArray[*TreeNode]()for !s1.IsEmpty() {node, _ := s1.Pop()s2.Push(node)if node.Left != nil {s1.Push(node.Left)}if node.Right != nil {s1.Push(node.Right)}}for !s2.IsEmpty() {node, _ := s2.Pop()fmt.Println(node.Val)}
}
二、广度优先遍历
1、层序遍历
// 层序遍历
func postorderTraversal(root *TreeNode) {if root == nil {return}q := shard.NewQueueArray[*TreeNode]()q.Enqueue(root)for !q.IsEmpty() {node, _ := q.Dequeue()fmt.Print(node.Val, " ")if node.Left != nil {q.Enqueue(node.Left)}if node.Right != nil {q.Enqueue(node.Right)}}
}
三、shard库介绍
GitHub链接:https://github.com/xzhHas/shard
shard库获取:
go get -u github.com/xzhHas/shard@latest
关于使用Golang写一个数据结构的库,目前只支持栈、队列、堆。

相关文章:
二叉树Golang
二叉树 前言 完全二叉树 最底层节点按顺序从左到右排列。 满二叉树 一颗二叉树只有0度和2度的节点。 二叉搜索树 左子树上的所有节点的值均小于根节点的值。右子树上的所有节点的值均大于根节点的值。 平衡二叉搜索树 左右两个子树的高度差的绝对值不超过1 。 二叉树的存储…...
通过css的哪些方式可以实现隐藏页面上的元素?
1:opacity:0 通过将元素的透明度设置为o,实现隐藏效果,但是依然会占用空间并可以进行交互。 2:visibility:hidden 与透明度度为0的方案类似,会占据空间,但不可以进行交互。 3:Overflow:hi…...
微信小程序 === 使用腾讯地图选点
目录 插件介绍 接入指引 相关参数说明 插件错误处理 效果图 permission 插件的作用 添加插件 引入插件代码包 使用插件 页面 js 接口 插件介绍 腾讯位置服务地图选点插件 可以让用户快速、准确地选择并确认自己的当前位置,并将相关位置信息回传给开发者。…...
Redis高可用-Cluster(集群)
Redis cluster cluster 为无中心,分布式 sharding,高可用技术架构。 在哨兵 sentinel 机制中,可以解决 redis 高可用的问题,即当 master 故障后可以自动将 slave 提升为 master 从而可以保证 redis 服务的正常使用。 但是无法解…...
Spring Boot编程训练系统:数据管理与存储
摘要 随着信息技术在管理上越来越深入而广泛的应用,管理信息系统的实施在技术上已逐步成熟。本文介绍了编程训练系统的开发全过程。通过分析编程训练系统管理的不足,创建了一个计算机管理编程训练系统的方案。文章介绍了编程训练系统的系统分析部分&…...
报告解读 | 创意经济2024:如何在变革中抢占先机?
在科技飞速发展的今天,创意行业正面临前所未有的变化。《Skillshare Trendshare 2024》报告揭示了多项趋势,为创意人士提供了深刻的洞察和实用的建议。本文将为您详细解读这些趋势,助您在创意领域脱颖而出。 1. 人工智能(AI&…...
Flume1.9.0自定义Sink组件将数据发送至Mysql
需求 1、将Flume采集到的日志数据也同步保存到MySQL中一份,但是Flume目前不支持直接向MySQL中写数据,所以需要用到自定义Sink,自定义一个MysqlSink。 2、日志数据默认在Linux本地的/data/log/user.log日志文件中,使用Flume采集到…...
如何在 Ubuntu 24.04 上安装和配置 Fail2ban ?
确保你的 Ubuntu 24.04 服务器的安全是至关重要的,特别是如果它暴露在互联网上。一个常见的威胁是未经授权的访问尝试,特别是通过 SSH。Fail2ban 是一个强大的工具,可以通过自动阻止可疑活动来帮助保护您的服务器。 在本指南中,我…...
uniapp如何i18n国际化
1、正常情况下项目在代码生成的时候就已经有i18n的相关依赖,如果没有可以自行使用如下命令下载: npm install vue-i18n --save 2、创建相关文件 en文件下: zh文件下: index文件下: 3、在main.js中注册:…...
C++__day1
1、思维导图 2、如果登录失败,提示用户登录失败信息,并且提示错误几次,且重新输入;如果输入错误三次,则退出系统 #include <iostream> using namespace std;int main() {string id , pswd;string user"admi…...
Emacs进阶之插入时间信息(一百六十三)
简介: CSDN博客专家、《Android系统多媒体进阶实战》一书作者 新书发布:《Android系统多媒体进阶实战》🚀 优质专栏: Audio工程师进阶系列【原创干货持续更新中……】🚀 优质专栏: 多媒体系统工程师系列【…...
Java线程池:ThreadPoolExecutor原理解析
一、线程池的基本概念 1.1 线程池的定义 线程池是一组预先创建的线程,这些线程可以重复使用来执行多个任务,避免了频繁创建和销毁线程的开销。线程池的核心思想是通过复用一组工作线程,来处理大量的并发任务,减少系统资源消耗&a…...
二叉树、哈夫曼报文大全
1、泛型链树 #include <iostream> #include<Windows.h> #include<string> #include<stack> #include<queue> using namespace std; void menu() {cout << "**********" << endl;cout << "-1.添加" <&…...
NotePad++中安装XML Tools插件
一、概述 作为开发人员,日常开发中大部的数据是标准的json格式,但是对于一些古老的应用,例如webservice接口,由于其响应结果是xml,那么我们拿到xml格式的数据后,常常会对其进行格式化,以便阅读。…...
聊天服务器(7)数据模块
目录 Mysql数据库代码封装头文件与源文件 Mysql数据库代码封装 业务层代码不要直接写数据库,因为业务层和数据层的代码逻辑也想完全区分开。万一不想存储mysql,想存redis的话,就要改动大量业务代码。解耦合就是改起来很方便。 首先需要安装m…...
VS2022编译32位OpenCV
使用环境 Visual Studio 2022 OpenCV: 4.7.0 cmake: 3.30.2一、使用CMake工具生成vs2022的openCV工程解决方案 打开cmake,选择opencv的源代码目录,创建一个文件夹,作为VS工程文件的生成目录 点击configure构建项目,弹出构建设置…...
WP网站如何增加文章/页面的自定义模板
通过Wordpress我们后台在发布文章或者页面的时候其实可以看到有些主题 他有选择使用的页面模板,可以自定义模板,但是有些主题却没有选择主题这个功能,那这个自定义模板的功能是如何实现的呢?以下分两种情况:Page页面和…...
【Linux网络编程】简单的UDP网络程序
目录 一,socket编程的相关说明 1-1,sockaddr结构体 1-2,Socket API 二,基于Udp协议的简单通信 一,socket编程的相关说明 Socket编程是一种网络通信编程技术,它允许两个或多个程序在网络上相互通信&…...
LabVIEW中坐标排序与旋转 参见附件snippet程序
LabVIEW中坐标排序与旋转 参见附件snippet程序LabVIEW中坐标排序与旋转 参见附件snippet程序 - 北京瀚文网星科技有限公司 在LabVIEW中处理坐标排序的过程,尤其是按顺时针或逆时针排列坐标点,常见的应用包括处理几何形状、路径规划等任务。下面我将为您…...
SPIRiT-Diffusion:基于自一致性驱动的加速MRI扩散模型|文献速递-基于深度学习的病灶分割与数据超分辨率
Title 题目 SPIRiT-Diffusion: Self-Consistency Driven Diffusion Model for Accelerated MRI SPIRiT-Diffusion:基于自一致性驱动的加速MRI扩散模型 01 文献速递介绍 磁共振成像(MRI) 在临床和研究领域被广泛应用。然而,其…...
label-studio的使用教程(导入本地路径)
文章目录 1. 准备环境2. 脚本启动2.1 Windows2.2 Linux 3. 安装label-studio机器学习后端3.1 pip安装(推荐)3.2 GitHub仓库安装 4. 后端配置4.1 yolo环境4.2 引入后端模型4.3 修改脚本4.4 启动后端 5. 标注工程5.1 创建工程5.2 配置图片路径5.3 配置工程类型标签5.4 配置模型5.…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...
多场景 OkHttpClient 管理器 - Android 网络通信解决方案
下面是一个完整的 Android 实现,展示如何创建和管理多个 OkHttpClient 实例,分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...
基于uniapp+WebSocket实现聊天对话、消息监听、消息推送、聊天室等功能,多端兼容
基于 UniApp + WebSocket实现多端兼容的实时通讯系统,涵盖WebSocket连接建立、消息收发机制、多端兼容性配置、消息实时监听等功能,适配微信小程序、H5、Android、iOS等终端 目录 技术选型分析WebSocket协议优势UniApp跨平台特性WebSocket 基础实现连接管理消息收发连接…...
Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)
概述 在 Swift 开发语言中,各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过,在涉及到多个子类派生于基类进行多态模拟的场景下,…...
vue3 字体颜色设置的多种方式
在Vue 3中设置字体颜色可以通过多种方式实现,这取决于你是想在组件内部直接设置,还是在CSS/SCSS/LESS等样式文件中定义。以下是几种常见的方法: 1. 内联样式 你可以直接在模板中使用style绑定来设置字体颜色。 <template><div :s…...
鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/
使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题:docker pull 失败 网络不同,需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
C#中的CLR属性、依赖属性与附加属性
CLR属性的主要特征 封装性: 隐藏字段的实现细节 提供对字段的受控访问 访问控制: 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性: 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑: 可以…...
LLMs 系列实操科普(1)
写在前面: 本期内容我们继续 Andrej Karpathy 的《How I use LLMs》讲座内容,原视频时长 ~130 分钟,以实操演示主流的一些 LLMs 的使用,由于涉及到实操,实际上并不适合以文字整理,但还是决定尽量整理一份笔…...
