swift - 树的自定义遍历逻辑

Question

我有一个平面列表，我用这段代码将其转换为树

class Node {
    var Children: [Node] = []
    weak var parent: Node?
    weak var nextObject: Node?
    var associatedObject: AppListItem?

    init(associatedObject: AppListItem) {
        self.associatedObject = associatedObject
    }
}

func getRootsFrom(list: [AppListItem]) -> [Node] {
    var dict: [String : Node] = [:]
    list.forEach { (appItem) in
        dict[appItem.uuid] = Node(associatedObject: appItem)
    }
    dict.values.forEach { (node) in
        var proposedParent: Node
        if let value = dict[node.associatedObject?.parentUUID ?? ""] {
            proposedParent = value
            node.parent = proposedParent
            proposedParent.Children.append(node)
            proposedParent.Children.sort(by: {$0.associatedObject?.sort ?? "" < $1.associatedObject?.sort ?? ""})
            proposedParent.nextObject = proposedParent.Children.first
        }
    }
    return dict.values.filter({$0.parent == nil}).sorted(by: {$0.associatedObject?.sort ?? "" < $1.associatedObject?.sort ?? ""})
}

其中 getRootsFrom 将列表转换为树，并返回根，我在为每个对象正确标记 nextObject 时遇到了问题。

所以下一个对象应该是

beverages -> cold -> milk -> soda -> bitter lemon -> ginger ale

然后它应该去

hot

等等...

我不太确定我的代码是否正确执行，它唯一的标记是直到第一片叶子，然后 nextObject 变为 nil

感谢您的帮助。

Answer 1

看起来您已经在构建树，因此将其放入列表应该相当简单。根据您的图片，您似乎想要使用 pre order traversal 获取数组.首先，我将填充方法添加到 Node

func preorder() -> [Node] {
    return [self] + Children.flatMap { $0.preorder() }
}

然后在getRootsFrom中将return改成

return dict.values.first(where: {$0.parent == nil})?.preorder() ?? []

wikipedia article on tree traversal是阅读它的重要资源。它用图像和伪代码显示了不同的顺序。