这个函数代表什么数据结构？

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(sum_tree(tree)) # Output is `86`.

这个函数代表什么数据结构？

What data structure does this function represent?

python

binary-tree

b-tree