1

我有代表树的数字字符串（我不知道是否有正式名称）：

012323301212

上面的示例代表 2 棵树。根用 0 表示。根的直接子代是“1”，“1”的直接子代是“2”，以此类推。我需要将这些分组到由父母及其直系子女组成的子树中。所以上面的内容会被分解成...

01 122 23 233 011 12 12

我在想一种可能的方法是从字符串构建一个树结构，然后访问每个节点并生成它的子树及其直接子树（如果有的话），但这似乎相对复杂。有没有一些聪明的方法可以做到这一点，而无需创建树结构并遍历它？

4

1 回答 1

0

您请求的输出本质上是树结构。也就是说，您可以将您的输入视为预先排序的深度优先遍历并读取树结构，而无需一次将其全部保存在内存中：

depths = [0, 1, 2, 3, 2, 3, 3, 0, 1, 2, 1, 2]   # Our input

next_id = 0                                 # Id of the next node
ids = []                                    # The ids of nodes as we traverse
parents = {}                                # Maps children to parents
children = {}                               # Maps parents to lists of children

for depth in depths
  # First we give this node an id
  id = next_id
  next_id += 1

  if ids.length <= depth
    # If this is our first time to this depth, push a new level onto ids.
    ids.append(id)
  else
    # Otherwise just insert the id into the list at its depth
    ids[depth] = id

    # And truncate off all elements after.  This preserves the invariant
    # that each id is the descendent of ids that appears before it.
    ids[depth].resize(depth + 1)

  assert(ids.length == depth + 1)

  # Emit the link between this node and its parent
  if depth > 0
    parents[ids[depth]] = ids[depth - 1]
    children[ids[depth - 1]] ||= []       # add the empty list first if needed
    children[ids[depth - 1]].append(ids[depth])
于 2012-07-14T23:18:43.197 回答