# go语言｜数据结构：二叉树（2）广度和深度搜索

+关注继续查看

## 创建和追加的优化

package main

import "fmt"

type btNode struct {
Data           interface{}
Lchild, Rchild *btNode
}

type biTree struct {
root *btNode
}

func Create(data interface{}) *biTree {
var list []interface{}
btree := &biTree{}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) > 0 {
btree.root = &btNode{Data: list[0]}
for _, data := range list[1:] {
btree.AppendNode(data)
}
}
return btree
}

func (bt *biTree) Append(data interface{}) {
var list []interface{}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) > 0 {
for _, data := range list {
bt.AppendNode(data)
}
}
}

func (bt *biTree) AppendNode(data interface{}) {
root := bt.root
if root == nil {
bt.root = &btNode{Data: data}
return
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
} else {
cur.Lchild = &btNode{Data: data}
return
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
} else {
cur.Rchild = &btNode{Data: data}
break
}
}
}

func (bt *biTree) Levelorder() []interface{} {
var res []interface{}
root := bt.root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
res = append(res, cur.Data)
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
return res
}

func (bt *biTree) Preorder() []interface{} {
var res []interface{}
cur := bt.root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
res = append(res, cur.Data)
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}

func (bt *biTree) Inorder() []interface{} {
var res []interface{}
cur := bt.root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
res = append(res, cur.Data)
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}

func (bt *biTree) Postorder() []interface{} {
var res []interface{}
var cur, pre *btNode
Stack := []*btNode{bt.root}
for len(Stack) > 0 {
cur = Stack[len(Stack)-1]
if cur.Lchild == nil && cur.Rchild == nil ||
pre != nil && (pre == cur.Lchild || pre == cur.Rchild) {
res = append(res, cur.Data)
Stack = Stack[:len(Stack)-1]
pre = cur
} else {
if cur.Rchild != nil {
Stack = append(Stack, cur.Rchild)
}
if cur.Lchild != nil {
Stack = append(Stack, cur.Lchild)
}
}
}
return res
}

func main() {

list := []interface{}{1, 2, 3, 4, 5, 6, 7}

tree := &biTree{}
fmt.Println(tree.Preorder())
tree.Append(0)
fmt.Println(tree.Preorder())
tree.Append(1)
fmt.Println(tree.Preorder())

tree = Create(list)
fmt.Println(tree.Preorder())
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())

tree.Append("+")
tree.Append("-")
fmt.Println(tree.Inorder())
tree.Append([]interface{}{"A", "B", "C"})
fmt.Println(tree.Preorder())
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())

}

/*
[]
[0]
[0 1]
[1 2 4 5 3 6 7]
[4 2 5 1 6 3 7]
[4 5 2 6 7 3 1]
[+ 4 - 2 5 1 6 3 7]
[1 2 4 + - 5 A B 3 6 C 7]
[+ 4 - 2 A 5 B 1 C 6 3 7]
[+ - 4 A B 5 2 C 6 7 3 1]
*/

## 自定义包 biTree

### 导入和调用

package main

import (
"biTree" //导入二叉树自定义包 biTree
"fmt"
)

func main() {

list := []interface{}{1, 2, 3, 4, 5, 6, 7}

tree := biTree.Create(list)  //调用自定义包中的函数，需要用“包名称.”作前缀
fmt.Println(tree.Preorder()) //调用方法则不需要前缀，tree就是此包定义的对象
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())
fmt.Println(tree.Levelorder())

tree.Append(0)
tree.Append("+")
tree.Append("-")
fmt.Println(tree.Inorder())
tree.Append([]interface{}{"A", "B", "C"})
fmt.Println(tree.Preorder())
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())
fmt.Println(tree.Levelorder())

}

/*
[1 2 4 5 3 6 7]
[4 2 5 1 6 3 7]
[4 5 2 6 7 3 1]
[1 2 3 4 5 6 7]
[0 4 + 2 - 5 1 6 3 7]
[1 2 4 0 + 5 - A 3 6 B C 7]
[0 4 + 2 - 5 A 1 B 6 C 3 7]
[0 + 4 - A 5 2 B C 6 7 3 1]
[1 2 3 4 5 6 7 0 + - A B C]
*/

## 广度优先搜索BFS & 深度优先搜索DFS

### 广度优先搜索BFS

Breath First Search，也称宽度优先搜索，缩写BFS。也即先横向再纵向的搜索，BFS使用队列来实现。BFS就是上一集中写的层序遍历Levelorder()，层序遍历即广度优先。

### 深度优先搜索DFS

Depth First Search，缩写DFS。也即先纵向再横向的搜索，DFS使用来实现。DFS就是上一集中写的先序遍历Preorder()，可认为先序遍历即深度优先。

### 遍历二叉树全部叶子结点

func (bt *btNode) leaves() []interface{} {
var res []interface{}
if bt != nil {
if bt.Lchild == nil && bt.Rchild == nil {
res = append(res, bt.Data)
}
res = append(res, bt.Lchild.leaves()...)
res = append(res, bt.Rchild.leaves()...)
}
return res
}

func (bt *biTree) LeafNodeBFS() []interface{} {
var res []interface{}
root := bt.root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
cur := Queue[0]
Queue = Queue[1:]
if cur.Lchild == nil && cur.Rchild == nil {
res = append(res, cur.Data)
}
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
return res
}

func (bt *biTree) LeafNodeDFS() []interface{} {
var res []interface{}
cur := bt.root
Stack := []*btNode{}
for cur != nil || len(Stack) > 0 {
for cur != nil {
if cur.Lchild == nil && cur.Rchild == nil {
res = append(res, cur.Data)
}
Stack = append(Stack, cur)
cur = cur.Lchild
}
if len(Stack) > 0 {
cur = Stack[len(Stack)-1]
Stack = Stack[:len(Stack)-1]
cur = cur.Rchild
}
}
return res
}

