2

私はおそらく大きな根付きツリー構造を持っており、それはツリーの葉の量であり、1より大きい次数を持つツリー内のノードの量、つまりルートノードと内部ノードであるX * Y行列に変換したいと考えています。マトリックスは次のように入力する必要があります。XY

M i、j = {0葉iに祖先があるj場合は1、それ以外の場合は1

たとえば、次のツリー：

      --A 
     /
    1   B
   / \ /
  /   3  
 /     \
0       C
 \ 
  \   --D
   \ /
    2
     \--E

このマトリックスに変換されます：

  0 1 2 3
A T T F F
B T T F T
C T T F T
D T F T F
E T F T F

木はかなり大きくなる可能性があるので（おそらく約100,000枚の葉）、葉のノードごとに木を横断するよりも賢くて速い方法があるかどうか疑問に思いました。ある種のアルゴリズムがこの問題のどこかにあるように感じますが、私はまだそれを理解していません。多分誰かが助けることができますか？

私のアプリケーションでは、ツリーは大きな系統発生階層を表しているため、バランスが取れておらず、3つ以上の子を持つノードが存在する可能性があります。

4

1 に答える 1

1

注文後のトラバーサルを使用します。

ツリーをトラバースしている間、葉のリストを維持します。各レベルで、リストにはこのレベルまでのすべての葉が含まれます。

使用する関数のデカレーション：

list merge(list1,list2) //merges two lists and creates a new list
list create() // creates a new empty list
void add(list,e) // appends e to the list
void setParent(leaf,node) //sets (in your matrix) node as a parent of leaf

擬似コード：

list Traverse(root):
  if (root == nil):
      l <- create()
      return l
  else if (root is leaf):
      l <- create()
      add(l,root)
      return l
  else: 
      l1 <- Traverse(root.left)
      l2 <- Traverse(root.right)
      l <- merge(l1,l2)
      for each leaf in l:
          setParent(leaf,root)
      return l

時間はO(n*m)-マトリックスを設定するためのものです（ただし、アルゴリズム自体はO(nlogn)バランスの取れたツリーのための時間です）。

O(n*m)初期化を防ぎたい場合は、で行列を初期化してO(1)から、上記のアルゴリズムをで実行できますO(nlogn)。漸近的な複雑さが増しますが、実際にはもっと速くなるとは思えません。

于 2012-09-05T08:35:32.197 に答える