go语言｜数据结构：二叉树（2）广度和深度搜索-阿里云开发者社区

创建和追加的优化

对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:\Users\admin>set gopath

GOPATH=C:\Users\admin\go;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]