2

我有一棵树，我想遍历所有节点给它们一个值（score）：

  • leaves nodes:该值是通过基于节点本身及其姐妹的属性进行计算来给出的（只能在叶子节点上进行计算）
  • non leaf nodes:他们从孩子那里获取分数，即比较叶子的孩子的分数并获得最高的分数，例如，我可以计算出树的遍历，但我有点不知道如何根据前面列出的条件影响分数。

输入树：

((((a:1,((b:1,c:1)d:1,e:1)f:1)g:1,h:1,i:1)j:1,(k:1,l:1)m:1,(n:1,o:1,p:1)q:1)r:1)root;

遍历代码：

def trav_tree(n): 
       
    if not n.is_leaf():
        trav_tree(n.get_children()[0])
    sisters=[]
    sisters=n.get_sisters()
    print n.name,
    for sis in sisters:
        if not sis.is_leaf():
            trav_tree(sis.get_children()[0])
        print sis.name,

    n=t.get_tree_root() 
    trav_tree(n)

输出：

a b c d e f g h i j k l m n o p q r root

我应该做的是计算当我到达a时，我让我一直下去直到离开的姐妹，计算b和c的分数，而不是我取最高分给d，然后我可以计算a的分数和很快 ...

解决这个问题的最佳方法是什么？
ps：我正在研究用于树数据结构的python ete2

提前谢谢了

4

1 回答 1

0

只需添加一个属性字段来表示每个非叶节点的子节点的最高分数。

然后执行根后遍历。

于 2013-08-09T03:09:24.287 回答