遍历树并提取具有可重用组件的信息

Question

I have a tree of nested structs in a Go project. I would like to walk through the tree and perform different actions, such as picking out certain structs at different levels in the tree and appending them to a list, or modifying the structs in place.

I would like to do this using reusable components so that I can focus on implementing that perform the tasks, not having to reimplement the walker for every such function. So far the only thing I can think of is this API:

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

The function walker can clearly be used to modify the tree because it is passed pointers to the tree nodes. I like it because I can write applyFunc functions separately without having to bother with the actual recursive walker code. However, extracting nodes or deleting them is more difficult.

For extracting information from nodes, perhaps I can use a closure:

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

Would this be a good solution? Are there better ones?

Answer 1

You could also add the walk function to your tree type, add a pointer to the parent in a node and add a deleteChild method to a node which takes the index of the child as argument which would allow you to manipulate easily.

Example (here i called 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) // []
}