golang数据结构与算法——递归、迷宫回溯和二叉树的遍历

一递归

1.1 递归的概念

简单的说: 递归就是函数/方法自己调用自己,每次调用时传入不同的变量.第归有助于编程者解决复杂的问题,同时可以让代码变得简洁。

使用递归函数最重要的三点：

递归就是自己调用自己。
必须先定义函数的退出条件，没有退出条件，递归将成为死循环。
go语言递归函数很可能会产生一大堆的goroutine，也很可能会出现栈空间内存溢出问题。

1.2 快速入门

package main

import "fmt"

func test(n int) {
	if n > 2 {
		n--
		test(n)
	} else {
		fmt.Println("n=", n)
	}
}

func main() {
	n := 4
	test(n)
}

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
n= 2

[Done] exited with code=0 in 3.936 seconds

示意图：

1.3 应用场景

各种数学问题如: 8 皇后问题 , 汉诺塔, 阶乘问题, 迷宫问题, 球和篮子的问题(google 编程大
赛)
将用栈解决的问题–>第归代码比较简洁

1.4 递归需要遵守的重要原则

执行一个函数时，就创建一个新的受保护的独立空间(新函数栈)
函数的局部变量是独立的，不会相互影响, 如果希望各个函数栈使用同一个数据，使用引用传递
递归必须向退出递归的条件逼近【程序员自己必须分析】，否则就是无限递归，死循环了
当一个函数执行完毕，或者遇到 return，就会返回，遵守谁调用，就将结果返回给谁，同时当函数执行完毕或者返回时，该函数本身也会被系统销毁

二迷宫回溯问题

问题描述：

有一个迷宫地图，其中地图中有一些不过达的位置（墙壁、障碍）。从一个起点开始，一步一步走到终点，如何找到一条到达的道路呢？

思路分析：

利用二位数组来模拟迷宫地图，0表示没有走过的点，1表示墙壁，2表示走通的点，3表示走不通的点，按照自定义的寻路策略，遍历寻找路径，如果是死路则标示该路径走不通，回到起点，再重新找一条新路，以此类推，直到走通为止。这种方法又称作为回溯法（递归）。

代码实现：

package main

import "fmt"

// SetWay 寻找出路 i,j表示地图的坐标起点
func SetWay(myMap *[8][8]int, i, j int) bool {

	// 设置终点
	if myMap[6][6] == 2 {
		return true
	}

	if myMap[i][j] == 0 {
		// 假设可以走通
		myMap[i][j] = 2
		// 寻路策略：下右上左
		if SetWay(myMap, i+1, j) { // 下
			return true
		} else if SetWay(myMap, i, j+1) { // 右
			return true
		} else if SetWay(myMap, i-1, j) { // 上
			return true
		} else if SetWay(myMap, i, j-1) { // 左
			return true
		} else { // 死路
			myMap[i][j] = 3
			return false
		}
	}

	return false
}

// ShowMap 输出地图
func ShowMap(myMap [8][8]int) {
	for i := 0; i < 8; i++ {
		for j := 0; j < 8; j++ {
			fmt.Print(myMap[i][j], " ")
		}
		fmt.Println()
	}
}

func main() {
	/**
	0=没有走过的点
	1=墙壁
	2=走通的点
	3=走不通的点
	*/
	var myMap [8][8]int

	// 设置地图最上和最下为1（墙）
	for i := 0; i < 8; i++ {
		myMap[0][i] = 1
		myMap[7][i] = 1
	}

	// 设置地图最左和最右为1（墙）
	for i := 0; i < 8; i++ {
		myMap[i][0] = 1
		myMap[i][7] = 1
	}

	// 设置地图中的障碍（墙）
	myMap[3][1] = 1
	myMap[3][2] = 1
	myMap[3][3] = 1

	fmt.Println("地图为:")
	ShowMap(myMap)

	// 测试
	SetWay(&myMap, 1, 1)
	fmt.Println("路径为:")
	ShowMap(myMap)

}

运行结果：

[Running] go run "e:\golang开发学习\go_pro\test.go"
地图为:
1 1 1 1 1 1 1 1 
1 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 1 
1 1 1 1 0 0 0 1 
1 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 1 
1 0 0 0 0 0 0 1 
1 1 1 1 1 1 1 1 
路径为:
1 1 1 1 1 1 1 1 
1 2 0 0 0 0 0 1 
1 2 2 2 2 0 0 1 
1 1 1 1 2 0 0 1 
1 0 0 0 2 0 0 1 
1 0 0 0 2 0 0 1 
1 0 0 0 2 2 2 1 
1 1 1 1 1 1 1 1 

