此功能代表什么数据结构？

Question

我具有以下功能，但我不确定他们是否正在实现二叉树，即B树。

这里是代码：

def foo(x):
    if x:
        a, b, c = x
        return foo(a) + b + foo(c)
    else:
        return 0

有人可以帮我弄清楚正在使用的数据结构吗？

Answer 1

那是确实一棵二叉树，但是对于某些人（通常是那些更喜欢指针的人）来说，是一个相当奇怪的实现。树的每个节点都是一个三元组：

• 整个左子树为三元组，如果没有子树，则为假类型值；
• 此节点的值；和
• 整个右子树三元组或假类型值。

您的foo函数实际上是总结所有节点，尽管我会做一些小改动：

def sum_tree(tpl):
    if tpl:
        return foo(tpl[0]) + tpl[1] + foo(tpl[2])
    return 0

# Construct tree for testing:
#          __42__          (42)
#         /      \
#        7        5        (12)
#       / \      /
#     12   17   3          (32)
#                          ----
#                          (86)

tree = [[[None, 12, [None, 7, None]], 17, None], 42, [[None, 3, None], 5, None]]
print(foo(tree)) # Output is `86`.