
李二狗的星球
V1
2022/03/01阅读:52主题:默认主题
goalng实现二叉树
大家好,我是李二狗!一起坚持!一起学习!
每日一课,无论长短,有所学有所得
业精于勤技在专,行则将至事必成
对于一般的算法操作,无非就是写入,查找和删除三种主要的操作,此外可能还有一些获取对应的数据结构的信息等操作,比如二叉树可能需要获取树的度,栈和队列需要获取长度等;
按照这个思路,对于二叉树的操作我们需要了解这些:
-
二叉树的结构定义(上一节内容:树的基础概念) -
二叉树的创建 -
二叉树的添加数据 -
计算二叉树节点的个数 -
计算二叉树的深度 -
二叉树的遍历:四种遍历方法 -
先序遍历:先访问根节点,再访问左子树,最后访问右子树;如此递归直至结束 -
后序遍历:先访问左子树,再访问右子树,最后访问根节点;如此递归直至结束 -
中序遍历:先访问左子树,再访问根节点,最后访问右子树;如此递归直至结束 -
层次遍历:每一层从左到右访问每一个节点;
-
除了上面列举的操作以外,肯定还有很多很多其他的操作,比如获取某一层的节点数,比如计算节点的度或树的度,比如计算某节点的子节点个数,比如查找某节点的子节点或父节点等等,我们不可能一一例举所有的操作,但是我们只要深刻的理解并掌握了前面所学的链表的知识,以及二叉树的定义和结构设计,这些问题即使变化万千,我们依然能够自己探索出来;
-
二叉树的结构:
// 设计二叉树的结构体
// 利用单向链表的特点和二叉树的相似之处来设计:
// 1.树是一种递归的形式,且在每个节点之间链接和存储
// 2.二叉树仅有左右子树
type TreeNode struct {
Data int // 用于存储数据
Left *TreeNode // 左子树
Right *TreeNode // 右子树
} -
二叉树的创建
// 创建
// 思路:
// 因为利用单向链表的特性来创建二叉树(实际上这里不能叫做单向链表,因该是类单向链表;一个根节点指向两个子节点)
// 所以二叉树的节点就是类链表的节点
func CreateNode(v int) *TreeNode {
return &TreeNode{v, nil, nil}
} -
二叉树的添加数据
// 思路:
// 二叉树的创建,从唯一的一个根节点开始;
// 然后按照需要,或者左子树方向发展,或者右子树方向发展,直接链接上新的节点即可,如此反复
func InitTree() *TreeNode {
//创建一颗树
root := CreateNode(1) //根节点
root.Left = CreateNode(2) //左子树
root.Right = CreateNode(3) //右子树
root.Left.Right = CreateNode(4) //左子树的右子树
root.Right.Left = CreateNode(5) //右子树的左子树的左子树
root.Left.Left = CreateNode(6)
root.Right.Right = CreateNode(7)
return root
}结果示意图如下:
-
计算二叉树的节点的个数:如上图所示的二叉树
// 计算节点个数
// 思路:
// 因为二叉树是个递归的结构,因此可以使用递归的方式来遍历计算
func (root *TreeNode) GetTreeNodeNum() int {
if root == nil {
return 0
} else {
// 计算左节点下的节点数量,以及右节点下的节点数量,再加上根节点的数量
return root.Left.GetTreeNodeNum() + root.Right.GetTreeNodeNum() + 1
}
} -
计算二叉树的深度
// 计算树的深度:即树的最大层次
// 思路:
// 根节点是第一层;但凡有左子树或者右子树的,层次+1,一直到结束
// 上述的逻辑可以通过递归的方式来计算
func (root *TreeNode) GetTreeDegree() int {
maxDegree := 0
if root == nil {
return maxDegree
}
if root.Left.GetTreeDegree() > root.Right.GetTreeDegree() {
maxDegree = root.Left.GetTreeDegree()
} else {
maxDegree = root.Right.GetTreeDegree()
}
return maxDegree + 1
} -
四种二叉树的遍历,前三种简单,利用递归的方法即可;第四种方法较为麻烦;
// - 先序遍历:先访问根节点,再访问左子树,最后访问右子树;如此递归直至结束
// - 后序遍历:先访问左子树,再访问右子树,最后访问根节点;如此递归直至结束
// - 中序遍历:先访问左子树,再访问根节点,最后访问右子树;如此递归直至结束
// 先根再左右;
// 如上图示例,输出的结果应该是: 1 2 6 4 3 5 7
func (root *TreeNode) PreOrder() {
if root != nil {
// 先打印根节点
fmt.Print(root.Data, " ")
// 再打印左子树
root.Left.PreOrder()
// 再打印右字树
root.Right.PreOrder()
}
}
// 先左右再根
// 如上图示例,输出的结果应该是: 6 4 2 5 7 3 1
func (root *TreeNode) PostOrder() {
if root != nil {
// 先打印左子树
root.Left.PostOrder()
// 再打印右字树
root.Right.PostOrder()
// 再打印根节点
fmt.Print(root.Data, " ")
}
}
// 先左再根再右
// 如上图示例,输出的结果应该是: 6 2 4 1 5 3 7
func (root *TreeNode) MidOrder() {
if root != nil {
// 先打印左子树
root.Left.MidOrder()
// 再打印根节点
fmt.Print(root.Data, " ")
// 再打印右字树
root.Right.MidOrder()
}
}第四种层次遍历的方法,如上图所示的输出结果应该为:1 2 3 6 4 5 7
分析思路如下:
-
因为是树形结构,又想要一层层输出结果,输出左节点值后,下一个需要输出这一层的右节点值;
-
而前面的三种方法都是按照模型"一棵三节点小树"的方式输出的,因此这三种方法都无法立刻找到隔壁的右节点;
-
因此我们可以考虑创建一个队列缓存(先进先出特性),遍历数据,按照输出的顺序依次放入到队列中
二叉树层次遍历写入链表队列第一步示意图:
-

