Golang 二叉树的层次遍历

在编程中，有不同的数据结构用于存储数据。线性和非线性是两种不同类型的数据结构。数组、堆栈、队列和链表是线性数据结构。二叉树、字典树等是非线性数据结构。在本文中，我们将探索在非线性数据结构之一——二叉树上的层次遍历。

层次遍历

在二叉树的层次遍历中，我们从根节点开始，然后遍历子节点并移动到子节点的子节点。这样，我们到达最后一层并完成层次遍历。为了实现这一点，我们使用广度优先搜索算法，其中使用队列数据结构。

例如，在上面的树中：

Level 1： 遍历根节点1

Level 2： 先遍历节点2，然后节点3，最后节点4

Level 3： 先遍历节点5，然后节点6，最后节点7

步骤

步骤1：import “fmt” − 引入fmt库

步骤2：type TreeNode struct { Val int Left *TreeNode Right *TreeNode } − 创建一个树节点的结构体，它有一个整数值用于存储节点数据，以及两个指向树节点的指针。

步骤3： 开始主函数

• root := TreeNode{0, nil, nil} − 创建一个根节点的变量，类型为树节点。

• 调用函数 CreateBinaryTree( &root)创建完全二叉树。

• levelOrder := LevelOrderTraversal( &root) −** 通过传递对根节点的引用来调用函数执行层次遍历。

• 打印层次遍历函数返回的数组。

步骤4： 层次遍历函数。

• func LevelOrderTraversal(root *TreeNode) []int {} − 声明一个函数，它的参数是类型为TreeNode的变量，返回类型是整数数组。

• if root == nil { return []int{} } −** 检查根节点是否为nil，如果是则返回一个空数组。

• 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分别是图中顶点和边的数量。我们也可以使用深度优先搜索算法找到一棵树的层序遍历。要了解更多关于Golang的内容，您可以浏览这些 教程 。