程序员经验分享-hwhale

Go语言数据结构-二叉树

2023-10-27

定义

二叉树是一种数据结构，它是由 n(n≥1) 个有限节点组成一个具有层次关系的集合。
根节点：最上面的节点；叶子节点：左右子节点都为nil的节点。
在这里插入图片描述

特点

  • 每个节点有零个或两个子节点；
  • 没有父节点的节点称为根节点；
  • 每一个非根节点有且只有一个父节点；
  • 除了根节点外，每个子节点可以分为多个不相交的子树

基本结构

type Node struct {
	Value int
	Left  *Node
	Right *Node
}

遍历

前序遍历

对每颗子树，均遵循根节点–>左节点–>右节点

递归前序
func preShowTree(head *Node) {
	if head == nil {
		return
	}
	fmt.Println(head.V)//第一次来到节点的时候打印
	showTree(head.Left)
	showTree(head.Right)
}
非递归前序(深度优先遍历)

思路：

  1. 声明一个栈
  2. 从栈中弹出一个节点cur
  3. 打印（处理）cur
  4. 先右后左（如果有），把该节点的子节点压入栈中
  5. 循环执行1->2->3

代码实现：

package main

import (
	"errors"
	"fmt"
)

type Node struct {
	Value int
	Left  *Node
	Right *Node
}

type Stack struct {
	MaxTop int      //栈最大可以存放的数的个数
	Top    int      //表示栈顶的索引id，初始值为-1，最大值为MaxTop-1
	Arr    [7]*Node //数组模拟栈
}

func (s *Stack) Push(pushNode *Node) error {
	if s.Top == s.MaxTop-1 {
		return errors.New("栈满了")
	}

	s.Top++
	s.Arr[s.Top] = pushNode

	return nil
}

func (s *Stack) Pop() (popNode *Node, err error) {
	if s.Top == -1 {
		return nil, errors.New("空栈")
	}
	popNode = s.Arr[s.Top]
	s.Arr[s.Top] = nil
	s.Top--
	return popNode, nil
}

func (s *Stack) List() {
	if s.Top == -1 {
		fmt.Println("空栈")
	}
	for i := 0; i < s.Top+1; i++ {
		fmt.Printf("Arr[%v]=%v\n", i, s.Arr[i])
	}
}

func main() {
	root := &Node{Value: 1}
	left := &Node{Value: 3}
	right := &Node{Value: 4}
	root.Left = left
	root.Right = right
	left1 := &Node{Value: 5}
	right1 := &Node{Value: 6}
	left2 := &Node{Value: 7}
	right2 := &Node{Value: 8}
	left.Left = left1
	left.Right = right1
	right.Left = left2
	right.Right = right2
	showTree(root)
}

func preShowTree(head *Node) {
	if head != nil {
		nodeStack := &Stack{MaxTop: 7, Top: -1}
		nodeStack.Push(head)
		for nodeStack.Top < nodeStack.MaxTop-1 && nodeStack.Top > -1 {
			tmpNode, _ := nodeStack.Pop()
			if tmpNode != nil {
				fmt.Println(tmpNode.Value)
			}
			if tmpNode.Right != nil {
				nodeStack.Push(tmpNode.Right)
			}
			if tmpNode.Left != nil {
				nodeStack.Push(tmpNode.Left)
			}
		}
	}

}

中序遍历

中序:对每颗子树，均遵循左节点–>根节点–>右节点

递归中序
func midShowTree(head *Node) {
	if head == nil {
		return
	}
	showTree(head.Left)
    fmt.Println(head.V)//第二次来到节点的时候打印
	showTree(head.Right)
}
非递归中序

思路：

  1. 申请1个栈
  2. 把每颗子树的整树所有左节点入栈
  3. 依次弹出的过程中，打印该节点，且对该节点的右节点，循环1，2,
  4. 循环执行1->2->3
  5. 打印收集栈中数据

代码实现：

