Golang中关于结构体的递归函数

Question

我有以下代码来组织 *Widget 结构体成为一个层级结构。 Parent() 返回具有调用者父 ID 的小部件。层次结构最多可以深达 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
}

有没有更符合习惯的方法实现这个？

- Bebbs

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
}

此方法将在调用“根”（对于所有切片类型的零值）时返回nil。 在其他情况下，它将返回“路径”，即从直接父级到“根”的路径。

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

结果符合预期：

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上尝试。

- icza