Python递归遍历二叉搜索树存为JSON仅返回首层节点问题

问题背景 #

开发二叉搜索树遍历逻辑时，目标是将树结构转换为字典类型，支持直接序列化为JSON格式，完整保留树的层级关系。已通过自定义insert方法完成所有测试节点插入，代码运行后返回结果仅包含首层节点，无法获取完整深层子树结构。

问题复现代码 #

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

def __str__(self):
    return str(self.data)

class BinarySearchTree:
    def __init__(self):
        self.root = None

# Return the BST object in dictionary format
def __str__(self):
    return str(self.__dict__)

def traverse(self, current_node):
    tree = {'root': current_node.data}
    print(tree)
    if current_node.left is not None:
        tree.update({'left': current_node.left.data})
        print(tree)
        self.traverse(current_node.left)
    if current_node.right is not None:
        tree.update({'right': current_node.right.data})
        print(tree)
        self.traverse(current_node.right)
    return tree

测试用二叉树结构 #

__10_____           
    /         \          
   _5_       20_________ 
  /   \     /           \
 _3   7    15    ______73
/  \ /    /     /        
1  4 6   12    25___     
 \                  \    
  2                 30_   
                  /   \  
                 27  35  

运行日志 #

{'root': 10}
{'root': 10, 'left': 5}
{'root': 5}
{'root': 5, 'left': 3}
{'root': 3}
{'root': 3, 'left': 1}
{'root': 1}
{'root': 1, 'right': 2}
{'root': 2}
{'root': 3, 'left': 1, 'right': 4}
{'root': 4}
{'root': 5, 'left': 3, 'right': 7}
{'root': 7}
{'root': 7, 'left': 6}
{'root': 6}
{'root': 10, 'left': 5, 'right': 20}
{'root': 20}
{'root': 20, 'left': 15}
{'root': 15}
{'root': 15, 'left': 12}
{'root': 12}
{'root': 20, 'left': 15, 'right': 73}
{'root': 73}
{'root': 73, 'left': 25}
{'root': 25}
{'root': 25, 'right': 30}
{'root': 30}
{'root': 30, 'left': 27}
{'root': 27}
{'root': 30, 'left': 27, 'right': 35}
{'root': 35}
{'root': 10, 'left': 5, 'right': 20}

Process finished with exit code 0

故障表现 #

日志显示递归逻辑已经访问到所有节点，但最终返回的字典仅包含根节点10及其直接左右子节点5、20，未正确嵌套深层子树结构。

问题根因 #

• 递归返回值未被使用：每次递归调用遍历子节点时，子树遍历生成的字典对象直接被丢弃，没有挂载到当前层级的字典结构中。
• 字段赋值逻辑错误：代码中left、right字段存储的是子节点的data数值，而非子树遍历生成的完整字典，无法保留深层层级关系。
• 类方法缩进错误：Node类的__str__方法、BinarySearchTree类的__str__方法、traverse方法均定义在类外部，不属于类的成员方法，按类方法调用时会抛出参数不匹配异常。

修复方案 #

1. 修正类方法缩进，将所有属于类的方法调整到类定义内部。
2. 调整遍历逻辑，将左右子树递归调用的返回值，直接赋值给当前节点字典的left、right键，替代原来直接存储节点data值的逻辑。
3. 增加递归终止判断，节点为空时直接返回None，兼容空子树场景。

修复后代码 #

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

    def __str__(self):
        return str(self.data)

class BinarySearchTree:
    def __init__(self):
        self.root = None

    def __str__(self):
        return str(self.traverse(self.root))

    def traverse(self, current_node):
        if current_node is None:
            return None
        tree = {'root': current_node.data}
        if current_node.left is not None:
            tree['left'] = self.traverse(current_node.left)
        if current_node.right is not None:
            tree['right'] = self.traverse(current_node.right)
        return tree

效果说明 #

修复后从根节点调用traverse方法，返回的字典会完整嵌套所有层级的子树结构，可直接序列化为JSON，不会丢失节点层级关系。例如根节点10的left字段值不是单个数字5，而是以5为根节点的完整左子树字典，包含其下3、7等所有后代节点结构。

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