Преобразование между рекурсивной / отступовой структурой данных дерева

Question

Для представления дерева, например:

• root
  • a
    • a.1
    • a.2
  • b

a, можно использовать следующую структуру данных:

struct TreeNode {
    var name: String
    var children: [TreeNode] = []
}

var rootNode =
    TreeNode(name: "root", children: [
        TreeNode(name: "a", children: [
            TreeNode(name: "a.1"),
            TreeNode(name: "a.2"),
        ]),
        TreeNode(name: "b"),
    ])

b, альтернативно упорядоченный список сможно использовать атрибут для отступа:

struct FlatTreeNode {
    var indent: Int
    var name: String
}

var tree = [
    FlatTreeNode(indent: 0, name: "root"),
    FlatTreeNode(indent: 1, name: "a"),
    FlatTreeNode(indent: 2, name: "a.1"),
    FlatTreeNode(indent: 2, name: "a.2"),
    FlatTreeNode(indent: 1, name: "b"),
]

В зависимости от того, что я хочу сделать с деревом, я обнаружил, что с одной или другой формой проще работать.

Мне было интересно:

• Существуют ли общеизвестные термины, которые вы бы использовали для разграничения структуры данных, такой как а) или б)? (что-то вроде recursive против flat/indented представление дерева?)

• Существует ли стандартный алгоритм для преобразования между этими двумя формами?

Answer 1

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

Вот программа на Python, которая:

1. Определяет первый как вложенный узел как 2 кортежа имени, за которым следует список его дочерних элементов (который может быть пустым списком, обозначающим конечные элементы).
2. Второй формат представляет собой список из двух кортежей, первый элемент которых имеет отступ, второй элемент - имя.

Программаконвертирует в обоих направлениях и сравнивает, чтобы показать, что вы можете в обоих направлениях конвертировать.

from pprint import pprint as pp

def to_list(node, depth=0, flat=None):
    if flat is None:
        flat = []
    if node:
        flat.append((depth, node[0]))
    for child in node[1]:
        to_list(child, depth + 1, flat)
    return flat

def to_nest(lst, depth=0, level=None):
    if level is None:
        level = []
    while lst:
        d, name = lst[0]
        if d == depth:
            children = []
            level.append((name, children))
            lst.pop(0)
        elif d > depth:  # down
            to_nest(lst, d, children)
        elif d < depth:  # up
            return
    return level[0] if level else None

if __name__ == '__main__':
    print('Start Nest format:')
    nest = ('root', [('a', [('a.1', []), ('a.2', [])]), ('b', [])])
    pp(nest, width=20)

    print('\n... To List format:')
    as_list = to_list(nest)
    pp(as_list, width=20)

    print('\n... To Nest format:')
    as_nest = to_nest(as_list)
    pp(as_nest, width=20)

    assert nest == as_nest

Вывод:

Start Nest format:
('root',
 [('a',
   [('a.1', []),
    ('a.2', [])]),
  ('b', [])])

... To List format:
[(0, 'root'),
 (1, 'a'),
 (2, 'a.1'),
 (2, 'a.2'),
 (1, 'b')]

... To Nest format:
('root',
 [('a',
   [('a.1', []),
    ('a.2', [])]),
  ('b', [])])

Конечно, структуры данных могут использовать namedtuples, но я не хочу.

Answer 2

Версия Swift flatten + unflatten:

import Foundation

public struct TreeNode<T: Equatable>: Equatable {
    var content: T
    var children: [TreeNode] = []
}

public struct IndentedTreeNode<T: Equatable>: Equatable {
    var indent: Int
    var content: T
}

public func flatten<T>(_ node: TreeNode<T>, indent: Int = 0) -> [IndentedTreeNode<T>] {
    [IndentedTreeNode(indent: indent, content: node.content)] + node.children.flatMap { flatten($0, indent: indent + 1) }
}

public func unflatten<T>(_ list: [IndentedTreeNode<T>]) -> TreeNode<T>? {
    guard let firstNode = list.first?.content else { return nil }
    let remainingNodes = list.dropFirst()

    var root = TreeNode(content: firstNode)
    var lastNodePath = IndexPath()

    for node in remainingNodes {
        let pathToNodeParent = lastNodePath.prefix(max(node.indent, 1) - 1)
        var children = root[pathToNodeParent].children
        children.append(TreeNode(content: node.content))
        root[pathToNodeParent].children = children
        lastNodePath = pathToNodeParent.appending(children.indices.last!)
    }

    return root
}

public extension TreeNode {

    subscript(indexPath: IndexPath) -> TreeNode {
        get {
            if indexPath.isEmpty {
                return self
            } else {
                return self.children[indexPath.first!][indexPath.dropFirst()]
            }
        }
        set {
            if indexPath.isEmpty {
                self = newValue
            } else {
                self.children[indexPath.first!][indexPath.dropFirst()] = newValue
            }
        }
    }

}

Пакет Swift с юнит-тестами: https://github.com/ralfebert/IndentedTree

Answer 3

В псевдокоде это должно сработать:

// Arguments flatTree and index mussed be passed by ref
Flatten(node, flatTree, index = 0, indent = 0){
    flatTree[index] = FlatTreeNode(node, indent)
    index += 1
    for child of node {
        Flatten(child, flatTree, index, indent+1)
    }
}

// Arguments flatTree and index mussed be passed by ref
Unflatten(flatTree, index = 0){
    indt = Indent(flatTree[index])
    node = TreeNode(flatTree[index])
    index += 1
    while index < len(flatTree) and Indent(flatTree[index]) > indt {
        child = Unflatten(flatTree, index)
        AddChild(node, child)
    }
    return node
}