李二狗的星球

V1

2022/03/01阅读:52主题:默认主题

goalng实现二叉树

大家好,我是李二狗!一起坚持!一起学习!
每日一课,无论长短,有所学有所得
业精于勤技在专,行则将至事必成

对于一般的算法操作,无非就是写入,查找和删除三种主要的操作,此外可能还有一些获取对应的数据结构的信息等操作,比如二叉树可能需要获取树的度,栈和队列需要获取长度等;

按照这个思路,对于二叉树的操作我们需要了解这些:

  1. 二叉树的结构定义(上一节内容:树的基础概念
  2. 二叉树的创建
  3. 二叉树的添加数据
  4. 计算二叉树节点的个数
  5. 计算二叉树的深度
  6. 二叉树的遍历:四种遍历方法
    • 先序遍历:先访问根节点,再访问左子树,最后访问右子树;如此递归直至结束
    • 后序遍历:先访问左子树,再访问右子树,最后访问根节点;如此递归直至结束
    • 中序遍历:先访问左子树,再访问根节点,最后访问右子树;如此递归直至结束
    • 层次遍历:每一层从左到右访问每一个节点;

除了上面列举的操作以外,肯定还有很多很多其他的操作,比如获取某一层的节点数,比如计算节点的度或树的度,比如计算某节点的子节点个数,比如查找某节点的子节点或父节点等等,我们不可能一一例举所有的操作,但是我们只要深刻的理解并掌握了前面所学的链表的知识,以及二叉树的定义和结构设计,这些问题即使变化万千,我们依然能够自己探索出来;

  1. 二叉树的结构:

    // 设计二叉树的结构体
    // 利用单向链表的特点和二叉树的相似之处来设计:
    // 1.树是一种递归的形式,且在每个节点之间链接和存储
    // 2.二叉树仅有左右子树
    type TreeNode struct {
     Data  int       // 用于存储数据
     Left  *TreeNode // 左子树
     Right *TreeNode // 右子树
    }
  2. 二叉树的创建

    // 创建
    // 思路:
    // 因为利用单向链表的特性来创建二叉树(实际上这里不能叫做单向链表,因该是类单向链表;一个根节点指向两个子节点)
    // 所以二叉树的节点就是类链表的节点
    func CreateNode(v int) *TreeNode {
     return &TreeNode{v, nilnil}
    }
  3. 二叉树的添加数据

    // 思路:
    // 二叉树的创建,从唯一的一个根节点开始;
    // 然后按照需要,或者左子树方向发展,或者右子树方向发展,直接链接上新的节点即可,如此反复
    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
    }

    结果示意图如下:

  4. 计算二叉树的节点的个数:如上图所示的二叉树

    // 计算节点个数
    // 思路:
    // 因为二叉树是个递归的结构,因此可以使用递归的方式来遍历计算
    func (root *TreeNode) GetTreeNodeNum() int {
     if root == nil {
      return 0
     } else {
      // 计算左节点下的节点数量,以及右节点下的节点数量,再加上根节点的数量
      return root.Left.GetTreeNodeNum() + root.Right.GetTreeNodeNum() + 1
     }
    }
  5. 计算二叉树的深度

    // 计算树的深度:即树的最大层次
    // 思路:
    // 根节点是第一层;但凡有左子树或者右子树的,层次+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
    }
  6. 四种二叉树的遍历,前三种简单,利用递归的方法即可;第四种方法较为麻烦;

    // - 先序遍历:先访问根节点,再访问左子树,最后访问右子树;如此递归直至结束
    // - 后序遍历:先访问左子树,再访问右子树,最后访问根节点;如此递归直至结束
    // - 中序遍历:先访问左子树,再访问根节点,最后访问右子树;如此递归直至结束

    // 先根再左右;
    // 如上图示例,输出的结果应该是: 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

李二狗的星球