二叉树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写一个数据结构的库，目前只支持栈、队列、堆。