在golang中扁平化递归数据结构的有效方法

Question

我有一个递归数据结构，它可以包含几种不同类型的数据：

type Data interface{
 // Some methods
}
type Pair struct { // implements Data
  fst Data
  snd Data
}
type Number float64 // implements Data

现在我想把一个Pair链展平成一个[]Data。但是，不应展平fst字段中的Data，只应展平snd中的数据。例如：

chain := Pair{Number(1.0), Pair{Number(2.0), Pair{Number(3.0), nil}}}
chain2 := Pair{Pair{Number(1.0), Number(4.0)}, Pair{Number(2.0), Pair{Number(3.0), nil}}}

变成：

data := []Data{Number(1.0), Number(2.0), Number(3.0)}
data2 := []Data{Pair{Number(1.0), Number(4.0)}, Number(2.0), Number(3.0)}

我天真的方法是：

var data []Data
chain := Pair{Number(1.0), Pair{Number(2.0), Pair{Number(3.0), nil}}}

for chain != nil {
    data = append(data, chain.fst)
    chain = chain.snd
}

有没有一种更有效的方法可以将像变量chain中的数据结构扁平化到[]Data数组中？

Answer 1

您可以使用递归函数。在向下的过程中，在底部添加对的数量，分配数组，在返回的过程中，从后到前填充数组。

如果需要支持任意树，可以向Data添加一个size方法，然后执行另一次树遍历以实际填充数组。

Answer 2

嗯，你的天真方法对嵌套在fst中的Pair不起作用。如果你有chain := Pair{Pair{Number(1.0), Number(2.0)}, Number{3.0}}，它就会变成[]Data{Pair{Number(1.0), Number(2.0)}, Number{3.0}}。这是一个固有的递归问题，所以为什么不这样实现它呢？

我建议在您的接口中添加一个flatten()方法。Pairs可以递归地嵌套自己，而Numbers只是返回它们的值。

下面是一个完整的工作示例，其中包含了一些最少的测试：

package main

import "fmt"

type Data interface {
    flatten() []Data
}

type Pair struct {
    fst Data
    snd Data
}

type Number float64

func (p Pair) flatten() []Data {
    res := []Data{}
    if p.fst != nil {
        res = append(res, p.fst.flatten()...)
    }
    if p.snd != nil {
        res = append(res, p.snd.flatten()...)
    }
    return res
}

func (n Number) flatten() []Data {
    return []Data{n}
}

func main() {
    tests := []Data{
        Pair{Number(1.0), Pair{Number(2.0), Pair{Number(3.0), nil}}},
        Pair{Pair{Number(1.0), Number(2.0)}, Number(3.0)},
        Pair{Pair{Pair{Number(1.0), Number(2.0)}, Pair{Number(3.0), Number(4.0)}}, Pair{Pair{Number(5.0), Number(6.0)}, Number(7.0)}},
        Number(1.0),
    }
    for _, t := range tests {
        fmt.Printf("Original: %v\n", t)
        fmt.Printf("Flattened: %v\n", t.flatten())
    }
}

(这假设顶级输入Data永远不是nil)。

代码打印如下：

Original: {1 {2 {3 <nil>}}}
Flattened: [1 2 3]
Original: {{1 2} 3}
Flattened: [1 2 3]
Original: {{{1 2} {3 4}} {{5 6} 7}}
Flattened: [1 2 3 4 5 6 7]
Original: 1
Flattened: [1]

Answer 3

正如所建议的，编写一个递归函数最适合这个问题。但也可以编写一个非递归版本(IMHO递归版本会更清楚)：

func flatten(d Data) []Data {
    var res []Data

    stack := []Data{d}

    for {
        if len(stack) == 0 {
            break
        }
        switch x := stack[len(stack)-1].(type) {
        case Pair:
            stack[len(stack)-1] = x.snd
            stack = append(stack, x.fst)
        case Number:
            res = append(res, x)
            stack = stack[:len(stack)-1]
        default:
            if x == nil {
                stack = stack[:len(stack)-1]
            } else {
                panic("INVALID TYPE")
            }
        }
    }

    return res
}