Python二叉搜索树中序遍历报错及遍历原理疑问

一、函数参数错误修复 #

你遇到的错误inorder_traversal() takes 0 positional arguments but 1 was given，原因是Python类的实例方法必须接收self作为第一个参数。当你调用tree.inorder_traversal()时，Python会自动把tree这个实例作为参数传递给函数，但你的inorder_traversal定义里没有声明这个参数，所以触发报错。

修正后的完整代码如下：

class BinarySearchTree:
    def __init__(self, value):
        self.left = None
        self.right = None
        self.value = value
        
    def insert(self, value):
        #checking if value that we are trying to insert is less then the current value
        if value < self.value:
            if self.left is None:
                #if the left node is not existing then we are going to create it
                self.left = BinarySearchTree(value)
            else:
                self.left.insert(value)
        else:
            if self.right is None:
                self.right = BinarySearchTree(value)
            else:
                self.right.insert(value)
                
    # 修正：添加self参数
    def inorder_traversal(self):
        if self.left:
            self.left.inorder_traversal()
        print(self.value)
        if self.right:
            self.right.inorder_traversal()
        
            
tree = BinarySearchTree(15)
tree.insert(14)
tree.insert(20)
tree.insert(7)
tree.insert(8)
tree.insert(1)
tree.insert(70)
tree.inorder_traversal()

二、中序遍历的回溯过程详解 #

中序遍历的核心逻辑是左子树 → 当前节点 → 右子树，回溯的本质是递归调用栈的弹出过程，结合你的示例树拆解如下：

你的二叉树结构：

15
       /  \
     14    20
    /       \
   7        70
  / \
 1   8

遍历完整流程：

1. 从根节点15开始，调用15.inorder_traversal()，先执行self.left.inorder_traversal()，进入14的遍历。
2. 进入14的遍历，执行self.left.inorder_traversal()，进入7的遍历。
3. 进入7的遍历，执行self.left.inorder_traversal()，进入1的遍历。
4. 进入1的遍历，self.left和self.right都是None，打印1后函数执行完毕，从调用栈弹出，回到7的遍历函数。
5. 回到7的遍历，打印7；接着执行self.right.inorder_traversal()，进入8的遍历。
6. 进入8的遍历，打印8后函数执行完毕，从调用栈弹出，回到7的遍历函数，7的遍历完成后弹出回到14的遍历函数。
7. 回到14的遍历，打印14；self.right是None，函数执行完毕，弹出回到15的遍历函数。
8. 回到15的遍历，打印15；执行self.right.inorder_traversal()，进入20的遍历。
9. 进入20的遍历，打印20；执行self.right.inorder_traversal()，进入70的遍历。
10. 进入70的遍历，打印70后函数执行完毕，依次弹出回到20、15的遍历函数，整个流程结束。

简单说，每一次递归调用都会把当前节点的遍历任务压入调用栈，当某个节点的左、右子树都处理完成（或没有子树），该节点的遍历任务就结束了，调用栈弹出这个任务，回到上一层节点继续处理剩余步骤（打印当前节点、处理右子树），这就是回溯的过程。

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