二叉树递归插入方法定位正确节点但未保存数据，是否为引用问题？

你的判断方向是对的，问题出在变量赋值的作用域和树节点的关联逻辑上，并非传统意义的"引用错误"，但本质是没有正确将新节点挂载到二叉树的父节点上。

原代码的核心问题 #

1. 局部变量无法影响上层节点：当node is None时，你创建了TreeNode(data)但仅赋值给局部变量node，这个变量只在当前递归栈帧中有效，不会传递到上层的父节点，导致新节点根本没被添加到树里。
2. 递归调用未修改父节点指针：执行node = node.left后调用in_insert(node, data)，这里修改的是局部变量node，而非原父节点的left属性。相当于你只是把父节点左子节点的引用复制了一份，修改这份副本不会改变原树的结构。

修正后的代码 #

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

class BTree():
    def __init__(self, root=None):
        self.root = root

    def insert(self, data):
        def in_insert(node, data):
            # 空节点时返回新创建的节点，让上层父节点接收并挂载
            if node is None:
                return TreeNode(data)
            elif node.data == data:
                print(f'{node.data} already in here.')
                return node  # 重复数据，返回原节点
            elif node.data > data:
                # 将递归结果赋值给当前节点的left，确保新节点被挂载
                node.left = in_insert(node.left, data)
                return node
            else:
                # 同理处理右子树
                node.right = in_insert(node.right, data)
                return node

        if self.root is None:
            self.root = TreeNode(data)
        else:
            self.root = in_insert(self.root, data)

修正逻辑说明 #

• 让递归函数in_insert返回处理后的节点，这样每次递归调用时，父节点可以把返回值赋值给自己的left或right属性，确保新节点被正确关联到树结构中。
• 遇到重复数据时返回原节点，避免破坏现有树结构。
• 根节点的更新也通过递归函数的返回值处理，保持代码逻辑的一致性。

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