## BFS/DFS题目实例

### 实例1：层序遍历二叉树成二维数组

(leetcode102#) Binary Tree Level Order Traversal
Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For Example:
Given binary tree [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
(leetcode107#) Binary Tree Level Order Traversal II

102题的结果倒序，返回[[3],[9,20],[15,7]]，代码略。

func (bt *biTree) BForder2D() [][]interface{} {
var res [][]interface{}
root := bt.root
if root == nil {
return res
}
Queue := []*btNode{root}
for len(Queue) > 0 {
Nodes := []interface{}{}
Levels := len(Queue)
for Levels > 0 {
cur := Queue[0]
Queue = Queue[1:]
Nodes = append(Nodes, cur.Data)
Levels--
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
res = append(res, Nodes)
}
return res
}

package main

import (
"biTree" //导入二叉树自定义包 biTree
"fmt"
)

func main() {

list1 := []interface{}{1, 2, 4, 5, 6}
list2 := []interface{}{3, 9, 20, 15, 7}

tree := biTree.Create(list1)
fmt.Println(tree.BForder2D())

tree = biTree.Create(list2)
fmt.Println(tree.BForder2D())

}

/*
[[1] [2 4] [5 6]]
[[3] [9 20] [15 7]]
*/

func Build(data interface{}) *biTree {
var list []interface{}
if data == nil {
return &biTree{}
}
switch data.(type) {
case []interface{}:
list = append(list, data.([]interface{})...)
default:
list = append(list, data)
}
if len(list) == 0 {
return &biTree{}
}
node := &btNode{Data: list[0]}
list = list[1:]
Queue := []*btNode{node}
for len(list) > 0 {
if len(Queue) == 0 {
//panic("Given array can not build binary tree.")
//for example: {1, nil, nil, 2, 3}
return &biTree{root: node}
}
cur := Queue[0]
val := list[0]
Queue = Queue[1:]
if val != nil {
cur.Lchild = &btNode{Data: val}
if cur.Lchild != nil {
Queue = append(Queue, cur.Lchild)
}
}
list = list[1:]
if len(list) > 0 {
val := list[0]
if data != nil {
cur.Rchild = &btNode{Data: val}
if cur.Rchild != nil {
Queue = append(Queue, cur.Rchild)
}
}
list = list[1:]
}
}
return &biTree{root: node}
}

package main

import (
"biTree" //导入二叉树自定义包 biTree
"fmt"
)

func main() {

list := []interface{}{3, 9, 20, nil, nil, 15, 7}

tree := biTree.Build(list)
fmt.Println(tree.BForder2D())

fmt.Println(tree.Levelorder())
fmt.Println(tree.Preorder())
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())

list = []interface{}{3, 9, 20, 15, 7}
tree = biTree.Build(list)
fmt.Println(tree.BForder2D())

fmt.Println(tree.Levelorder())
fmt.Println(tree.Preorder())
fmt.Println(tree.Inorder())
fmt.Println(tree.Postorder())
}

/*
[[3] [9 20] [15 7]]
[3 9 20 15 7]
[3 9 20 15 7]
[9 3 15 20 7]
[9 15 7 20 3]
[[3] [9 20] [15 7]]
[3 9 20 15 7]
[3 9 15 7 20]
[15 9 7 3 20]
[15 7 9 20 3]
*/

### 实例2：Z字型层序遍历二叉树成二维数组

(leetcode103#) Binary Tree Zigzag Level Order Traversal
Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).
For Example:
Given binary tree [3,9,20,null,null,15,7],

3
/ \
9 20
/ \
15 7

return its zigzag level order traversal as:

[
[3],
[20,9],
[15,7]
]

### 实例3：二叉树从根到叶子的最大深度和最小深度

(leetcode104#) Maximum Depth of Binary Tree

Given a binary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Note: A leaf is a node with no children.

(leetcode111#) Minimum Depth of Binary Tree

### 实例4：二叉树最下一层的最左边的叶子结点

(leetcode513#) Find Bottom Left Tree Value

Given a binary tree, find the leftmost value in the last row of the tree.
Example 1:
Input:
2
/ \
1 3
Output:
1
Example 2:
Input:
1
/ \
2   3
/    /  \
4  5   6
/
7
Output:
7
Note: You may assume the tree (i.e., the given root node) is not NULL.

### 实例5：找出二叉树每一层的最大值

(leetcode 515#) Find Largest Value in Each Tree Row
You need to find the largest value in each row of a binary tree.
Example:
Input:
1
/ \
3  2
/ \    \
5  3   9
Output: [1, 3, 9]

|
23小时前
|
Go 索引
Go语言中的数组、切片和映射解析
Go语言中的数组、切片和映射解析
7 0
|
4天前
|

18 0
|
4天前
|

Go 语言内置类型全解析：从布尔到字符串的全维度探究
Go 语言内置类型全解析：从布尔到字符串的全维度探究
18 0
|
7天前
|
Java Go 开发工具
Go 语言内存管理详解
Go 语言内存管理详解
17 0
|
7天前
|

Go语言进阶-工程进阶
Go语言进阶-工程进阶
17 0
|
8天前
|

GO语言学习 - 创建TCP监听
GO语言学习 - 创建TCP监听
88 0
|
8天前
|
Go
GO语言学习-读取本地文本文件
GO语言学习-读取本地文本文件
73 0
|
18天前
|

Golang并发编程技术：解锁Go语言的并行潜力

24 0
|
19天前
|
Java 编译器 Go

27 0
|
22天前
|

39 3