遍歷樹並使用可重用組件提取信息

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