数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究Go 语言二叉树层序遍历程序
在编程中，有多种数据结构用于存储数据。数据结构主要分为线性结构和非线性结构两种。数组、栈、队列和链表是线性数据结构。二叉树、Trie 树等是非线性数据结构。本文将探讨非线性数据结构之一——二叉树的层序遍历。
层序遍历
在二叉树的层序遍历中，我们从根节点开始，然后遍历子节点，再依次遍历子节点的子节点。以此类推，直到遍历到最后一层，完成层序遍历。为了实现这一点，我们使用广度优先搜索算法，其中使用队列数据结构。
例如，在上图所示的树中
第 1 层：遍历根节点 1
第 2 层：依次遍历节点 2、节点 3 和节点 4。
第 3 层：依次遍历节点 5、节点 6 和节点 7。
算法
步骤 1：导入 "fmt" - 导入 fmt 库
步骤 2：type TreeNode struct { Val int Left *TreeNode Right *TreeNode } - 创建一个树节点的结构体，其中包含一个整数类型的 Val 用于存储节点数据，以及两个 TreeNode 类型的指针 Left 和 Right。
步骤 3：开始主函数
root : = TreeNode{0, nil, nil} - 创建一个变量 root，表示树的根节点，类型为 TreeNode。
调用函数 CreateBinaryTree(&root) 创建完整的二叉树。
levelOrder : = LevelOrderTraversal(&root) - 调用函数 LevelOrderTraversal 执行层序遍历，并将根节点的引用作为参数传递。
打印层序遍历函数返回的数组。
步骤 4：层序遍历函数。
func LevelOrderTraversal(root *TreeNode) []int {} - 声明一个函数，TreeNode 类型的变量作为参数，返回一个整数数组。
if root == nil { return []int{} } - 检查根节点是否为空，如果为空则返回一个空数组。
var q Queue - 创建一个队列，用于实现广度优先搜索算法。
var levelOrder []int - 创建一个数组，用于在层序遍历过程中存储节点的值。
应用广度优先搜索算法，最后返回数组。
示例
在此代码中，我们实现了队列数据结构及其函数，因为目前 Go 语言中没有预构建的队列库。
package main
import "fmt"
type Queue struct {
List [](*TreeNode)
}
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
// function to add an element in the queue
func (q *Queue) Enqueue(element *TreeNode) {
q.List = append(q.List, element)
}
// function to delete elements in the queue
func (q *Queue) Dequeue() *TreeNode {
if q.isEmpty() {
fmt.Println("Queue is empty.")
return nil
}
element := q.List[0]
q.List = q.List[1:]
return element
}
// function checks that queue is empty or not
func (q *Queue) isEmpty() bool {
return len(q.List) == 0
}
// function to find the length of the queue
func (q *Queue) size() int {
return len(q.List)
}
// creating binary tree
func CreateBinaryTree(root *TreeNode) {
n1 := TreeNode{1, nil, nil}
n2 := TreeNode{2, nil, nil}
root.Left = &n1
root.Right = &n2
n3 := TreeNode{3, nil, nil}
n4 := TreeNode{4, nil, nil}
n1.Left = &n3
n1.Right = &n4
n5 := TreeNode{5, nil, nil}
n6 := TreeNode{6, nil, nil}
n2.Left = &n5
n2.Right = &n6
}
// level order traversal of a function with root node as argument
// and returns the right-view elements in the array
func LevelOrderTraversal(root *TreeNode) []int {
// returning empty array if the tree is empty
if root == nil {
return []int{}
}
// creating variable for queue
var q Queue
// creating array to store right side element
var levelOrder []int
// enqueue root address in the queue
q.Enqueue(root)
q.Enqueue(nil)
// breadth-first search over the tree
for q.size() > 1 {
currNode := q.Dequeue()
if currNode == nil {
q.Enqueue(nil)
levelOrder = append(levelOrder, -1)
continue
}
levelOrder = append(levelOrder, currNode.Val)
if currNode.Left != nil {
q.Enqueue(currNode.Left)
}
if currNode.Right != nil {
q.Enqueue(currNode.Right)
}
}
return levelOrder
}
func main() {
fmt.Println("Golang program to find the level order traversal of a binary tree.")
// creating root node of binary tree
root := TreeNode{0, nil, nil}
// calling CreateBinaryTree function to create a complete binary tree
CreateBinaryTree(&root)
// calling LevelOrderTraversal function
levelOrder := LevelOrderTraversal(&root)
// print elements of binary tree in level order
for i := 0; i < len(levelOrder); i++ {
if levelOrder[i] == -1 {
fmt.Println()
continue
}
fmt.Print(levelOrder[i], " ")
}
fmt.Println()
}
输出
Golang program to find the level order traversal of a binary tree. 0 1 2 3 4 5 6
结论
通过这种方式，我们使用广度优先搜索算法实现了树的层序遍历。树还有其他遍历算法，例如中序遍历、先序遍历和后序遍历。此方法的时间复杂度为 O(V + E)，其中 V 和 E 分别是图中的顶点数和边数。我们也可以使用深度优先搜索算法来查找树的层序遍历。要了解更多关于 Go 语言的信息，您可以浏览这些 教程。
345 次浏览
