algorithm - 如何快速获得树上所有叶子的所有 parent ？

Question

我有一个可能很大的有根树结构，我想将其转换为 X * Y 矩阵，其中 X 是树中叶子的数量， Y 是树中度数大于 1 的节点数，即根节点和内部节点。矩阵应该这样填写:

M_i,j = { 0 如果叶子 i 有祖先 j，否则为 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 片叶子)，我想知道是否有比遍历树上的每个叶节点更聪明/更快的方法。感觉这个问题的某个地方有某种算法，但我还没有弄清楚。也许有人可以提供帮助？

在我的应用程序中，树代表大 phylogenetic hierarchies , 所以它是不平衡的，可能有节点有两个以上的 child 。

Answer 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) 初始化你可以initialize the matrix in O(1) ，然后在 O(nlogn) 中运行上面的算法。虽然它会提供更好的渐近复杂性，但我怀疑它实际上会更快。