Пользовательская логика перемещения для дерева

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 для каждого объекта.

, поэтому следующий объект должен быть

напитки -> холодные -> молоко -> сода -> горький лимон-> имбирный эль

и после этого он должен перейти на

hot

и т. д ...

Я не совсем уверен, что мой код делает это правильно, он только помечает до первого листа и после этого nextObject становится nil

Спасибо за помощь.

Answer 1

Похоже, что вы уже строите дерево, поэтому включение его в список должно быть довольно простым.Основываясь на вашем изображении, похоже, что вы хотите получить массив, используя предварительный обход .Сначала я добавлю метод заполнения к Node

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

Затем в getRootsFrom изменим возвращаемое значение на

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

Статья Википедии о обходе дерева - отличный источник, чтобы прочитать об этом.Он показывает различные упорядочения с изображениями и псевдокодом.