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, nil, nil}
   }
   

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