golang melaksanakan preorder traversal-Golang-php.cn

golang melaksanakan preorder traversal

王林

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

asal

436 orang telah melayarinya

Preorder traversal ialah sejenis binari tree traversal Urutan traversal adalah untuk melintasi nod akar dahulu, kemudian melintasi subtree kiri, dan akhirnya melintasi subtree kanan. Dalam golang, algoritma rekursif boleh digunakan untuk melaksanakan traversal prapesanan.

Pertama, kita perlu mentakrifkan struktur nod pokok binari, termasuk nilai nod, subpokok kiri dan penunjuk subpokok kanan.

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

Salin selepas log masuk

Seterusnya, kita boleh mentakrifkan fungsi rekursif PreOrder untuk melakukan traversal prapesanan.

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
}

Salin selepas log masuk

Dalam fungsi, kita mula-mula menentukan sama ada nod akar kosong, dan jika ia kosong, kembalikan kepingan kosong.

Jika tidak, kami mula-mula menambah nilai nod akar pada hasil, kemudian secara rekursif memanggil subpokok kiri dan subpokok kanan dan menggabungkannya ke dalam hasilnya.

Akhir sekali, hasil yang dikembalikan adalah hasil preorder traversal.

Di bawah ialah kod contoh lengkap.

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

Salin selepas log masuk

Hasil keluaran ialah: [1 2 4 5 3 6 7], yang merupakan hasil prapesan traversal pokok binari.

Melalui algoritma rekursif, sangat mudah untuk melaksanakan traversal prapesanan pokok binari dalam golang dan hanya memerlukan beberapa baris kod untuk diselesaikan.

Atas ialah kandungan terperinci golang melaksanakan preorder traversal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!