[Done] exited with code=0 in 1.273 seconds

三二叉树的4种遍历方式

3.1 二叉树介绍

满足以下两个条件的树就是二叉树：

本身是有序树
树中包含的各个节点的度不能超过 2，即只能是 0、1 或者 2

3.2 二叉树的遍历方式

前序遍历：先访问根节点，再前序遍历左子树，再前序遍历右子树

中序遍历：先中序遍历左子树，再访问根节点，再中序遍历右子树

后序遍历：先后序遍历左子树，再后序遍历右子树，再访问根节点

层序遍历：按照节点深度，由树根部（深度为0），一层一层向下遍历子节点

以根访问顺序决定是什么遍历
左子树都是优先右子树

3.3 二叉树模型

我们以上面的这个二叉树图为基础数据编写代码

3.3.1 基础结构

二叉树需要存储自身节点数据，以及最多两个子节点的索引

type BinaryTree struct {
	Value     int         `json:"value,omitempty"`
	LeftNode  *BinaryTree `json:"left_node,omitempty"`
	RightNode *BinaryTree `json:"right_node,omitempty"`
}

3.3.2 二叉树模型代码

结合上面的节点结构体代码，我们把模拟数据用代码表示出来

//根节点
var rootNode *BinaryTree = &BinaryTree{
	Value: 1,
	LeftNode: &BinaryTree{
		Value: 2,
		LeftNode: &BinaryTree{
			Value: 4,
			RightNode: &BinaryTree{
				Value:     6,
				LeftNode:  &BinaryTree{Value: 7},
				RightNode: &BinaryTree{Value: 8},
			},
		},
	},
	RightNode: &BinaryTree{
		Value:     3,
		RightNode: &BinaryTree{Value: 5},
	},
}

3.4 前序递归遍历

先输出自己的值，再遍历输出左子树的值，再遍历输出右子树的值。

// 先序遍历
func RecursionPreorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}
	// 先输出自身节点的值
	fmt.Printf("%v ", node.Value)
	// 递归遍历左子树
	RecursionPreorderTraversal(node.LeftNode)
	// 递归遍历右子树
	RecursionPreorderTraversal(node.RightNode)
}
 
func main(){
    RecursionPreorderTraversal(rootNode)
}

运行结果：

1 2 4 6 7 8 3 5

3.5 中序递归遍历

先遍历输出左子树，再输出自身的值，再遍历输出右子树的值

// 中序遍历
func RecursionMiddleorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}
 
	// 先递归遍历左子树
	RecursionMiddleorderTraversal(node.LeftNode)
	// 再输出自身节点的值
	fmt.Printf("%v ", node.Value)
	// 最后递归遍历右子树
	RecursionMiddleorderTraversal(node.RightNode)
}
 
func main(){
    RecursionMiddleorderTraversal(rootNode)
}

运行结果：

4 7 6 8 2 1 3 5

3.6 后序递归遍历

先遍历输出左子树的值，再遍历输出右子树，最后输出自身节点的值

// 后序遍历
func RecursionPostorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}
 
	// 先递归遍历左子树
	RecursionPostorderTraversal(node.LeftNode)
	// 再递归遍历右子树
	RecursionPostorderTraversal(node.RightNode)
	// 最后输出自身节点的值
	fmt.Printf("%v ", node.Value)
}
 
func main(){
    RecursionPostorderTraversal(rootNode)
}

运行结果：

7 8 6 4 2 5 3 1

3.7 层序递归遍历

按照节点深度，由树根部（深度为0），一层一层向下遍历子节点

// 从root节点开始层级遍历
func LevelTraversal(rootNode *BinaryTree) {
	//如果当前节点为nil，直接结束遍历
	if rootNode == nil {
		return
	}
 
	// 封装成slice
	var nodeSlice []*BinaryTree
	nodeSlice = append(nodeSlice, rootNode)
 
	// 开始递归遍历
	RecursionTraversal(nodeSlice)
}
 
