我如何读取文本文件并根据这些值实现树？

Question

我正在尝试使用 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

}

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

Answer 1

这是创建树的方法（未测试）：func FillLevel(parents []*Node, level []string) (children []*Node, err error){&nbsp; &nbsp; if len(parents) + 1 != len(level) {&nbsp; &nbsp; &nbsp; &nbsp; return nil, errors.New("params size not OK")&nbsp; &nbsp; }&nbsp; &nbsp; for i, p := range parents {&nbsp; &nbsp; &nbsp; &nbsp; leftVal, err := strconv.Atoi(level[i])&nbsp; &nbsp; &nbsp; &nbsp; rightVal, err := strconv.Atoi(level[i+1])&nbsp; &nbsp; &nbsp; &nbsp; if err != nil {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return nil, err&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; p.Left = NewNode(leftVal)&nbsp; &nbsp; &nbsp; &nbsp; p.Right = NewNode(rightVal)&nbsp; &nbsp; &nbsp; &nbsp; children = append(children, p.Left)&nbsp; &nbsp; &nbsp; &nbsp; if i == len(parents) - 1 {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; children = append(children, p.Right)&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return children, nil}func FillNodes(lines *[][]string) (*Node, error){&nbsp; &nbsp; nodes := *lines&nbsp; &nbsp; rootInt, _ := strconv.Atoi(nodes[0][0])&nbsp; &nbsp; root := NewNode(rootInt)&nbsp; &nbsp; // add the values here&nbsp; &nbsp; parents := []*Node{root}&nbsp; &nbsp; for _, level := range nodes[1:] {&nbsp; &nbsp; &nbsp; &nbsp; parents, _ = FillLevel(parents, level)&nbsp; &nbsp; }&nbsp; &nbsp; return root, nil}func main() {&nbsp; &nbsp; nodes := OpenFile()&nbsp; &nbsp; r, _ := FillNodes(&nodes)&nbsp; &nbsp; wg.Add(1)&nbsp; &nbsp; r.DFS()&nbsp; &nbsp; wg.Wait()}如果这是用于生产，我的建议是对它进行 TDD，并正确处理所有错误并决定您的软件应该如何处理每个错误。您还可以编写一些基准，然后使用 goroutine 优化算法（如果适用）你现在的做法，没有 goroutines 会更好：想象你有一个巨大的树，有 1M 个节点，DFS 函数将递归启动 1M 个 goroutines，每个 goroutines 都有内存和 CPU 额外成本而不做很多来证明它是合理的。您需要一种更好的方法来拆分工作以在更少的 goroutine 上完成，每个 goroutine 可能有 10000 个节点。我强烈建议你编写一个没有 goroutines 的版本，研究它的复杂性，编写基准来验证预期的复杂性。一旦你有了它，就开始寻找引入 goroutines 的策略，并验证它是否比你已经拥有的更有效。