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

    目录

    创建和追加的优化

    自定义包 biTree

    导入和调用

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

    广度优先搜索BFS

    深度优先搜索DFS

    遍历二叉树全部叶子结点

    BFS/DFS题目实例

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

    创建和追加的优化

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

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

    1. package main
    2.  
    3. import "fmt"
    4.  
    5. type btNode struct {
    6. 	Data           interface{}
    7. 	Lchild, Rchild *btNode
    8. }
    9.  
    10. type biTree struct {
    11. 	root *btNode
    12. }
    13.  
    14. func Create(data interface{}) *biTree {
    15. 	var list []interface{}
    16. 	btree := &biTree{}
    17. 	switch data.(type) {
    18. 	case []interface{}:
    19. 		list = append(list, data.([]interface{})...)
    20. 	default:
    21. 		list = append(list, data)
    22. 	}
    23. 	if len(list) > 0 {
    24. 		btree.root = &btNode{Data: list[0]}
    25. 		for _, data := range list[1:] {
    26. 			btree.AppendNode(data)
    27. 		}
    28. 	}
    29. 	return btree
    30. }
    31.  
    32. func (bt *biTree) Append(data interface{}) {
    33. 	var list []interface{}
    34. 	switch data.(type) {
    35. 	case []interface{}:
    36. 		list = append(list, data.([]interface{})...)
    37. 	default:
    38. 		list = append(list, data)
    39. 	}
    40. 	if len(list) > 0 {
    41. 		for _, data := range list {
    42. 			bt.AppendNode(data)
    43. 		}
    44. 	}
    45. }
    46.  
    47. func (bt *biTree) AppendNode(data interface{}) {
    48. 	root := bt.root
    49. 	if root == nil {
    50. 		bt.root = &btNode{Data: data}
    51. 		return
    52. 	}
    53. 	Queue := []*btNode{root}
    54. 	for len(Queue) > 0 {
    55. 		cur := Queue[0]
    56. 		Queue = Queue[1:]
    57. 		if cur.Lchild != nil {
    58. 			Queue = append(Queue, cur.Lchild)
    59. 		} else {
    60. 			cur.Lchild = &btNode{Data: data}
    61. 			return
    62. 		}
    63. 		if cur.Rchild != nil {
    64. 			Queue = append(Queue, cur.Rchild)
    65. 		} else {
    66. 			cur.Rchild = &btNode{Data: data}
    67. 			break
    68. 		}
    69. 	}
    70. }
    71.  
    72. func (bt *biTree) Levelorder() []interface{} {
    73. 	var res []interface{}
    74. 	root := bt.root
    75. 	if root == nil {
    76. 		return res
    77. 	}
    78. 	Queue := []*btNode{root}
    79. 	for len(Queue) > 0 {
    80. 		cur := Queue[0]
    81. 		Queue = Queue[1:]
    82. 		res = append(res, cur.Data)
    83. 		if cur.Lchild != nil {
    84. 			Queue = append(Queue, cur.Lchild)
    85. 		}
    86. 		if cur.Rchild != nil {
    87. 			Queue = append(Queue, cur.Rchild)
    88. 		}
    89. 	}
    90. 	return res
    91. }
    92.  
    93. func (bt *biTree) Preorder() []interface{} {
    94. 	var res []interface{}
    95. 	cur := bt.root
    96. 	Stack := []*btNode{}
    97. 	for cur != nil || len(Stack) > 0 {
    98. 		for cur != nil {
    99. 			res = append(res, cur.Data)
    100. 			Stack = append(Stack, cur)
    101. 			cur = cur.Lchild
    102. 		}
    103. 		if len(Stack) > 0 {
    104. 			cur = Stack[len(Stack)-1]
    105. 			Stack = Stack[:len(Stack)-1]
    106. 			cur = cur.Rchild
    107. 		}
    108. 	}
    109. 	return res
    110. }
    111.  
    112. func (bt *biTree) Inorder() []interface{} {
    113. 	var res []interface{}
    114. 	cur := bt.root
    115. 	Stack := []*btNode{}
    116. 	for cur != nil || len(Stack) > 0 {
    117. 		for cur != nil {
    118. 			Stack = append(Stack, cur)
    119. 			cur = cur.Lchild
    120. 		}
    121. 		if len(Stack) > 0 {
    122. 			cur = Stack[len(Stack)-1]
    123. 			res = append(res, cur.Data)
    124. 			Stack = Stack[:len(Stack)-1]
    125. 			cur = cur.Rchild
    126. 		}
    127. 	}
    128. 	return res
    129. }
    130.  
    131. func (bt *biTree) Postorder() []interface{} {
    132. 	var res []interface{}
    133. 	var cur, pre *btNode
    134. 	Stack := []*btNode{bt.root}
    135. 	for len(Stack) > 0 {
    136. 		cur = Stack[len(Stack)-1]
    137. 		if cur.Lchild == nil && cur.Rchild == nil ||
    138. 			pre != nil && (pre == cur.Lchild || pre == cur.Rchild) {
    139. 			res = append(res, cur.Data)
    140. 			Stack = Stack[:len(Stack)-1]
    141. 			pre = cur
    142. 		} else {
    143. 			if cur.Rchild != nil {
    144. 				Stack = append(Stack, cur.Rchild)
    145. 			}
    146. 			if cur.Lchild != nil {
    147. 				Stack = append(Stack, cur.Lchild)
    148. 			}
    149. 		}
    150. 	}
    151. 	return res
    152. }
    153.  
    154. func main() {
    155.  
    156. 	list := []interface{}{1, 2, 3, 4, 5, 6, 7}
    157.  
    158. 	tree := &biTree{}
    159. 	fmt.Println(tree.Preorder())
    160. 	tree.Append(0)
    161. 	fmt.Println(tree.Preorder())
    162. 	tree.Append(1)
    163. 	fmt.Println(tree.Preorder())
    164.  
    165. 	tree = Create(list)
    166. 	fmt.Println(tree.Preorder())
    167. 	fmt.Println(tree.Inorder())
    168. 	fmt.Println(tree.Postorder())
    169.  
    170. 	tree.Append("+")
    171. 	tree.Append("-")
    172. 	fmt.Println(tree.Inorder())
    173. 	tree.Append([]interface{}{"A", "B", "C"})
    174. 	fmt.Println(tree.Preorder())
    175. 	fmt.Println(tree.Inorder())
    176. 	fmt.Println(tree.Postorder())
    177.  
    178. }
    179.  
    180. /*
    181. []
    182. [0]
    183. [0 1]
    184. [1 2 4 5 3 6 7]
    185. [4 2 5 1 6 3 7]
    186. [4 5 2 6 7 3 1]
    187. [+ 4 - 2 5 1 6 3 7]
    188. [1 2 4 + - 5 A B 3 6 C 7]
    189. [+ 4 - 2 A 5 B 1 C 6 3 7]
    190. [+ - 4 A B 5 2 C 6 7 3 1]
    191. */

    自定义包 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使用了。

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

    导入和调用

    1. package main
    2.  
    3. import (
    4. 	"biTree" //导入二叉树自定义包 biTree
    5. 	"fmt"
    6. )
    7.  
    8. func main() {
    9.  
    10. 	list := []interface{}{1, 2, 3, 4, 5, 6, 7}
    11.  
    12. 	tree := biTree.Create(list)  //调用自定义包中的函数，需要用“包名称.”作前缀
    13. 	fmt.Println(tree.Preorder()) //调用方法则不需要前缀，tree就是此包定义的对象
    14. 	fmt.Println(tree.Inorder())
    15. 	fmt.Println(tree.Postorder())
    16. 	fmt.Println(tree.Levelorder())
    17.  
    18. 	tree.Append(0)
    19. 	tree.Append("+")
    20. 	tree.Append("-")
    21. 	fmt.Println(tree.Inorder())
    22. 	tree.Append([]interface{}{"A", "B", "C"})
    23. 	fmt.Println(tree.Preorder())
    24. 	fmt.Println(tree.Inorder())
    25. 	fmt.Println(tree.Postorder())
    26. 	fmt.Println(tree.Levelorder())
    27.  
    28. }
    29.  
    30. /*
    31. [1 2 4 5 3 6 7]
    32. [4 2 5 1 6 3 7]
    33. [4 5 2 6 7 3 1]
    34. [1 2 3 4 5 6 7]
    35. [0 4 + 2 - 5 1 6 3 7]
    36. [1 2 4 0 + 5 - A 3 6 B C 7]
    37. [0 4 + 2 - 5 A 1 B 6 C 3 7]
    38. [0 + 4 - A 5 2 B C 6 7 3 1]
    39. [1 2 3 4 5 6 7 0 + - A B C]
    40. */

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

    是连通图等图结构的一种遍历算法原型，而树也可以看作是一种没用环的特殊图结构。

    广度优先搜索BFS

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

    深度优先搜索DFS

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

    遍历二叉树全部叶子结点

    递归法：

    1. func (bt *btNode) leaves() []interface{} {
    2. 	var res []interface{}
    3. 	if bt != nil {
    4. 		if bt.Lchild == nil && bt.Rchild == nil {
    5. 			res = append(res, bt.Data)
    6. 		}
    7. 		res = append(res, bt.Lchild.leaves()...)
    8. 		res = append(res, bt.Rchild.leaves()...)
    9. 	}
    10. 	return res
    11. }

    广度优先BFS：

    1. func (bt *biTree) LeafNodeBFS() []interface{} {
    2. 	var res []interface{}
    3. 	root := bt.root
    4. 	if root == nil {
    5. 		return res
    6. 	}
    7. 	Queue := []*btNode{root}
    8. 	for len(Queue) > 0 {
    9. 		cur := Queue[0]
    10. 		Queue = Queue[1:]
    11. 		if cur.Lchild == nil && cur.Rchild == nil {
    12. 			res = append(res, cur.Data)
    13. 		}
    14. 		if cur.Lchild != nil {
    15. 			Queue = append(Queue, cur.Lchild)
    16. 		}
    17. 		if cur.Rchild != nil {
    18. 			Queue = append(Queue, cur.Rchild)
    19. 		}
    20. 	}
    21. 	return res
    22. }

    深度优先DFS：

    1. func (bt *biTree) LeafNodeDFS() []interface{} {
    2. 	var res []interface{}
    3. 	cur := bt.root
    4. 	Stack := []*btNode{}
    5. 	for cur != nil || len(Stack) > 0 {
    6. 		for cur != nil {
    7. 			if cur.Lchild == nil && cur.Rchild == nil {
    8. 				res = append(res, cur.Data)
    9. 			}
    10. 			Stack = append(Stack, cur)
    11. 			cur = cur.Lchild
    12. 		}
    13. 		if len(Stack) > 0 {
    14. 			cur = Stack[len(Stack)-1]
    15. 			Stack = Stack[:len(Stack)-1]
    16. 			cur = cur.Rchild
    17. 		}
    18. 	}
    19. 	return res
    20. }

    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备用：

    1. func (bt *biTree) BForder2D() [][]interface{} {
    2. 	var res [][]interface{}
    3. 	root := bt.root
    4. 	if root == nil {
    5. 		return res
    6. 	}
    7. 	Queue := []*btNode{root}
    8. 	for len(Queue) > 0 {
    9. 		Nodes := []interface{}{}
    10. 		Levels := len(Queue)
    11. 		for Levels > 0 {
    12. 			cur := Queue[0]
    13. 			Queue = Queue[1:]
    14. 			Nodes = append(Nodes, cur.Data)
    15. 			Levels--
    16. 			if cur.Lchild != nil {
    17. 				Queue = append(Queue, cur.Lchild)
    18. 			}
    19. 			if cur.Rchild != nil {
    20. 				Queue = append(Queue, cur.Rchild)
    21. 			}
    22. 		}
    23. 		res = append(res, Nodes)
    24. 	}
    25. 	return res
    26. }

    遍历过程如以下动图：

    测试代码：

    1. package main
    2.  
    3. import (
    4. 	"biTree" //导入二叉树自定义包 biTree
    5. 	"fmt"
    6. )
    7.  
    8. func main() {
    9.  
    10. 	list1 := []interface{}{1, 2, 4, 5, 6}
    11. 	list2 := []interface{}{3, 9, 20, 15, 7}
    12.  
    13. 	tree := biTree.Create(list1)
    14. 	fmt.Println(tree.BForder2D())
    15.  
    16. 	tree = biTree.Create(list2)
    17. 	fmt.Println(tree.BForder2D())
    18.  
    19. }
    20.  
    21. /*
    22. [[1] [2 4] [5 6]]
    23. [[3] [9 20] [15 7]]
    24. */

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

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

    1. func Build(data interface{}) *biTree {
    2. 	var list []interface{}
    3. 	if data == nil {
    4. 		return &biTree{}
    5. 	}
    6. 	switch data.(type) {
    7. 	case []interface{}:
    8. 		list = append(list, data.([]interface{})...)
    9. 	default:
    10. 		list = append(list, data)
    11. 	}
    12. 	if len(list) == 0 {
    13. 		return &biTree{}
    14. 	}
    15. 	node := &btNode{Data: list[0]}
    16. 	list = list[1:]
    17. 	Queue := []*btNode{node}
    18. 	for len(list) > 0 {
    19. 		if len(Queue) == 0 {
    20. 			//panic("Given array can not build binary tree.")
    21. 			//for example: {1, nil, nil, 2, 3}
    22. 			return &biTree{root: node}
    23. 		}
    24. 		cur := Queue[0]
    25. 		val := list[0]
    26. 		Queue = Queue[1:]
    27. 		if val != nil {
    28. 			cur.Lchild = &btNode{Data: val}
    29. 			if cur.Lchild != nil {
    30. 				Queue = append(Queue, cur.Lchild)
    31. 			}
    32. 		}
    33. 		list = list[1:]
    34. 		if len(list) > 0 {
    35. 			val := list[0]
    36. 			if data != nil {
    37. 				cur.Rchild = &btNode{Data: val}
    38. 				if cur.Rchild != nil {
    39. 					Queue = append(Queue, cur.Rchild)
    40. 				}
    41. 			}
    42. 			list = list[1:]
    43. 		}
    44. 	}
    45. 	return &biTree{root: node}
    46. }

    测试代码：

    1. package main
    2.  
    3. import (
    4. 	"biTree" //导入二叉树自定义包 biTree
    5. 	"fmt"
    6. )
    7.  
    8. func main() {
    9.  
    10. 	list := []interface{}{3, 9, 20, nil, nil, 15, 7}
    11.  
    12. 	tree := biTree.Build(list)
    13. 	fmt.Println(tree.BForder2D())
    14.  
    15. 	fmt.Println(tree.Levelorder())
    16. 	fmt.Println(tree.Preorder())
    17. 	fmt.Println(tree.Inorder())
    18. 	fmt.Println(tree.Postorder())
    19.  
    20. 	list = []interface{}{3, 9, 20, 15, 7}
    21. 	tree = biTree.Build(list)
    22. 	fmt.Println(tree.BForder2D())
    23.  
    24. 	fmt.Println(tree.Levelorder())
    25. 	fmt.Println(tree.Preorder())
    26. 	fmt.Println(tree.Inorder())
    27. 	fmt.Println(tree.Postorder())
    28. }
    29.  
    30. /*
    31. [[3] [9 20] [15 7]]
    32. [3 9 20 15 7]
    33. [3 9 20 15 7]
    34. [9 3 15 20 7]
    35. [9 15 7 20 3]
    36. [[3] [9 20] [15 7]]
    37. [3 9 20 15 7]
    38. [3 9 15 7 20]
    39. [15 9 7 3 20]
    40. [15 7 9 20 3]
    41. */

    实例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]

  • 相关阅读:
    剑指 Offer 13. 机器人的运动范围
    YOLOv8改进 | 2023 | InnerIoU、InnerSIoU、InnerWIoU、FoucsIoU等损失函数
    mac的Jupyter怎么使用
    WPS相关使用
    如何公网远程访问本地群晖NAS File Station文件夹
    国学短剧《我是小影星》栏目火热开拍
    老板让你Excel统计数据无从下手？没事，ChatGPT来帮你！
    VCS工具学习笔记（6）
    搭建zerotier planet服务
    微信小程序ios下，border显示不全兼容问题解决
  • 原文地址：https://blog.csdn.net/boysoft2002/article/details/126556516