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

Question

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

到目前为止我的理解是：

>

插入（根，节点(10))

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

(ii)调用Root.left为10，节点值为2的递归insert函数。程序再次进入第二个if条件，条件为2<10。

(iii)再次调用Root.left为None，value为2的递归insert函数。现在程序进入first if条件,root获得值2。这将完成递归重复调用，程序执行下一个打印语句print（“left：”+str(root.left.value))，该语句打印2。

(iv)现在，正如预期的那样，程序将第三个if条件计算为false，并成功调用return。
但是，在开始insert(root，Node(80))之前，它再次返回到第二个if条件中的print语句，并打印一个10。
我没有得到这个，那为什么在完成之后（或者不是？）函数调用它会再次返回到print语句？

Answer 1

当插入节点2时，它会在第二个if语句中运行两次，正如您所说的：

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

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

您可以将上面的代码可视化为一个堆栈，因此在算法结束之前，所有的东西都需要执行，最上面的东西将首先执行。