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

Question

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

我想使用可重用组件来执行此操作，这样我就可以专注于执行任务的实现，而不必为每个此类功能重新实现 walker。到目前为止，我唯一能想到的就是这个 API:

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

函数 walker 显然可以用来修改树，因为它传递了指向树节点的指针。我喜欢它，因为我可以单独编写 applyFunc 函数，而不必费心处理实际的递归 walker 代码。然而，提取节点或删除它们更加困难。

为了从节点中提取信息，也许我可以使用闭包:

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

这是一个好的解决方案吗？还有更好的吗？

Answer 1

您还可以将 walk 函数添加到您的树类型，在节点中添加指向父节点的指针，并向节点添加 deleteChild 方法，该方法将子节点的索引作为参数，这样您就可以轻松操作。

示例(这里我称之为walk apply):

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) // []
}