func midShowTree(head *Node) {
	if head != nil {
		nodeStack := &Stack{MaxTop: 7, Top: -1}
		for !nodeStack.IsEmpty() || head != nil {
			if head != nil { //所有左节点压入栈
				nodeStack.Push(head)
				head = head.Left
			} else { //弹出栈的数据，打印节点，且对右子节点循环if的操作
				popNode, _ := nodeStack.Pop()
				fmt.Println(popNode.Value)
				head = popNode.Right
			}
		}
	}
}

后序遍历

后序:对每颗子树，均遵循左节点–>右节点–>根节点

递归后序
func afterShowTree(head *Node) {
	if head == nil {
		return
	}
	showTree(head.Left)
	showTree(head.Right)
    fmt.Println(head.V)//第三次来到节点的时候打印
}
非递归后序

思路：

  1. 申请两个栈（普通栈和收集栈）
  2. 从普通栈中弹出一个节点cur
  3. 把该节点压入收集栈中
  4. 先左后右（如果有），把该节点的子节点压入普通栈中
  5. 循环执行1->2->3
  6. 打印收集栈中数据

代码实现：

func afterShowTree(head *Node) {
	if head != nil {
		nodeStack := &Stack{MaxTop: 7, Top: -1}
		showStack := &Stack{MaxTop: 7, Top: -1}
		nodeStack.Push(head)
		for !nodeStack.IsEmpty() {
			popNode, _ := nodeStack.Pop()
			showStack.Push(popNode) //当前节点压入收集栈
			//左子节点压入普通栈
			if popNode.Left != nil {
				nodeStack.Push(popNode.Left)
			}
			//右子节点压入栈
			if popNode.Right != nil {
				nodeStack.Push(popNode.Right)
			}
		}
		//便利收集栈数据
		showStack.List()
	}
}

宽度优先遍历

思路：

  1. 申请一个队列
  2. 把头结点加入队列
  3. 从队列中弹出一个节点cur，并打印
  4. 先左后右（如果有），把该节点的子节点加入队列
  5. 循环执行2->3

代码实现：

type Queue struct {
	buff    []*Node //队列的的数据存储在数组上
	maxsize int     //队列最大容量
	front   int     //队列头索引，不包括自己（队列头索引值-1）
	rear    int     //队列尾索引
}

//
// Push
// @Description: 压入队列
// @Author: maxwell.ke
// @time 2022-10-25 22:58:58
// @receiver q
// @param n
// @return error
//
func (q *Queue) Push(pushNode *Node) error {
	if q.rear == q.maxsize-1 {
		if q.front == -1 { //头尾都到头了
			return fmt.Errorf("队列已满，PUSH失败")
		} else { 尾都到头了，头有空，则重置front
			q.front = -1
			q.rear = len(q.buff) - 1
		}
	}
	q.rear++
	q.buff = append(q.buff, pushNode)
	return nil
}

//
// Pop
// @Description: 出队列
// @Author: maxwell.ke
// @time 2022-10-25 23:14:20
// @receiver q
// @return n
// @return err
//
func (q *Queue) Pop() (popNode *Node, err error) {
	if len(q.buff) == 0 {
		return nil, fmt.Errorf("空队列,POP失败")
	}
	popNode = q.buff[0]
	q.buff = q.buff[1:]
	q.front++
	return popNode, nil
}

//
// List
// @Description: 队列遍历
// @Author: maxwell.ke
// @time 2022-10-25 23:13:10
// @receiver q
// @return error
//
func (q *Queue) List() error {
	if len(q.buff) == 0 {
		return fmt.Errorf("空队列")
	}
	for i := 0; i < q.maxsize; i++ {
		if i > q.front && i <= q.rear {
			fmt.Println(q.buff[i-q.front-1].Value)
		} else {
			fmt.Println("nil")
		}
	}
	fmt.Println()
	return nil
}

