网络知识 娱乐 go语言｜数据结构：二叉树（2）广度和深度搜索

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

发布: 2023年2月14日 10:17:50

目录

创建和追加的优化

自定义包 biTree

导入和调用

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

广度优先搜索BFS

深度优先搜索DFS

遍历二叉树全部叶子结点

BFS/DFS题目实例

实例1：层序遍历二叉树成二维数组
实例2：Z字型层序遍历二叉树成二维数组
实例3：二叉树从根到叶子的最大深度和最小深度
实例4：二叉树最下一层的最左边的叶子结点
实例5：找出二叉树每一层的最大值

创建和追加的优化

对Append()和buildTree()的参数作判断，可以是数组也可以单个数据

要用数组作结点数据域，只能使用appendNode()来创建

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

上面的代码中，去掉import "fmt"一行 及 main()函数全部，package main替换成 package biTree，然后另存为 biTree.go。

接下来在DOS窗口用set gopath查看GOPATH变量，我的电脑返回：

C:Usersadmin>set gopath

GOPATH=C:Usersadmingo;d:GOsrc

在gopath的任一路径下新建一个src文件夹，再在src下新建biTree文件夹，最后把biTree.go存放到此文件夹下，就能导入import使用了。

注意：自定义包中的函数和方法命名时一定要首字母大写，否则调用会无法找到。

导入和调用

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
}

广度优先BFS：

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
}

深度优先DFS：

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]]，代码略。

遍历代码如下，把它写进biTree.go备用：

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]]
*/

注意：代码遍历方法是正确的，但是题目给定的数组是 [3,9,20,null,null,15,7]，而Create()函数按层再从左到右添加结点的，它创建的是一个完全二叉树。需要增加对数据域的类型判断，空值在Go语言中用nil表示，在遍历数组时碰到nil值，则跳过创建此结点，这样就可以创建一个非完全二叉树。另外存在没法创建的可能，比如： {1, nil, nil, 2, 3}，要么忽略要么抛出错误。

改进后的创建代码Build()函数，放进biTree.go，以备调用。

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]

相关文章