Python实现的Binary Search Tree中print_tree方法存在什么问题？

你的print_tree方法存在两个关键问题：

• 方法没有接收当前要打印的节点作为参数，递归调用时始终操作self.root，导致递归逻辑完全混乱
• 最后一行递归传参错误：self.root.left.value是节点的数值，不是Node对象，后续递归时会因为无法访问节点属性报错

修复后的代码 #

修改print_tree方法，让它接收一个可选的node参数（默认是树的根节点），针对每个节点递归处理其左右子树：

class Node:
    def __init__(self,value):
        self.value = value
        self.left = None
        self.right = None
        
class BinarySearchTree:
    def __init__(self):
        self.root = None
    
    def insert(self,value):
        new_node = Node(value)
        if self.root is None:
            self.root = new_node
            return True
        temp = self.root
        while (True): 
            if new_node.value == temp.value:
                return False
            if new_node.value < temp.value: #left
                if temp.left is None:
                    temp.left = new_node
                    return True
                temp = temp.left
            else:                           #right
                if temp.right is None:
                    temp.right = new_node
                    return True
                temp =temp.right
                
    def contains(self,value):
        temp = self.root
        while (temp is not None):
            if value < temp.value:
                temp = temp.left
            elif value > temp.value:
                temp = temp.right
            else:
                return True
        return False
    
    def print_tree(self, node=None, level=0):
        # 未传入节点时默认从根节点开始
        if node is None:
            node = self.root
        if node is not None:
            # 先递归打印右子树（值更大，对应输出的上层）
            self.print_tree(node.right, level + 1)
            print("   " * level + "->", node.value)
            # 再递归打印左子树
            self.print_tree(node.left, level + 1)

验证运行 #

执行你的测试代码：

my_tree = BinarySearchTree()
my_tree.insert(2)
my_tree.insert(1)
my_tree.insert(3)
my_tree.print_tree()

输出结果与预期一致：

-> 3
-> 2
    -> 1

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