algorithm - 在递归/缩进树数据结构之间转换

Question

以表示一棵树为例:

• 根
  • 一个
    • 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"),
]

根据我想对树做什么，我发现一种或另一种形式更容易处理。

我想知道:

• 您是否会使用众所周知的术语来区分 a) 或 b) 之类的数据结构？ (类似于 recursive 与 flat/indented 树表示？)

• 是否有标准算法可以在这两种形式之间进行转换？

Answer 1

关于命名法，我不知道有任何标准描述，但我会将您的第一个描述为嵌套数据结构；第二个是显示连续缩进的列表。

这是一个 Python 程序:

1. 将第一个嵌套节点定义为名称的二元组，后跟其子项列表(可以是表示叶项的空列表)。
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', [])])

当然，数据结构可以使用命名元组，但我选择不使用。