首页
学习
活动
专区
工具
TVP
发布
社区首页 >问答首页 >了解使用Python插入二进制搜索树

了解使用Python插入二进制搜索树
EN

Stack Overflow用户
提问于 2018-07-22 06:56:44
回答 2查看 199关注 0票数 4

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

代码语言:javascript
复制
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))

代码打印如下:

代码语言:javascript
复制
left: 10
left: 2
left: 10
right: 80
right: 15
left: 10
left: 60

right: 80
right: 90
right: 80

到目前为止我的理解是:

  1. 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。

我没有得到这个,那为什么在完成之后(或者不是?)调用它的函数将再次返回到打印语句--

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2018-07-22 07:37:48

正如您所说,当节点2被插入时,它会在第二个if语句中出现两次:

代码语言:javascript
复制
insert(root, Node(2)) -> root being Node 50
insert(root, Node(2)) -> root being Node 10

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

您可以将上面的代码可视化为一个堆栈,因此所有内容都需要在算法完成之前执行,而顶部的代码将首先执行。

票数 2
EN

Stack Overflow用户

发布于 2018-07-22 18:04:01

我尝试了几个实验,根据结果,以下是一个答案:

当插入函数的return root通过中间节点到达根节点时,将为注入2层或更深的节点执行额外的打印。发布带有附加调试打印的代码,以跟踪根对象的ids和打印执行的时间戳。

代码:

代码语言:javascript
复制
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

代码语言:javascript
复制
 root node id: 50359600 

插入第一个节点10

代码语言:javascript
复制
left: 10  3.77580764525532e-07

对于return root调用,插入函数返回驻留在50359600的根50

代码语言:javascript
复制
50359600

插入第二个节点2

代码语言:javascript
复制
left: 2  3.398226880729788e-05

使用return root调用,insert函数返回到50359600,但通过50360272 (2的直接根10的id)并在返回根50 @ 50359600之前打印10

代码语言:javascript
复制
50360272
left: 10  4.8330337859268096e-05
50359600

80是紧接在50之后的右侧节点,因此在注入80后return root直接达到50@50359600。

代码语言:javascript
复制
right: 80  6.305598767576385e-05
50359600

与前面执行中的节点2类似,在插入15之后,插入函数必须通过10通过return root调用返回到50。

代码语言:javascript
复制
right: 15  7.702647596320853e-05
50360272
left: 10  8.986422195707663e-05
50359600

同样的..。

代码语言:javascript
复制
left: 60  0.00010345712947999577
50360304
right: 80  0.0001155397139448128
50359600

right: 90  0.00012837745993868089
50360304
right: 80  0.00014008246363897238
50359600
票数 1
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/51460733

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档