深入理解数据结构--二叉树（基础篇）
0 / 0 / 创建于 3年前 /
oliver-l 的个人博客
最近开始学习go，公司也安排了一些对应的练习题，其中就包括二叉树相关的练习题，刚好也顺便捡起这方面的知识点
在计算机数据结构中，我们会经常接触到树这种典型的非线性数据结构，下面图片展示的就是一个标准的树结构
在数据结构中，树的定义如下。
树(tree)是n(n>=0)个节点的有限集。当n=0时，称为空树。在任意一个非空树中，有如下特点。
- 有且仅有一个特定的称为根的节点
- 当n>1时，其余节点可分为m(m>0)个互不相交的有限集，每一个集合本身又是一个树，并称为根的子树
什么是二叉树
二叉树(binary tree)是树的一种特性形式。二叉，顾名思义，这种树的每个节点最多有2个字节点。注意，这里是最多有2个，也可能只有1个，或者没有孩子节点。
二叉树还有二种特殊形式，一个叫作满二叉树，另一个叫作完全二叉树
一个二叉树的所有非叶子节点都存在左右节点，并且所有叶子节点都在同一层级上，那么这个树就是满二叉树。如下图所示
对一个有n个节点的二叉树，按层级顺序编号，则所有节点的编号为1到n。如果这个树所有节点和同样深度的满二叉树的编号为1到n的节点位置相同，则这个二叉树为完全二叉树。如下图所示
二叉树的遍历
介绍完二叉树的概念，开始进入实践，二叉树是典型的非线性数据结构，遍历时需要把非线性关联的节点转化成一个线性的序列，以不同的方式来遍历，遍历出的序列顺序也不同。
从节点之间位置关系的角度来看，二叉树的遍历分为4种。
1.前序遍历
2.中顺遍历
3.后序遍历
4.层序遍历
从更宏观的角度来看，二叉树的遍历归结为两大类
1.深度优先遍历(前序遍历，中序遍历，后序遍历)
2.广度优先遍历(层序遍历)
深度优先遍历
1.前序遍历
二叉树的前序遍历，输出顺序是根节点、左子树、右子树。如下图所示
代码实现如下
package main
import (
"fmt"
)
//定义二叉树结构体
type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}
func main(){
//0代表节点为空
num := []int{1,2,3,4,5,0,6}
//将数组切片转化为二叉树结构体
tree := createBinaryTree(0,num)
//二叉树数据
var front []int
front = frontForeach(*tree,front)
fmt.Println(front)
}
//创建二叉树
func createBinaryTree(i int,nums []int) *binaryTree {
tree := &binaryTree{nums[i], nil, nil}
//左节点的数组下标为1,3,5...2*i+1
if i<len(nums) && 2*i+1 < len(nums) {
tree.leftNode = createBinaryTree(2*i+1, nums)
}
//右节点的数组下标为2,4,6...2*i+2
if i<len(nums) && 2*i+2 < len(nums) {
tree.rightNode = createBinaryTree(2*i+2, nums)
}
return tree
}
//前序遍历
func frontForeach(tree binaryTree,num []int) []int{
//先遍历根节点
if tree.value != 0 {
num = append(num,tree.value)
}
var leftNum,rightNum []int
//若存在左节点，遍历左节点树
if tree.leftNode != nil {
leftNum = frontForeach(*tree.leftNode,leftNum)
for _,value := range leftNum{
num = append(num,value)
}
}
//若存在右节点，遍历右节点树
if tree.rightNode != nil {
rightNum = frontForeach(*tree.rightNode,rightNum)
for _,value := range rightNum{
num = append(num,value)
}
}
return num
}2.中序遍历
二叉树的中序遍历，输出顺序是左子树、根节点、右子树。如下图所示
package main
import (
"fmt"
)
//定义二叉树结构体
type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}
func main(){
//0代表节点为空
num := []int{1,2,3,4,5,0,6}
tree := createBinaryTree(0,num)
//二叉树数据
var middle []int
middle = middleForeach(*tree,middle)
fmt.Println(middle)
}
//创建二叉树
func createBinaryTree(i int,nums []int) *binaryTree {
tree := &binaryTree{nums[i], nil, nil}
//左节点的数组下标为1,3,5...2*i+1
if i<len(nums) && 2*i+1 < len(nums) {
tree.leftNode = createBinaryTree(2*i+1, nums)
}
//右节点的数组下标为2,4,6...2*i+2
if i<len(nums) && 2*i+2 < len(nums) {
tree.rightNode = createBinaryTree(2*i+2, nums)
}
return tree
}
//中序遍历
func middleForeach(tree binaryTree,num []int) []int{
var leftNum,rightNum []int
//若存在左节点，遍历左节点树
if tree.leftNode != nil {
leftNum = middleForeach(*tree.leftNode,leftNum)
for _,value := range leftNum{
num = append(num,value)
}
}
//先遍历根节点
if tree.value != 0 {
num = append(num,tree.value)
}
//若存在右节点，遍历右节点树
if tree.rightNode != nil {
rightNum = middleForeach(*tree.rightNode,rightNum)
for _,value := range rightNum{
num = append(num,value)
}
}
return num
}
3.后序遍历
二叉树的后序遍历，输出顺序是左子树、右子树、根节点。如下图所示
package main
import (
"fmt"
)
//定义二叉树结构体
type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}
func main(){
//0代表节点为空
num := []int{1,2,3,4,5,0,6}
tree := createBinaryTree(0,num)
//二叉树数据
var behind []int
behind = behindForeach(*tree,behind)
fmt.Println(behind)
}
//创建二叉树
func createBinaryTree(i int,nums []int) *binaryTree {
tree := &binaryTree{nums[i], nil, nil}
//左节点的数组下标为1,3,5...2*i+1
if i<len(nums) && 2*i+1 < len(nums) {
tree.leftNode = createBinaryTree(2*i+1, nums)
}
//右节点的数组下标为2,4,6...2*i+2
if i<len(nums) && 2*i+2 < len(nums) {
tree.rightNode = createBinaryTree(2*i+2, nums)
}
return tree
}
//后序遍历
func behindForeach(tree binaryTree,num []int) []int{
var leftNum,rightNum []int
//若存在左节点，遍历左节点树
if tree.leftNode != nil {
leftNum = behindForeach(*tree.leftNode,leftNum)
for _,value := range leftNum{
num = append(num,value)
}
}
//若存在右节点，遍历右节点树
if tree.rightNode != nil {
rightNum = behindForeach(*tree.rightNode,rightNum)
for _,value := range rightNum{
num = append(num,value)
}
}
//先遍历根节点
if tree.value != 0 {
num = append(num,tree.value)
}
return num
}
以上三种遍历方式相对比较简单，只需要的遍历过程中调整遍历顺序即可完成，下面我们看看另一种方式的遍历
广度优先遍历
层序遍历
顾名思义，就是二叉树按照从根节点到叶子节点的层次关系，一层一层横向遍历各个节点，如下所示
代码实现上，与深度优先遍历有所区别，没有使用递归的方式去实现，而是使用了队列的方式，遍历过程中，通过添加队列，读取队头的方式，完成层序遍历
package main
import (
"fmt"
)
//定义二叉树结构体
type binaryTree struct {
value int
leftNode *binaryTree
rightNode *binaryTree
}
func main(){
//0代表节点为空
num := []int{1,2,3,4,5,0,6}
tree := createBinaryTree(0,num)
//二叉树数据
var row []int
row = rowForeach(*tree,row)
fmt.Println(row)
}
//创建二叉树
func createBinaryTree(i int,nums []int) *binaryTree {
tree := &binaryTree{nums[i], nil, nil}
//左节点的数组下标为1,3,5...2*i+1
if i<len(nums) && 2*i+1 < len(nums) {
tree.leftNode = createBinaryTree(2*i+1, nums)
}
//右节点的数组下标为2,4,6...2*i+2
if i<len(nums) && 2*i+2 < len(nums) {
tree.rightNode = createBinaryTree(2*i+2, nums)
}
return tree
}
//层序遍历
func rowForeach(tree binaryTree,num []int) []int {
//定义队列
var queue []binaryTree
queue = append(queue,tree)
for len(queue) > 0{
var first binaryTree
first = queue[0]
if first.value != 0 {
//取出队头值
num = append(num,first.value)
}
//将队头删除
queue = queue[1:]
//左节点存在则加入队尾
if first.leftNode != nil {
queue = append(queue,*first.leftNode)
}
//右节点存在则加入队尾
if first.rightNode != nil {
queue = append(queue,*first.rightNode)
}
}
return num
}
二叉堆
二叉堆本质上是一种完全二叉树，它分为两个类型
1.最大堆:大顶堆任何一个父节点,都大于或等于它左、右孩子节点的值,如下图所示
2.最小堆:小顶堆的任何一个父节点,都小于或等于它左、右孩子节点的值,如下图所示
二叉堆的根节点叫作堆顶。最大堆和最小堆的特点决定了：最大堆的堆顶是整个堆中的最大元素；最小堆的堆顶事整个堆中的最小元素。
对于二叉堆，有如下几种操作
1.插入节点
2.删除节点
3.构建二叉树
在代码实现上，由于堆是一个完全二叉树，所以在存储上可以使用数组实现，假设父节点的下标为parent，那么它的左孩子下标就是2 * parent+1，右孩子下标就是2 * parent+2
构建最大堆代码如下：实现思路大致先找到最近的非叶子结点，假设有n个结点，则最近的非叶子结点为n/2，对每个结点进行判断，判断结点是否大于根节点，若不大于则节点下沉，这样一步步的循环判断，就构建了一个最大堆
package main
import "fmt"
func main(){
var numArr = []int{2,8,23,4,5,77,65,43}
buildMaxHeap(numArr,len(numArr))
fmt.Print(numArr)
}
//构建最大堆
func buildMaxHeap(arr []int,arrLen int){
for i := arrLen/2;i >= 0; i-- {
sink(arr,i,arrLen)
}
}
//树节点值下沉判断
func sink(arr []int,i,arrLen int) {
//左节点下标
left := i*2+1
//右节点下标
right := i*2+2
largest := i
//若左节点大于父节点，则交换值
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
//存在节点值大于父节点值，需要交换数据
if largest != i {
//交换值
swap(arr,i,largest)
//交换完成后，继续判断交换的节点值是否需要继续下沉
sink(arr,largest,arrLen)
}
}
//交换位置
func swap(arr []int,i,j int) {
arr[i],arr[j] = arr[j],arr[i]
}
优先队列
队列的特点是先进先出(FIFO)
入队列，将新元素置于队尾;出队列，队头元素最先被移出；
而优先队列不再遵循先入先出的原则，而是分为两种情况。
- 最大优先队列，无论入队顺序如何，都是当前最大的元素优先出列
- 最小优先队列，无论入队顺序如何，都是当前最小的元素优先出列
在上面实现了构建最大堆的代码后，还有两个基本操作，插入节点和删除节点，插入节点必须先往数组最后插入，并进行判断插入的值是否需要上浮到父节点，删除节点只允许删除根节点的值，删除后再将数组最后的值放置到根节点，再进行调整，完成节点的值下沉。当完成上述操作后，就实现了优先队列
实现代码如下：
package main
import "fmt"
func main(){
var numArr = []int{2,8,23,4,5,77,65,43}
arrLen := len(numArr)
buildMaxHeapQueue(numArr,arrLen)
var out int
numArr,out = outQueue(numArr)
fmt.Print(numArr,out)
fmt.Print("\n")
numArr = inQueue(numArr,55)
fmt.Print(numArr)
fmt.Print("\n")
numArr,out = outQueue(numArr)
fmt.Print(numArr,out)
fmt.Print("\n")
}
//入队列
func inQueue(arr []int,num int) []int {
arr = append(arr,num)
floatingNode(arr,len(arr)-1)
return arr
}
//出队列
func outQueue(arr []int) ([]int,int){
first := arr[0]
arrLen := len(arr)
if arrLen == 0 {
panic("nothing")
}
if arrLen == 1 {
var emptyArr []int
return emptyArr,first
}
//交换最后一个节点和根节点值
swapNode(arr,0,arrLen-1)
//将切片最后的值删除
arr = arr[0:arrLen-1]
//节点下沉
sinkNode(arr,0,len(arr))
return arr,first
}
//构建大顶堆
func buildMaxHeapQueue(arr []int,arrLen int){
for i := arrLen/2;i >= 0; i-- {
sinkNode(arr,i,arrLen)
}
}
//节点值上浮判断
func floatingNode(arr []int,i int){
var root int
if i%2 == 0 {
root = i/2-1
}else {
root = i/2
}
//判断父节点是否小于子节点
if arr[root] < arr[i] {
swapNode(arr,root,i)
if i > 1 {
floatingNode(arr,root)
}
}
}
//树节点值下沉判断
func sinkNode(arr []int,i int,arrLen int) {
//左节点下标
left := i*2+1
//右节点下标
right := i*2+2
largest := i
//若左节点大于父节点，则交换值
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
//存在节点值大于父节点值，需要交换数据
if largest != i {
//交换值
swapNode(arr,i,largest)
//交换完成后，继续判断交换的节点值是否需要继续下沉
sinkNode(arr,largest,arrLen)
}
}
//交换位置
func swapNode(arr []int,i,j int) {
arr[i],arr[j] = arr[j],arr[i]
}堆排序
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。
其实现思想在于先构建一个最大堆，再重新遍历，每次遍历将根节点与最后一个元素值交换，然后隔离最后一个元素，因为此时最后一个元素为最大的元素，然后根节点的值进行下沉操作，再次形成最大堆，再重复进行操作，就完成了排序。
package main
import "fmt"
func main(){
var numArr = []int{2,8,23,4,5,77,65,43}
sort := heapSort(numArr)
fmt.Print(sort)
}
//堆排序
func heapSort(arr []int) []int{
arrLen := len(arr)
//构建大顶堆
buildMaxHeap(arr,arrLen)
for i := arrLen-1; i >= 0; i-- {
swap(arr,0,i)
arrLen -= 1
sink(arr,0,arrLen)
}
return arr
}
//构建大顶堆
func buildMaxHeap(arr []int,arrLen int){
for i := arrLen/2;i >= 0; i-- {
sink(arr,i,arrLen)
}
}
//树节点值下沉判断
func sink(arr []int,i,arrLen int) {
//左节点下标
left := i*2+1
//右节点下标
right := i*2+2
largest := i
//若左节点大于父节点，则交换值
if left < arrLen && arr[left] > arr[largest] {
largest = left
}
if right < arrLen && arr[right] > arr[largest] {
largest = right
}
//存在节点值大于父节点值，需要交换数据
if largest != i {
//交换值
swap(arr,i,largest)
//交换完成后，继续判断交换的节点值是否需要继续下沉
sink(arr,largest,arrLen)
}
}
//交换位置
func swap(arr []int,i,j int) {
arr[i],arr[j] = arr[j],arr[i]
}本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号