遍历树并使用可重用组件提取信息

Question

我在Go项目中有一个嵌套结构树。我想穿过树并执行不同的操作，例如在树中的不同级别挑选某些结构并将它们附加到列表中，或者修改结构。

我想使用可重用组件来做到这一点，这样我就可以专注于实现执行任务，而不必为每个此类功能重新实现Walker。到目前为止，我能想到的唯一的事情是这样的API：因为它是通过指针指向树节点

type applyFunc func(*Node) 
func walker(node *Node, f applyFunc) { 
    .... 
    for _, child := range node.children() { 
     walker(child, f) 
    } 
} 

功能walker可以清楚地用于修改树。我喜欢它，因为我可以单独编写applyFunc函数，而不必担心实际的递归漫游器代码。但是，提取节点或删除它们更困难。

对于提取节点的信息，也许我可以用一个封闭：

values := &[]int{} 
f := func(node *Node) { 
    values.append(node.val) 
} 
walker(root, f) 
//values now hold the information I am interested in 

这会是一个很好的解决方案呢？有更好的吗？

Answer 1

您还可以将漫游功能添加到您的树型，在节点中添加指向父节点的指针，并将deleteChild方法添加到将子节点的索引作为参数的节点，以便您轻松操作。

例（在这里，我叫步行适用）：

type node struct { 
    children []*node 
    parent *node 
    value int 
} 

func (n *node) deleteChild(index int) { 
    n.children = append(n.children[:index], n.children[index+1:]...) 
} 

func (n *node) delete(index int) { 
    if n.parent != nil { 
     n.parent.deleteChild(index) 
    } 
} 

func (n *node) apply(index int, f func(int, *node)) { 
    f(index, n) 
    for childIndex, child := range n.children { 
     child.apply(childIndex, f) 
    } 
} 

func main() { 
    t := &node{} 
    t.children = []*node{ 
     &node{ 
      children: []*node{ 
       &node{value: 2}, 
      }, 
      value: 1, 
      parent: t, 
     }, 
    } 

    // extract all values in nodes 
    values := []int{} 
    t.apply(0, func(index int, n *node) { 
     values = append(values, n.value) 
    }) 
    fmt.Println(values) // [0 1 2] 

    // delete a node 
    fmt.Println(t.children) // [0xc4.....] 
    t.apply(0, func(index int, n *node) { 
     n.delete(index) 
    }) 
    fmt.Println(t.children) // [] 
}