1

木を表す数値文字列があります (これに正式な名前があるかどうかはわかりません)。

012323301212

上記の例は、2 つのツリーを表しています。ルートは 0 で示されます。ルートの直下の子は「1」、「1」の直下の子は「2」などです。これらを、親とその直接の子で構成されるサブツリーにグループ化する必要があります。したがって、上記は次のように分解されます...

01 122 23 233 011 12 12

これを行う1つの可能な方法は、文字列からツリー構造を構築し、各ノードにアクセスして、そのサブツリーとその直下の子 (存在する場合) を生成することだと考えていましたが、これは比較的複雑に思えます。ツリー構造を作成してトラバースすることなく、これを行うことができる賢い方法はありますか?

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 に答える