如何正确将可视化二叉树转换为指定结构的tuple？

我需要将一棵可视化二叉树（见图片）转换为(left_subtree, key, right_subtree)结构的元组（其中左右子树本身也是元组）。我尝试编写了如下代码，但元组结构或树本身存在问题，请教正确的实现方式：

class TreeNode:
    def __init__(self, key):
        self.key = key
        self.left = None
        self.right = None


tree_tuple = (((None, 6, None), 4,2,(9, 7, 10)), 1,
              ((13, 11, 14),8, (15, 12, 16), 5, 3))


print(len(tree_tuple))


def parse_tuple(data):
    if isinstance(data, tuple) and len(data) == 3:
        node = TreeNode(data[1])
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        node = None
    else:
        node = TreeNode(data)
    return node


tree = parse_tuple(tree_tuple)

print(tree.right.right.left.right.key)

问题分析 #

你的parse_tuple函数逻辑是正确的，它只处理长度为3的元组（对应完整节点）、None（空节点）或单个值（叶子节点）。但你定义的tree_tuple结构完全不符合(左子树, 键, 右子树)的嵌套规则：

• 左子树部分((None, 6, None), 4,2,(9, 7, 10))长度为4，不是三元组
• 右子树部分((13, 11, 14),8, (15, 12, 16), 5, 3)长度为5，同样不符合要求

正确实现方式 #

每个节点必须严格对应(左子树, 节点值, 右子树)的三元组，空节点用None填充。假设你的可视化二叉树结构对应以下逻辑：

• 根节点为1，左孩子是4，右孩子是3
• 节点4的左孩子是6（无左右子节点），右孩子是2；节点2的右孩子是7，7的左是9、右是10
• 节点3的左孩子是5；节点5的左孩子是8，8的左是11（左13、右14），8的右是12（左15、右16）

对应的正确元组结构如下：

# 严格按(左子树, 键, 右子树)嵌套的三元组
tree_tuple = (
    ((None, 6, None), 4, (None, 2, ((None, 9, None), 7, (None, 10, None)))),
    1,
    (((((None, 13, None), 11, (None, 14, None)), 8, ((None, 15, None), 12, (None, 16, None))), 5, None), 3, None)
)

替换后运行你的代码，print(tree.right.right.left.right.key)会输出16（对应节点12的右子节点），符合预期。

内容的提问来源于stack exchange，提问作者rezaatb