Golang implementiert die Vorbestellungsdurchquerung

Vorbestellungsdurchquerung ist eine Art Binärbaumdurchquerung. Die Durchquerungsreihenfolge besteht darin, zuerst den Wurzelknoten, dann den linken Teilbaum und schließlich den rechten Teilbaum zu durchqueren. In Golang können rekursive Algorithmen verwendet werden, um die Durchquerung vor der Bestellung zu implementieren.

Zuerst müssen wir die Struktur des Binärbaumknotens definieren, einschließlich des Knotenwerts, des linken Teilbaums und des rechten Teilbaumzeigers.

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

Als nächstes können wir eine rekursive FunktionPreOrder definieren, um eine Vorbestellungsdurchquerung durchzuführen.

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
}

In der Funktion bestimmen wir zunächst, ob der Wurzelknoten leer ist, und wenn er leer ist, geben wir ein leeres Slice zurück.

Ansonsten addieren wir zunächst den Wert des Wurzelknotens zum Ergebnis, rufen dann rekursiv den linken Teilbaum und den rechten Teilbaum auf und führen sie zum Ergebnis zusammen.

Das zurückgegebene Ergebnis ist schließlich das Ergebnis der Vorbestellungsdurchquerung.

Nachfolgend finden Sie einen vollständigen Beispielcode.

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)
}

Das Ausgabeergebnis ist: [1 2 4 5 3 6 7], was das Ergebnis der Vorbestellungsdurchquerung des Binärbaums ist.

Durch den rekursiven Algorithmus ist es sehr einfach, die Binärbaum-Vorbestellungsdurchquerung in Golang zu implementieren, und es sind nur wenige Codezeilen erforderlich.

Das obige ist der detaillierte Inhalt vonGolang implementiert die Vorbestellungsdurchquerung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!