// 递归遍历核心
func RecursionTraversal(nodeSlice []*BinaryTree) {
	// 如果当前层级slice为空，则结束遍历
	if len(nodeSlice) == 0 {
		return
	}
 
	// 创建新的节点slice，存储下一层需要遍历的node
	var nextSlice []*BinaryTree
 
	//遍历当前nodeSlice
	for i := 0; i < len(nodeSlice); i++ {
		//取出要遍历的node
		node := nodeSlice[i]
 
		//输出当前node的值
		fmt.Printf("%v ", node.Value)
 
		//当前node左子节点append到下一层node slice中
		if node.LeftNode != nil {
			nextSlice = append(nextSlice, node.LeftNode)
		}
 
		//当前node右子节点append到下一层node slice中
		if node.RightNode != nil {
			nextSlice = append(nextSlice, node.RightNode)
		}
	}
 
	//递归遍历下一层的node slice
	RecursionTraversal(nextSlice)
}
 
func main(){
    LevelTraversal(rootNode)
}

运行结果：

1 2 3 4 5 6 7 8

3.8 完整代码

package main

import "fmt"

type BinaryTree struct {
	Value     int         `json:"value,omitempty"`
	LeftNode  *BinaryTree `json:"left_node,omitempty"`
	RightNode *BinaryTree `json:"right_node,omitempty"`
}

//根节点
var rootNode *BinaryTree = &BinaryTree{
	Value: 1,
	LeftNode: &BinaryTree{
		Value: 2,
		LeftNode: &BinaryTree{
			Value: 4,
			RightNode: &BinaryTree{
				Value:     6,
				LeftNode:  &BinaryTree{Value: 7},
				RightNode: &BinaryTree{Value: 8},
			},
		},
	},
	RightNode: &BinaryTree{
		Value:     3,
		RightNode: &BinaryTree{Value: 5},
	},
}

// 先序遍历
func RecursionPreorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}
	// 先输出自身节点的值
	fmt.Printf("%v ", node.Value)
	// 递归遍历左子树
	RecursionPreorderTraversal(node.LeftNode)
	// 递归遍历右子树
	RecursionPreorderTraversal(node.RightNode)
}

// 中序遍历
func RecursionMiddleorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}

	// 先递归遍历左子树
	RecursionMiddleorderTraversal(node.LeftNode)
	// 再输出自身节点的值
	fmt.Printf("%v ", node.Value)
	// 最后递归遍历右子树
	RecursionMiddleorderTraversal(node.RightNode)
}

// 后序遍历
func RecursionPostorderTraversal(node *BinaryTree) {
	//如果当前节点为nil，则结束遍历
	if node == nil {
		return
	}

	// 先递归遍历左子树
	RecursionPostorderTraversal(node.LeftNode)
	// 再递归遍历右子树
	RecursionPostorderTraversal(node.RightNode)
	// 最后输出自身节点的值
	fmt.Printf("%v ", node.Value)
}

// 从root节点开始层级遍历
func LevelTraversal(rootNode *BinaryTree) {
	//如果当前节点为nil，直接结束遍历
	if rootNode == nil {
		return
	}

	// 封装成slice
	var nodeSlice []*BinaryTree
	nodeSlice = append(nodeSlice, rootNode)

	// 开始递归遍历
	RecursionTraversal(nodeSlice)
}

// 递归遍历核心
func RecursionTraversal(nodeSlice []*BinaryTree) {
	// 如果当前层级slice为空，则结束遍历
	if len(nodeSlice) == 0 {
		return
	}

	// 创建新的节点slice，存储下一层需要遍历的node
	var nextSlice []*BinaryTree

	//遍历当前nodeSlice
	for i := 0; i < len(nodeSlice); i++ {
		//取出要遍历的node
		node := nodeSlice[i]

		//输出当前node的值
		fmt.Printf("%v ", node.Value)

		//当前node左子节点append到下一层node slice中
		if node.LeftNode != nil {
			nextSlice = append(nextSlice, node.LeftNode)
		}

		//当前node右子节点append到下一层node slice中
		if node.RightNode != nil {
			nextSlice = append(nextSlice, node.RightNode)
		}
	}

	//递归遍历下一层的node slice
	RecursionTraversal(nextSlice)
}

func main() {
	RecursionPreorderTraversal(rootNode)
	fmt.Println()

	RecursionMiddleorderTraversal(rootNode)
	fmt.Println()

	RecursionPostorderTraversal(rootNode)
	fmt.Println()

	LevelTraversal(rootNode)
}