python - 使用 Python 理解二叉搜索树插入

Question

我正在尝试理解以下 Python 中的二叉搜索树节点插入实现。我在插入函数中放置了一些打印语句。我可以理解由两个插入调用生成的前两个打印，但我无法理解在第 3 个插入调用之前生成的第三个打印。带有调试打印的实现如下所示:

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


def insert(root, node):
    if root is None:
        root = node
        return root
    if node.value < root.value:
        root.left = insert(root.left, node)
        print("left: " + str(root.left.value))
    if node.value > root.value:
        root.right = insert(root.right, node)
        print("right: " + str(root.right.value))
    return root


root = Node(50)

insert(root, Node(10))
insert(root, Node(2))
insert(root, Node(80))
insert(root, Node(15))
insert(root, Node(60))
insert(root, Node(90))

代码打印:

left: 10
left: 2
left: 10
right: 80
right: 15
left: 10
left: 60

right: 80
right: 90
right: 80

目前我的理解:

1. 插入(根，节点(10))

   (i) __init__ 调用了 value = 10。由于 root 已经设置为 50，如果条件为 10<50，程序将进入第二个。

   (ii) 调用递归插入函数，root.left 为 None，节点值为 10。由于 root.left 现在为 None，如果条件和 root 的值为 10，则程序进入第一个。这完成了递归调用和程序执行下一条语句，即 print("left: "+ str(root.left.value)) 这将打印 10。程序评估第三个 if 条件是否如预期的那样为 false 并完成插入的函数调用共 10 个。

2. 插入(根，节点(2))

   (i) __init__ 调用了 value=2。如果条件为 2<50，则程序进入第二个。

   (ii) 调用递归插入函数，root.left 为 10，节点值为 2。如果条件为 2<10，程序再次进入第二个。

   (iii) 再次调用递归插入函数，root.left 为 None，值为 2。现在如果条件和 root 得到，程序首先进入 值 2。这完成了递归重复调用，程序执行下一个打印语句 print("left: "+ str(root.left.value)) 打印 2。

   (iv) 现在如预期程序评估第三个 if 条件为 false 并成功调用 return。
   但是，在开始 insert(root, Node(80)) 之前，它再次返回到第二个 if 条件中的打印语句并打印 10。
   我不明白，为什么在完成(或者不是？)函数调用后又回到打印语句？

Answer 1

当插入节点 2 时，它进入第二个 if 语句两次，如您所说:

insert(root, Node(2)) -> root being Node 50
insert(root, Node(2)) -> root being Node 10

因此，当递归步骤结束时，将运行两个打印语句，但顺序相反。这意味着第一个打印将显示节点 10 的左侧(插入的节点 2)，第二个打印将显示节点 50 的左侧(节点 10)

你可以将上面的代码想象成一个堆栈，所以所有的东西都需要在算法完成之前执行，并且在顶部的将首先执行。