func wideShowTree(head *Node) {
	nodeQueue := &Queue{buff: make([]*Node, 0, 7), maxsize: 7, front: -1, rear: -1}
	nodeQueue.Push(head)
	for len(nodeQueue.buff) < nodeQueue.maxsize && len(nodeQueue.buff) > 0 {
		cur, _ := nodeQueue.Pop()
		fmt.Println(cur.Value)
		if cur.Left != nil {
			nodeQueue.Push(cur.Left)
		}
		if cur.Right != nil {
			nodeQueue.Push(cur.Right)
		}
	}
}

特殊二叉树

搜索二叉树

定义

每一个子树，左节点比根节点小，右节点比根节点大的二叉树，二叉树的节点无重复值。

判断方法

中序（递归中序或者非递归中序均可）遍历二叉树，如果是升序的即为搜索二叉树。

代码实现（递归中序的方法）：

func isBST(head *Node) bool {
	if head == nil {
		return true
	}
	leftBST := isBST(head.Left)
	if !leftBST {
		return false
	}
	//打印事件改为了比较事件
	if head.Value <= preValue {
		return false
	} else {
		preValue = head.Value
	}

	rightBST := isBST(head.Right)
	return rightBST
}

满二叉树

定义

如果二叉树中除了叶子结点，每个结点的度都为2，则此二叉树称为满二叉树。

性质
  1. 满二叉树中第 i 层的节点数为 2^i - 1 个。
  2. 深度为k的满二叉树必有 2k-1 个节点 ，叶子数为 2k-1。
  3. 满二叉树中不存在度为 1 的节点，每一个分支点中都两棵深度相同的子树，且叶子节点都在最底层。
  4. 具有 n 个节点的满二叉树的深度为 log2(n+1)。
判断方法

方法一：根据性质1来判断：

  1. 先求出树的层数i，再统计节点数k
  2. 如果k = 2^i -1，则为满二叉树

方法二：判断左子树为满二叉树且右子树为满二叉树

代码实现：

func isFBT(head *Node) bool {
	if head == nil {
		return true
	}
	leftFBT := isFBT(head.Left)
	if !leftFBT {
		return false
	}
	if (head.Left != nil && head.Right == nil) || (head.Left == nil && head.Right != nil) {
		return false
	}
	rightFBT := isFBT(head.Right)
	return rightFBT
}

完全二叉树

定义

如果二叉树中除去最后一层节点为满二叉树，且最后一层的结点依次从左到右分布，则此二叉树被称为完全二叉树。

判断方法
  1. 按照宽度优先遍历
  2. 任意一个节点有右子节点无左子节点，则为非完全二叉树
  3. 在条件1不违规的情况下，如果遇到左右子节点不齐全的情况下，后续节点皆为叶子节点，如果后续存在非叶子节点，则为非完全二叉树。

代码实现：

func isCBT(head *Node) bool {
	if head == nil {
		return true
	}
	var (
		leaf = false //是否遇到左右子节点不齐全的情况
		l    *Node
		r    *Node
	)
	nodeQueue := &Queue{buff: make([]*Node, 0, 8), maxsize: 8, front: -1, rear: -1}
	nodeQueue.Push(head)
	for len(nodeQueue.buff) < nodeQueue.maxsize && len(nodeQueue.buff) > 0 {
		popNode, _ := nodeQueue.Pop()
		l = popNode.Left
		r = popNode.Right

		//如果遇到了不双全的节点后，又发现当前节点有子节点 或者 有右节点但无左节点
		if (leaf && (l != nil || r != nil)) || (l == nil && r != nil) {
			return false
		}

		if l != nil {
			nodeQueue.Push(l)
		}
		if r != nil {
			nodeQueue.Push(r)
		}
		if l == nil || r == nil { //左右节点不双全，则后续为叶子节点
			leaf = true
		}
	}
	return true
}

平衡二叉树

定义

对于任何一个子树来说，左树高度和右树高度差不超过1

判断方法

