二叉树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) 在临床和研究领域被广泛应用。然而,其…...
SciencePlots——绘制论文中的图片
文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了:一行…...
QMC5883L的驱动
简介 本篇文章的代码已经上传到了github上面,开源代码 作为一个电子罗盘模块,我们可以通过I2C从中获取偏航角yaw,相对于六轴陀螺仪的yaw,qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...
ssc377d修改flash分区大小
1、flash的分区默认分配16M、 / # df -h Filesystem Size Used Available Use% Mounted on /dev/root 1.9M 1.9M 0 100% / /dev/mtdblock4 3.0M...
抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
Golang dig框架与GraphQL的完美结合
将 Go 的 Dig 依赖注入框架与 GraphQL 结合使用,可以显著提升应用程序的可维护性、可测试性以及灵活性。 Dig 是一个强大的依赖注入容器,能够帮助开发者更好地管理复杂的依赖关系,而 GraphQL 则是一种用于 API 的查询语言,能够提…...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
MySQL中【正则表达式】用法
MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现(两者等价),用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例: 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
代码随想录刷题day30
1、零钱兑换II 给你一个整数数组 coins 表示不同面额的硬币,另给一个整数 amount 表示总金额。 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额,返回 0 。 假设每一种面额的硬币有无限个。 题目数据保证结果符合 32 位带…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
