c++ - 获取用数字字符串表示的树中的所有直接父/子

Question

我有代表树的数字字符串(我不知道是否有官方名称):

012323301212

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

01 122 23 233 011 12 12

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

Answer 1

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

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])