Python实现Binary Search Tree缺失rootdata参数报错及打印问题求解

现有代码错误列表 #

• 初始化BSTree实例时未传入必填的rootdata参数，直接调用BSTree()触发参数缺失报错
• insert、find方法需要手动传入当前节点参数，对外调用不友好，且现有调用逻辑未传入第二个参数
• 前序遍历方法名拼写错误：定义为PreOder，递归时调用的是不存在的PreOrder
• 调用前序遍历时传入了数值3，应该传入树的根节点对象
• 未对重复值的插入做兼容处理，题目给定的列表包含重复元素

修复后完整代码 #

class Node: 
    # 构造方法创建新节点
    def __init__(self, data): 
        self.data = data 
        self.left = None
        self.right = None
        
class BSTree():
    def __init__(self, rootdata=None):
        # 兼容空树初始化，后续可调用insert插入根节点
        self.root = Node(rootdata) if rootdata is not None else None
    
    # 对外暴露的插入接口，无需手动传当前节点
    def insert(self, data):
        if self.root is None:
            self.root = Node(data)
            return
        self._insert_recursive(data, self.root)
    
    # 内部递归插入逻辑
    def _insert_recursive(self, data, cur_node):
        if data < cur_node.data:
            if cur_node.left is None:
                cur_node.left = Node(data)
            else:
                self._insert_recursive(data, cur_node.left)
        elif data > cur_node.data:
            if cur_node.right is None:
                cur_node.right = Node(data)
            else:
                self._insert_recursive(data, cur_node.right)
        else:
            print(f"重复值 {data} 已存在，跳过插入")
         
    # 对外暴露的查找接口
    def find(self, data):
        return self._find_recursive(data, self.root) if self.root is not None else False
    
    # 内部递归查找逻辑
    def _find_recursive(self, data, cur_node):
        if data < cur_node.data and cur_node.left:
            return self._find_recursive(data, cur_node.left)
        elif data > cur_node.data and cur_node.right:
            return self._find_recursive(data, cur_node.right)
        return data == cur_node.data
    
    # 对外暴露的前序遍历接口
    def pre_order(self):
        print("前序遍历结果：")
        self._pre_order_recursive(self.root)
        print()
    
    # 内部递归前序遍历逻辑，修复拼写错误
    def _pre_order_recursive(self, root):
        if root is not None:
            print(root.data, end=" ")
            self._pre_order_recursive(root.left)
            self._pre_order_recursive(root.right)
    
    # 中序遍历：二叉搜索树中序遍历结果为升序，可验证构建是否正确
    def in_order(self):
        print("中序遍历结果：")
        self._in_order_recursive(self.root)
        print()
    
    def _in_order_recursive(self, root):
        if root is not None:
            self._in_order_recursive(root.left)
            print(root.data, end=" ")
            self._in_order_recursive(root.right)

# 基于给定列表构建二叉搜索树
mylist = [1,3,2,4,12,14,23,43,23,44,34,43]
bst = BSTree()
for num in mylist:
    bst.insert(num)

# 功能测试
print("查找元素3的结果：", bst.find(3))
print("查找元素100的结果：", bst.find(100))
# 打印树的遍历结果
bst.pre_order()
bst.in_order()

运行输出 #

重复值 23 已存在，跳过插入
重复值 43 已存在，跳过插入
查找元素3的结果： True
查找元素100的结果： False
前序遍历结果：
1 3 2 4 12 14 23 43 34 44 
中序遍历结果：
1 2 3 4 12 14 23 34 43 44 

中序遍历结果为升序，符合二叉搜索树的特性，证明树构建正确。

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