algorithm - 在 Go 中将 map 转换为树

Question

我有一个非常具体的问题，我找不到解决方案。

我有一个 map[string]Metric，我想将它转换成树以便在前端使用。 Metric 接口(interface)看起来有一个 Path() 和一个 Name() 方法，name 方法返回以句号分隔的路径的最后一部分(因此“my.awesome.metric”的路径将意味着该指标的名称为“metric”) 树应按路径排序，并应包含 IndexNode。这个结构看起来像这样:

type IndexNode struct {
    Name string
    Path string
    Children []*IndexNode
}

所以像这样的 map :

{
    my.awesome.metric.downloads
    my.awesome.othermetric.downloads
    my.awesome.othermetric.uploads
    my.other.cool.metric
}

应该会导致像这样的树:(对粗糙的 ascii 艺术感到抱歉)

     +-- other -- cool -- metric
     |
my --+             +-- metric -- downloads
     |             |
     +-- awesome --+                 +-- downloads
                   |                 |
                   +-- othermetric --+
                                     |
                                     +-- uploads

请注意，我只有一个根节点(在本例中为我的)。树内部的顺序对我来说并不重要。

我尽了最大努力，还是想不通……在大量谷歌搜索之后(只向我展示了如何创建二叉搜索树和 GoDS 库)，我辞职并决定在这里问我的第一个问题😊

感谢您的帮助!

Answer 1

将 Children 更改为 map[string]*IndexNode，您就完成了一半。如果你不介意查找东西会慢很多，你可以使用 slice ，但这意味着你需要在每次遍历树时搜索 slice 以找到你想要的 child 。在这种情况下， map 更快更容易。

现在您只需要编写一个递归函数沿着树向下移动，根据需要为路径中的每个元素创建节点，直到它到达终点。

不幸的是我没有准备好访问示例，我的所有代码都在我的另一台计算机上:(

一个简单粗暴的例子:

type Tree struct {
    Parent *Tree
    Children map[string]*Tree
    Payload bool // Your data here
}

func NewTree(parent *Tree, path []string, payload bool) *Tree {
    if parent == nil {
        parent = &Tree{nil, map[string]*Tree{}, false}
    }
    if len(path) == 0 {
        parent.Payload = payload
        return parent
    }

    child := parent.Children[path[0]]
    if child == nil {
        child = &Tree{parent, map[string]*Tree{}, false}
        parent.Children[path[0]] = child
    }
    return NewTree(child, path[1:], payload)
}

用法:

root := NewTree(nil, nil, false)
newnode := NewTree(root, []string{"A", "B", "C"}, true)

Try it on the Go Playground!