algorithm - python ete2二叉树获取后代值的总和

Question

我有 ab*二叉树* 其中只有叶子有字符串值(a,b,c,d,e) 我想 c*连接这些叶子的值并将其传递给它们的祖先*

        0
     /     \
    2      3
   / \    / \
  1   a  d   e
 / \
b   c

例如。

1->value=bc 2->value=abc  3->value=de  

在 python ete2 树类中执行此操作的最佳方法是什么

提前致谢

Answer 1

一个非常标准的程序是使用后序迭代。此外，ETE还实现了 get_cached_content 函数，它为这种类型的计算提供了一点便利。

from ete2 import Tree
t = Tree("(((b,c), a), (d,e));")

print "Method 1: caching node content"
internal_node_content = t.get_cached_content(store_attr="name")
for node, content in internal_node_content.iteritems():
    if not node.is_leaf():
        print node, "\nConcat:", ''.join(content)


print "Method 2: post order iteration"
node2concat = {}
for node in t.traverse("postorder"):
    if not node.is_leaf():
        concat = ''.join([node2concat[ch] for ch in node.children])
        node2concat[node] = concat
        print node, "\nConcat:", concat
    else:
        node2concat[node] = node.name


#Method 1: caching node content
# 
#         /-b
#      /-|
#   /-|   \-c
#  |  |
#--|   \-a
#  |
#  |   /-d
#   \-|
#      \-e 
#Concat: acbed
# 
#   /-b
#--|
#   \-c 
#Concat: cb
# 
#      /-b
#   /-|
#--|   \-c
#  |
#   \-a 
#Concat: acb
# 
#   /-d
#--|
#   \-e 
#Concat: ed
#Method 2: post order iteration
# 
#   /-b
#--|
#   \-c 
#Concat: bc
# 
#      /-b
#   /-|
#--|   \-c
#  |
#   \-a 
#Concat: bca
# 
#   /-d
#--|
#   \-e 
#Concat: de
# 
#         /-b
#      /-|
#   /-|   \-c
#  |  |
#--|   \-a
#  |
#  |   /-d
#   \-|
#      \-e 
#Concat: bcade