A && B && C
A: 左子树为平衡二叉树
B: 右子树为平衡二叉树
C: abs(左高-右高) <= 1
代码实现：

func isALV(head *Node) bool {
	return process(head).IsBalanced
}

type ReturnType struct {
	IsBalanced bool
	Height     int
}

func process(x *Node) *ReturnType {
	if x == nil {
		return &ReturnType{IsBalanced: true, Height: 0}
	}
	leftData := process(x.Left)
	rightData := process(x.Right)
	height := max(leftData.Height, rightData.Height) + 1 //当前节点的高度
	isBalanced := leftData.IsBalanced && rightData.IsBalanced && math.Abs(float64(leftData.Height-rightData.Height)) <= 1
	return &ReturnType{IsBalanced: isBalanced, Height: height}
}

func max(a, b int) int {
	maxNum := a
	if a < b {
		maxNum = b
	}
	return maxNum
}
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)

Golang

数据结构和算法

数据结构

二叉树

Go语言数据结构-二叉树 的相关文章

  • 华为OD机试真题- 最小的调整次数【2023Q1】【JAVA、Python、C++】

    题目描述 有一个特异性的双端队列 该队列可以从头部或尾部添加数据 但是只能从头部移出数据 小A依次执行2n个指令往队列中添加数据和移出数据 其中n个指令是添加数据 可能从头部添加 也可能从尾部添加 依次添加1到n n个指令是移出数据 现在要

  • OpenWrt配置（UCI）

    UCI简介 统一配置接口 Unified Configuration Interface UCI 其目的在于集中OpenWrt系统的配置 基本语法介绍 参考 UCI系统 https wiki openwrt org zh cn doc uc

