Python二叉树递归构建报错AttributeError，请求代码修正

问题背景 #

我刚学会创建平衡二叉树并访问节点，比如用元组data = ((1,3,None),2,((None,3,4),5,(6,7,8)))表示树结构。手动创建节点并关联的方式效率极低且代码冗长，手动实现代码如下：

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

# 创建节点
node_0 = tree(2)
node_1 = tree(3)
node_2 = tree(5)
node_3 = tree(1)
node_4 = tree(3)
node_5 = tree(7)
node_6 = tree(4)
node_7 = tree(6)
node_8 = tree(8)

# 关联节点
node_0.left = node_1
node_0.right = node_2
node_0.left.left = node_3
node_0.right.left = node_4
node_0.right.right = node_5
node_0.right.left.left = node_6
node_0.right.right.left = node_7
node_0.right.right.right = node_8

# 访问节点
print(node_0.right.right.right.key)  # 输出8

于是我尝试写了一个递归函数parse_tuple来解析元组自动构建树，但运行时触发了AttributeError: 'int' object has no attribute 'left'错误，我的递归代码如下：

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

报错详情如下：

18:10:41.43 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
18:10:41.43 ...... data = ((1, 3, None), 2, ((None, 3, 4), 5, (6, 7, 8)))
18:10:41.43 ...... len(data) = 3
18:10:41.43    4 | def parse_tuple(data):
18:10:41.43    6 |     if isinstance(data,tuple) and len(data)==3:
18:10:41.43    7 |         node = (data[1])
18:10:41.43 .............. node = 2
18:10:41.43    8 |         node.left = parse_tuple(data[0])
    18:10:41.44 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
    18:10:41.44 ...... data = (1, 3, None)
    18:10:41.44 ...... len(data) = 3
    18:10:41.44    4 | def parse_tuple(data):
    18:10:41.44    6 |     if isinstance(data,tuple) and len(data)==3:
    18:10:41.44    7 |         node = (data[1])
    18:10:41.44 .............. node = 3
    18:10:41.44    8 |         node.left = parse_tuple(data[0])
        18:10:41.44 >>> Call to parse_tuple in File "C:\Users\muzza\AppData\Local\Temp\ipykernel_17864\3153403204.py", line 4
        18:10:41.44 ...... data = 1
        18:10:41.44    4 | def parse_tuple(data):
        18:10:41.44    6 |     if isinstance(data,tuple) and len(data)==3:
        18:10:41.44   10 |     elif data is None:
        18:10:41.45   13 |         node=(data)
        18:10:41.45 .............. node = 1
        18:10:41.45   14 |     return node
        18:10:41.45 <<< Return value from parse_tuple: 1
    18:10:41.45    8 |         node.left = parse_tuple(data[0])
    18:10:41.46 !!! AttributeError: 'int' object has no attribute 'left'
    18:10:41.46 !!! When getting attribute: node.left
    18:10:41.46 !!! Call ended by exception
18:10:41.46    8 |         node.left = parse_tuple(data[0])
18:10:41.47 !!! AttributeError: 'int' object has no attribute 'left'
18:10:41.47 !!! When calling: parse_tuple(data[0])
18:10:41.47 !!! Call ended by exception

我尝试修复但没思路，希望修正这段代码，明确错误原因，实现和手动创建相同的节点访问效果。

错误原因 #

核心问题是没有创建tree类的实例，直接把数值赋值给了node：

• 处理三元组时，node = data[1]得到的是整数（比如2、3），而非tree类对象，整数类型没有left和right属性，赋值时触发AttributeError。
• 递归到叶子节点时，直接返回数值（比如1），正确做法应返回tree实例或None。

修正后的代码 #

修改递归函数，确保所有节点都是tree类的实例：

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

def parse_tuple(data):
    # 处理三元组：(左子树, 根节点, 右子树)
    if isinstance(data, tuple) and len(data) == 3:
        # 创建根节点实例
        node = tree(data[1])
        # 递归解析左右子树
        node.left = parse_tuple(data[0])
        node.right = parse_tuple(data[2])
    elif data is None:
        # 空节点返回None
        node = None
    else:
        # 叶子节点：直接创建tree实例
        node = tree(data)
    return node

验证效果 #

调用修正后的函数，即可实现和手动创建完全一致的节点访问：

data = ((1,3,None),2,((None,3,4),5,(6,7,8)))
root = parse_tuple(data)

# 访问节点，和手动创建的结果一致
print(root.right.right.right.key)  # 输出8
print(root.left.left.key)          # 输出1
print(root.right.left.left.key)    # 输出4

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