http://pt.stackoverflow.com/questions/118024/como-calcular-o-percentual-de-itens-realizados-em-uma-%C3%A1rvore-de-dados-no-formato

percentual_arvore_resolvida.py

arvore = [
    [0, False],
    [1, True],
    [1, False],
    [2, False],
    [2, True],
    [2, False],
    [3, False],
    [3, True],
    [2, False],
    [1, False],
    [2, False]
]

def resolver1(arvore):
    NIVEL = 0
    VALOR = 1
    PESO = 2
    arvore = map(lambda (n, v): [n, v * 100., 1.], arvore)
    p = len(arvore) - 1
    print p, arvore
    while p:
        if arvore[p][NIVEL] > arvore[p - 1][NIVEL]:
            arvore[p - 1][VALOR] = arvore[p][VALOR]
        elif arvore[p][NIVEL] == arvore[p - 1][NIVEL]:
            arvore[p - 1][PESO] = arvore[p][PESO] + 1
            arvore[p - 1][VALOR] = ((arvore[p][VALOR] * arvore[p][PESO]
                                     + arvore[p - 1][VALOR]) /
                                    arvore[p - 1][PESO])
        else:
            p -= 1
            continue
        del arvore[p]
        if p == len(arvore):
            p -= 1
        print p, arvore
    return arvore[0][VALOR]

def resolver2(arvore):
    arvore = map(lambda (n, v): [n, v * 100.], arvore)
    print arvore
    while len(arvore) > 1:
        niveis, valores = zip(*arvore)
        nivel_maior = max(niveis)
        inicial = niveis.index(nivel_maior)
        final = inicial + 1
        while final < len(niveis) and niveis[final] == nivel_maior:
            final += 1
        arvore[inicial - 1][1] = sum(valores[inicial:final]) / (final - inicial)
        del arvore[inicial:final]
        print arvore
    return arvore[0][1]

print "\nResolvido 1: %.2f%%\n" % resolver1(arvore)
print "\nResolvido 2: %.2f%%\n" % resolver2(arvore)