二叉树中的叶子数 Python

Question

我有一个看起来像这样的数据结构 Q = (A,(B,C))。 Len(Q) 显然等于 2。但我只关心叶子 (A, B, C)。我可以使用什么函数 return function(Q) = 3?

Answer 1

def count_nodes(tree):
    if not tree:
        return 0
    elif type(tree) == str:
        return 1
    else:
        return count_nodes(tree[0]) + count_nodes(tree[1:])


tree = ('a', ('b', ('d', 'e'), 'c', ('f', 'g')))
print count_nodes(tree) # prints 7

也就是说，如果您真正想要的是树叶（在您的示例中：(B,C)），您可以将其转换为字符串，使用正则表达式，然后还原：

import re

tree = ('a', ('b', ('d', 'e'), 'c', ('f', 'g')))
res = re.findall(r'\([^(]+?\)', str(tree))
res = map(eval, res)
print res # [('d', 'e'), ('f', 'g')]

Answer 2

你可以使用递归函数：

def rec_len(thing):
    if isinstance(thing, basestring):
        return 1
    try: 
        return sum(rec_len(x) for x in thing)
    except TypeError:
        return 1

请注意，您必须提防 'string-like' 的内容，否则您最终会计算叶节点的字母。

Answer 3

def flatten(container):
    for i in container:
        if isinstance(i, list) or isinstance(i, tuple):
            for j in flatten(i):
               yield j
        else:
            yield i

sum(1 for _ in flatten(Q))

Answer 4

def flatten(q):
    if not q:
        return 0
    if isinstance(q, tuple):
        if not isinstance(q[0], tuple):
            return 1+flatten(q[1:])
        else:
            return flatten(q[0]) + flatten(q[1:])
    else:
        return 1

二叉树中的叶子数 Python

Number of Leaves in a Binary Tree Python

python

binary-tree