随机推荐

  • MES系统开发手记(一)

    前言 从ERP开发转到MES系统开发又是将近5年时间了 前后做了几个项目的MES系统 终于想为自己的这几年开发做个总结 写一个比较产品化的MES系统 一 建模 1 基础资料 建立以下几个信息中心 车间资源 产品数据 工艺数据 对制造过程中所

  • gcc编译出现 invalid operands to binary -的解决方法

    在做pcap库抓包的程序中 使用了 pcap head gt caplen unsigned int unsigned char data packet 算式 然后就报 invalid operands to binary 检查代码 其中p

  • 一种为不联网(离线)电脑配置深度学习环境的方法

    1 场景描述 目标电脑为A 无法联网 但是硬件好 需要配置深度学习环境 家用电脑为B 可以联网 硬件条件仅满足日常办公 下面以Tensorflow为例 提供一种环境配置的思路 tensorflow也可以是pytorch等深度学习框架 2 思

  • 程序跑飞原因

    程序跑死原因查找 1 意外中断 是否打开了某个中断 但是没有响应和清除中端标志 导致程序一直进入中断 造成死机假象 2 中断变量处理不妥 若定义某些会在中断中修改的全局变量 这时要注意两个问题 首先为了防止编译器优化中断变量 要在这些变量定

  • docker部署zookeeper集群

    编写启动脚本 docker stop zookeeper docker rm zookeeper docker run restart always privileged true p 2181 2181 name zookeeper ne

  • reset --hard 后如何找回

    问 reset hard 后如何找回 答 拢共分两步 一 找到你想要切回的commit id 二 切过去 一 找到你想要切回的commit id 你的git操作在log中都会有记录 git logs refs heads master 如

  • 惠普ns1005w使用说明_惠普 NS1005w 多功能一体机深度评测：15秒智能闪充 + 全功能手机操控...

    在办公场景中 对打印机的要求比较多 如打印快 成本低 印量大 多功能等 而在桌面型多功能一体机中 HP Laser NS MFP 1005系列 智能闪充加粉式多功能一体机更能满足用户的要求 自从HP Laser NS MFP 1005系列智

  • 华为OD机试 -勾股数(Java)

    题目描述 如果三个正整数A B C A B C 则为勾股数 如果ABC之间两两互质 即A与B A与C B与C均互质没有公约数 则称其为勾股数元组 请求出给定 n m 范围内所有的勾股数元组 输入描述 起始范围 1 lt n lt 10000

  • 【已解决】ImportError: torch.utils.ffi is deprecated. Please use cpp extensions instead.

    本文记录了博主遇到问题 ImportError torch utils ffi is deprecated Please use cpp extensions instead 的解决方案 更新于2019 05 30 背景 博主需要安装一个程

  • ESP32: IDF_PYTHON_ENV_PATH: (not set)

    在Linux下编译esp32工程报错 law law hello world idf py build Setting IDF PATH environment variable home law esp32 esp idf The fol

  • libxxx_intermediates/export_includes’, needed by 解决办法

    xxx intermediates export includes needed by 解决办法 报错信息 ninja error out target product ac8257 demo obj SHARED LIBRARIES li

  • 【深度学习】【U-net】医学图像(血管)分割实验记录

    医学图像分割实验记录 U net介绍 数据集 实验记录 实验1 实验2 fail 实验3 fail 实验4 fail 实验5 fail 实验6 fail 本项目仅用于大创实验 使用pytorch编程 参考价值有限 U net介绍 这里先行挖

  • flutter 本项目做IM消息提醒的思路

    message util 监听接收到消息 container page 在最外层监听消息 如果有收到就弹出弹窗IMNoticeDialog 用converScreen封装过的 可以穿透 可以点击 conversationItem 进入 co

  • 基于MATLAB的战术手势识别功能的设计与实现

    一 课题介绍 手势识别技术是人们生活中常见的一类图像处理技术 也是目前比较火热的研究领域之一 手势识别可以用于人们生活中各种场景 比如利用手势进行电视信息交互 只需要通过手势就能实现对电视机的控制 在很多的VR游戏中 利用手势可以完成各种各

  • mptt介绍

    1 MQTT协议是由IBM开发的即时通讯协议 相比来说比较适合物联网场景的通讯协议 MQTT协议采用发布 订阅模式 所有的物联网终端都通过TCP连接到云端 云端通过主题的方式管理各个设备关注的通讯内容 负责将设备与设备之间消息的转发 2 m

  • 关于Java中对象的比较

    Java对象的比较有这三种 第一种equals 方法是对象值的比较 这是Object类提供的方法 第二种 第三种分别是实现Comparable Comparator接口 Object equals Comparable Comparator

  • 【C++】error LNK2019: 无法解析的外部符号

    转 C error LNK2019 无法解析的外部符号 错误解决方案 今天在实现类模板特例化的时候遇到一个问题 就是把类模板函数实现放到类的cpp文件中 然后在main函数中使用这个类的时候 就会出现无法解析的外部符号 函数名 xxxx 等

  • 深圳求职安全防范手册

    深圳作为中国第四大经济城市 吸引了来自全国各地的大批求职者 因为人口流动性较大 人员组成复杂 治安方面难免会出现一些问题 所以特整理这份求职安全防范手册 希望可以对准备到深圳求职或者已经在深圳求职的你提一个醒 防患于未然 毕竟出门在外 安全

  • 实现一个函数，可以左旋字符串中的k个字符。

    实现一个函数 可以左旋字符串中的k个字符 例如 ABCD左旋一个字符得到BCDA ABCD左旋两个字符得到CDAB 方法一 一 我们先假定这串字符为ABCDE 假设左旋1次 我们可以进行如下操作 ABCDE 一开始 BBCDE 第一次 第一

  • Go语言数据结构-二叉树

    定义 二叉树是一种数据结构 它是由 n n 1 个有限节点组成一个具有层次关系的集合 根节点 最上面的节点 叶子节点 左右子节点都为nil的节点 特点 每个节点有零个或两个子节点 没有父节点的节点称为根节点 每一个非根节点有且只有一个父节点

热门标签