Golang中结构的递归函数

Question

我有以下代码将 *Widget 结构组织成层次结构。 Parent() 返回 ID 为调用者 parentID 的小部件。层次结构最多可达 4 或 5 层。

type Widget struct {
  ID int64
  ParentID int64
}

func (w *Widget) Parent() *Widget {
  // Returns the widget with an ID of w.ParentID
}

我想要实现的是一个函数，它将父级以及父级的父级等聚合到层次结构的顶部，并返回所有父级 ID 的一部分。由于我不知道层次结构的深度，我认为我需要某种编程递归来获取每个父级的父级，这将执行如下操作:

func (w *Widget) AllParents() []*Widget {
  var parentWidgets []*Widget
  x := w.Parent()
  parentWidgets = append(parentWidgets, x)
  y := x.Parent()
  parentWidgets = append(parentWidgets, y)
  ...
  return parentWidgets
}

是否有更惯用的方法来实现这一点？

Answer 1

您只需要在层次结构中越走越高，直到到达根部。假设 Widget.Parent() 返回 nil 如果 Widget 是“根”(意味着它没有父级):

迭代解决方案

下面是一个简单的 for 循环的解决方案:

func (w *Widget) AllParents() []*Widget {
    var ws []*Widget
    for parent := w.Parent(); parent != nil; parent = parent.Parent() {
        ws = append(ws, parent)
    }
    return ws
}

如果在“根”(zero value 用于所有 slice 类型)上调用，此方法将返回 nil。在其他情况下，它将返回“路径”从直接父级通向“根”。

这是一个小测试程序。它创建了一个 ID = 0 的根小部件、一个 ID = 1 的子部件和一个 ID = 2 的“孙子”，并打印 AllParents() 分别调用。为了实现 Widget.Parent()，我使用了一个简单的“widget registry”映射。

结果符合预期:

Parents of 0:
Parents of 1: 0
Parents of 2: 1 0

在 Go Playground 上试试.

var wreg = map[int64]*Widget{}

func (w *Widget) Parent() *Widget {
    // Returns the widget with an ID of w.ParentID
    return wreg[w.ParentID]
}

func main() {
    w := &Widget{0, -1}
    wreg[w.ID] = w
    w2 := &Widget{1, 0}
    wreg[w2.ID] = w2
    w3 := &Widget{2, 1}
    wreg[w3.ID] = w3

    printParents(w)
    printParents(w2)
    printParents(w3)
}

func printParents(w *Widget) {
    fmt.Printf("Parents of %d:", w.ID)
    for _, w := range w.AllParents() {
        fmt.Print(" ", w.ID)
    }
    fmt.Println()
}

递归求解

当然也可以用递归来解决:

func (w *Widget) AllParents() []*Widget {
    if parent := w.Parent(); parent == nil {
        return nil
    } else {
        return append(parent.AllParents(), parent)
    }
}

此解决方案返回“路径”从根目录到直接父目录。

用这个实现运行上面的测试程序，输出是:

Parents of 0:
Parents of 1: 0
Parents of 2: 0 1

在 Go Playground 上试试这个.