在 Go 中遍历孩子的谱系

Question

我有一个庞大的人口谱系 ( map[int][]int)，其中关键是动物，而价值切片中的父母 (两个)。没有父母的动物将有父母的负整数。其次，我有一个动物列表，我想建立它们的特定谱系并写入文件。我列表谱系中的所有动物都应该写入同一个文件。pedigree := map[int][]int{    1:  []int{2, 3},    2:  []int{-1, 5},    3:  []int{6, 7},    4:  []int{8, 9},    5:  []int{-1, -2},    6:  []int{8, -2},    7:  []int{-1, -2},    8:  []int{-1, -2},    9:  []int{10, -2},    10: []int{-1, 4}}list := []int{1, 4}以及我对 io.Writer 编写的文件的期望：  1   2   3  2  -1   5  3   6   7  5  -1  -2  6   8  -2  7  -1  -2  8  -1  -2  4   8   9  9  10  -2 10  -1   4所以我需要一个递归函数来遍历从基础动物开始的谱系，然后在所有路径上继续，直到达到负数的父母。更重要的是，我列表中的动物被确定为导致谱系周期的动物（动物 4 成为其自身的伟大父母）。我已经使用以下代码进行了尝试：type tree struct {    sire   *tree    dam    *tree    animal int    base   int    path   []int}func newTree(a, s, d, b int) tree {    return tree{        animal: a,        sire:   &tree{animal: s, base: b},        dam:    &tree{animal: d, base: b},        base:   b,    }}for _, animal := range list {    myTree = newTree(animal, pedigree[animal][0], pedigree[animal][1], 0)    walk(myTree, written, fw) // written is a map of integers and fw is io.Writer}func walk(t tree, written map[int]int, writer io.Writer) tree {    style := "%12d%12d%12d\n"    if t.animal == t.base {        return t    }    if t.base == 0 {  // for the first iteration        t.base = t.animal    }    if _, ok := written[t.animal]; !ok {        sire := t.sire.animal        dam := t.dam.animal        if sire == 0 {            sire = t.base        }        if dam == 0 {            dam = t.base        }        written[t.animal] = 0        io.WriteString(writer, fmt.Sprintf(style, t.animal, sire, dam))    }    // Shift forward.    if t.sire.animal > 0 {        myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)        walk(myTree, written, writer)    }我的谱系由大约 1300 万只动物组成，但我无法让功能在正确的点停止并在stack overflow完成几只动物后感到恐慌。我相信我的一些问题是：参与循环的动物是基础动物，所以我应该检查是否animal == base (1->2->3->1)参与循环的动物不是基础动物(1->2->3->4->5->6->3)任何帮助将不胜感激。

Answer 1

由于您的系谱图中可以有循环，因此您可能会陷入这样的循环。这意味着您必须检测循环并停止在那里构建。你可以通过稍微改变你的树来做到这一点。

首先，您tree按值传递对象，但附加指向它的指针。将指针传递给周围的树：

func walk(t *tree, written map[int]int, writer io.Writer) *tree {

}

更好的方法可能是：

func (t *tree) walk(written map[int]int, writer io.Writer) {...}

您还应该将 a 添加*parent到树中，以便检测循环：

type tree struct {

    parent *tree

    sire   *tree

    dam    *tree

    animal int

    base   int

    path   []int

}

每次创建新关卡时，适当设置父级：

myTree := newTree(t.sire.animal, pedigree[t.sire.animal][0], pedigree[t.dam.animal][1], t.base)

myTree.parent=t

myTree.walk(written, writer)

然后添加一个函数来测试你是否进入循环：

func (t *tree) loop(animal int) bool {

   for t!=nil {

       if t.animal==animal {

          return true

       }

       t=t.parent

   }

   return false

}

并检查您是否正在进入循环：

if !myTree.loop(myTree.animal) {

   myTree.walk(written, writer)

}