golang implements preorder traversal-Golang-php.cn

golang implements preorder traversal

王林

Release： 2023-05-10 12:04:07

Original

360 people have browsed it

Preorder traversal is a type of binary tree traversal. The traversal order is to traverse the root node first, then traverse the left subtree, and finally traverse the right subtree. In golang, recursive algorithms can be used to implement preorder traversal.

First, we need to define the structure of the binary tree node, including the node value, left subtree and right subtree pointers.

type Node struct {
        Value int
        Left  *Node
        Right *Node
}

Copy after login

Next, we can define the recursive function PreOrder to perform preorder traversal.

func PreOrder(root *Node) []int {
        if root == nil {
                return []int{}
        }
        result := make([]int, 0)
        result = append(result, root.Value)
        result = append(result, PreOrder(root.Left)...)
        result = append(result, PreOrder(root.Right)...)
        return result
}

Copy after login

In the function, we first determine whether the root node is empty. If it is empty, an empty slice is returned.

Otherwise, we first add the value of the root node to the result, then recursively call the left subtree and right subtree and merge them into the result.

Finally, the result returned is the result of the preorder traversal.

The following is a complete sample code.

package main

import "fmt"

type Node struct {
        Value int
        Left  *Node
        Right *Node
}

func PreOrder(root *Node) []int {
        if root == nil {
                return []int{}
        }
        result := make([]int, 0)
        result = append(result, root.Value)
        result = append(result, PreOrder(root.Left)...)
        result = append(result, PreOrder(root.Right)...)
        return result
}

func main() {
        root := &Node{
                Value: 1,
                Left: &Node{
                        Value: 2,
                        Left: &Node{
                                Value: 4,
                        },
                        Right: &Node{
                                Value: 5,
                        },
                },
                Right: &Node{
                        Value: 3,
                        Left: &Node{
                                Value: 6,
                        },
                        Right: &Node{
                                Value: 7,
                        },
                },
        }
        result := PreOrder(root)
        fmt.Println(result)
}

Copy after login

The output result is: [1 2 4 5 3 6 7], which is the result of pre-order traversal of the binary tree.

Through the recursive algorithm, it is very simple to implement binary tree preorder traversal in golang and only requires a few lines of code to complete.

The above is the detailed content of golang implements preorder traversal. For more information, please follow other related articles on the PHP Chinese website!