了解使用Python插入二进制搜索树
我正在尝试理解以下Python中的二进制搜索树节点插入实现。我在insert函数中放置了一些print语句。我可以理解由两个insert调用生成的前两个print，但我不能理解在第3个insert调用之前生成的第三个print。调试打印的实现如下所示：
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到目前为止我的理解是：
insert(root, Node(10))
(i)调用值= 10的__init__。因为根已经设置为50，所以程序使用10<50在第二个if条件内。
(ii)在root.left为None、节点值为10的情况下调用递归插入函数。由于root.left现在为None，程序进入第一个if条件，根值为10。这将完成递归调用，程序执行下一条语句，该语句为print("left: " + str(root.left.value)) This打印10。程序如预期的将第三个if条件求值为false，并完成插入false的函数调用
(i)调用了带有value=2的__init__。使用2<50时，程序进入第二个if条件。
(ii)在root.left为10，节点值为2的情况下，调用递归插入函数。使用2<10，程序再次进入第二个if条件。
(iii)在root.left为None，value为2的情况下，再次调用递归插入函数。现在程序进入第一个if条件，根获得值2。这完成了递归重复调用，程序执行下一个打印语句print("left: " + str(root.left.value))，打印2。
(iv)现在不出所料，程序将第三个if条件求值为false，并成功调用return。
但是，在启动insert(root, Node(80))之前，它再次返回到第二个if条件中的打印语句，并打印一个10。
我没有得到这个，那为什么在完成之后(或者不是？)调用它的函数将再次返回到打印语句--
回答 2
Stack Overflow用户
发布于 2018-07-22 07:37:48
正如您所说，当节点2被插入时，它会在第二个if语句中出现两次：
insert(root, Node(2)) -> root being Node 50
insert(root, Node(2)) -> root being Node 10因此，当递归步骤结束时，将以相反的顺序运行两个print语句。这意味着第一个打印将显示节点10的左侧(插入的节点2)，第二个打印将显示节点50的左侧(节点10)
您可以将上面的代码可视化为一个堆栈，因此所有内容都需要在算法完成之前执行，而顶部的代码将首先执行。
Stack Overflow用户
发布于 2018-07-22 18:04:01
我尝试了几个实验，根据结果，以下是一个答案：
当插入函数的return root通过中间节点到达根节点时，将为注入2层或更深的节点执行额外的打印。发布带有附加调试打印的代码，以跟踪根对象的ids和打印执行的时间戳。
代码：
import time
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) + " " + str(time.clock()))
if node.value > root.value:
root.right = insert(root.right, node)
print("right: " + str(root.right.value) + " " + str(time.clock()))
print(id(root))
return root
root = Node(50)
print("root node id: " + str(id(root)))
insert(root, Node(10))
insert(root, Node(2))
insert(root, Node(80))
insert(root, Node(15))
insert(root, Node(60))
insert(root, Node(90))带有内联注释的程序输出：
为根节点50分配了对象id 50359600
root node id: 50359600 插入第一个节点10
left: 10 3.77580764525532e-07对于return root调用，插入函数返回驻留在50359600的根50
50359600插入第二个节点2
left: 2 3.398226880729788e-05使用return root调用，insert函数返回到50359600，但通过50360272 (2的直接根10的id)并在返回根50 @ 50359600之前打印10
50360272
left: 10 4.8330337859268096e-05
5035960080是紧接在50之后的右侧节点，因此在注入80后return root直接达到50@50359600。
right: 80 6.305598767576385e-05
50359600与前面执行中的节点2类似，在插入15之后，插入函数必须通过10通过return root调用返回到50。
right: 15 7.702647596320853e-05
50360272
left: 10 8.986422195707663e-05
50359600同样的..。
left: 60 0.00010345712947999577
50360304
right: 80 0.0001155397139448128
50359600
right: 90 0.00012837745993868089
50360304
right: 80 0.00014008246363897238
50359600https://stackoverflow.com/questions/51460733
复制相似问题
腾讯云开发者