二叉树层次遍历写入链表队列第二步示意图:

业务代码如下:
// - 层次遍历:每一层从左到右访问每一个节点;
// 思路:
// 先将树的根节点放入队列,由上图分析可知,需要定义一个链表队列
// 从队列里面 remove 出节点,先打印节点值,如果该节点有左子树节点,左子树入栈,如果有右子树节点,右子树入栈;
// 重复,直到队列里面没有元素;
func (root *TreeNode) LayerOrder() {
if root == nil {
return
}
// 新建队列
queue := new(LinkQueue)
// 根节点先入队
queue.Add(root)
for queue.size > 0 {
// 不断出队列
element := queue.Remove()
// 先打印节点值
fmt.Print(element.Data, " ")
// 左子树非空,入队列
if element.Left != nil {
queue.Add(element.Left)
}
// 右子树非空,入队列
if element.Right != nil {
queue.Add(element.Right)
}
}
}
关于该链表队列的内容,这里不再赘述,可以复习一下前面学过的内容:数组和链表
此处的相关代码贴在这里:
type LinkNode struct {
Next *LinkNode
Value *TreeNode
}
// 链表队列,先进先出
type LinkQueue struct {
root *LinkNode // 链表起点
size int // 队列的元素数量
lock sync.Mutex // 为了并发安全使用的锁
}
// 入队
func (queue *LinkQueue) Add(v *TreeNode) {
queue.lock.Lock()
defer queue.lock.Unlock()
// 如果栈顶为空,那么增加节点
if queue.root == nil {
queue.root = new(LinkNode)
queue.root.Value = v
} else {
// 否则新元素插入链表的末尾
// 新节点
newNode := new(LinkNode)
newNode.Value = v
// 一直遍历到链表尾部
nowNode := queue.root
for nowNode.Next != nil {
nowNode = nowNode.Next
}
// 新节点放在链表尾部
nowNode.Next = newNode
}
// 队中元素数量+1
queue.size = queue.size + 1
}
// 出队
func (queue *LinkQueue) Remove() *TreeNode {
queue.lock.Lock()
defer queue.lock.Unlock()
// 队中元素已空
if queue.size == 0 {
panic("over limit")
}
// 顶部元素要出队
topNode := queue.root
v := topNode.Value
// 将顶部元素的后继链接链上
queue.root = topNode.Next
// 队中元素数量-1
queue.size = queue.size - 1
return v
}
关注李二狗 持续精进
坚持每日输出go开发+面试题+算法+工作经验等后端相关技术
关于我今年的计划请查看flag-2022
更多博客内容请查看bigshake
![]()
作者介绍

李二狗的星球
V1
李二狗的星球