如何使用文本文件中的值来构建树结构？

积累知识，胜过积蓄金银！毕竟在Golang开发的过程中，会遇到各种各样的问题，往往都是一些细节知识点还没有掌握好而导致的，因此基础知识点的积累是很重要的。下面本文《如何使用文本文件中的值来构建树结构？》，就带大家讲解一下知识点，若是你对本文感兴趣，或者是想搞懂其中某个知识点，就请你继续往下看吧~

我正在尝试使用 go 实现 dfs（深度优先搜索）算法，但我的实际代码需要逐个节点添加来手动构建树。我想读取一个文本文件，其中包含以下数据（示例）：

75
95 64
17 47 82
18 35 87 10
20 04 83 47 65

并用这些值构建树。根值为 75，左为 95，右为 64，依此类推。

这是我的完整代码：

// Package main implements the DFS algorithm
package main

import (
    "bufio"
    "flag"
    "fmt"
    "log"
    "os"
    "strconv"
    "strings"
    "sync"
)

// Node handle all the tree data
type Node struct {
    Data  interface {}
    Left  *Node
    Right *Node
}

// NewNode creates a new node to the tree
func NewNode(data interface{}) *Node {
    node := new(Node)

    node.Data = data
    node.Left = nil
    node.Right = nil

    return node
}

// FillNodes create all the nodes based on each value on file
func FillNodes(lines *[][]string) {
    nodes := *lines

    rootInt, _ := strconv.Atoi(nodes[0][0])
    root := NewNode(rootInt)

    // add the values here

    wg.Add(1)
    go root.DFS()

    wg.Wait()

}

// ProcessNode checks and print the actual node
func (n *Node) ProcessNode() {
    defer wg.Done()

    var hello []int

    for i := 0; i < 10000; i++ {
        hello = append(hello, i)
    }

    fmt.Printf("Node    %v\n", n.Data)
}

// DFS calls itself on each node
func (n *Node) DFS() {
    defer wg.Done()

    if n == nil {
        return
    }

    wg.Add(1)
    go n.Left.DFS()

    wg.Add(1)
    go n.ProcessNode()

    wg.Add(1)
    go n.Right.DFS()
}

// CheckError handle erros check
func CheckError(err error) {
    if err != nil {
        log.Fatal(err)
    }
}

// OpenFile handle reading data from a text file
func OpenFile() [][]string {
    var lines [][]string

    ftpr := flag.String("fpath", "pyramid2.txt", "./pyramid2.txt")
    flag.Parse()

    f, err := os.Open(*ftpr)
    CheckError(err)

    defer func() {
        if err := f.Close(); err != nil {
            log.Fatal(err)
        }
    }()

    s := bufio.NewScanner(f)

    for s.Scan() {
        line := strings.Fields(s.Text())
        lines = append(lines, line)
    }

    err = s.Err()
    CheckError(err)


    return lines
}

var wg sync.WaitGroup

// Main creates the tree and call DFS
func main() {
    nodes := OpenFile()

    FillNodes(&nodes)
}

对此可能的解决方案是什么？另外，我如何以简单的方式将所有这些字符串转换为 int？

解决方案

这是创建树的方法（未测试）：

func FillLevel(parents []*Node, level []string) (children []*Node, err error){
    if len(parents) + 1 != len(level) {
        return nil, errors.New("params size not OK")
    }

    for i, p := range parents {
        leftVal, err := strconv.Atoi(level[i])
        rightVal, err := strconv.Atoi(level[i+1])
        if err != nil {
            return nil, err
        }

        p.Left = NewNode(leftVal)
        p.Right = NewNode(rightVal)
        children = append(children, p.Left)
        if i == len(parents) - 1 {
            children = append(children, p.Right)
        }
    }
    return children, nil
}

func FillNodes(lines *[][]string) (*Node, error){
    nodes := *lines

    rootInt, _ := strconv.Atoi(nodes[0][0])
    root := NewNode(rootInt)

    // add the values here
    parents := []*Node{root}
    for _, level := range nodes[1:] {
        parents, _ = FillLevel(parents, level)
    }
    return root, nil
}

func main() {
    nodes := OpenFile()
    r, _ := FillNodes(&nodes)
    wg.Add(1)
    r.DFS()
    wg.Wait()
}

如果这是用于生产，我的建议是 tdd，并正确处理所有错误并决定您的软件应该如何处理每个错误。您还可以编写一些基准测试，然后使用 goroutine 优化算法（如果适用）

按照你现在的做法，没有 goroutine 会更好： 想象一下，你有一棵巨大的树，有 1m 个节点，dfs 函数将递归启动 1m 个 goroutine，每个 goroutine 都有内存和 cpu 额外成本，但没有做太多事情来证明它的合理性。您需要一种更好的方法来将工作分配到更少的 goroutine 上，每个 goroutine 可能有 10000 个节点。

我强烈建议你编写一个没有 goroutine 的版本，研究它的复杂性，编写基准测试来验证预期的复杂性。一旦你有了这个，就开始寻找引入 goroutine 的策略，并验证它比你已有的更高效。

本篇关于《如何使用文本文件中的值来构建树结构？》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于Golang的相关知识，请关注golang学习网公众号！