时间戳

首页 > 解决方案 > 无法理解这种用于在 Python 中插入值的二叉搜索树 (BST) 算法

python - 无法理解这种用于在 Python 中插入值的二叉搜索树 (BST) 算法

问题描述

我正在学习算法。为了让 BST 构造在 BST 中插入一个值，我遇到了这段代码。我不太擅长 OOPS 概念，无法弄清楚 currentnode.left = BST(value) 和 currentnode = currentnode.left 是如何工作的。如果有人可以帮助我理解这一点，那将有很大帮助。

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

    def insert(self, value):
        currentnode = self
        while True:
            if value < currentnode.value:
                if currentnode.left is None:
                   currentnode.left = BST(value)
                   break
                else:
                   currentnode = currentnode.left
            else:
                if currentnode.right is None:
                    currentnode.right = BST(value)
                    break
                else:
                    currentnode = currentnode.right
        return self

标签： pythonpython-3.xalgorithmbinary-search-tree

解决方案

在insert函数中，currentnode已经赋值给self。从 while 循环开始，使用 currentnode 的值检查参数值。如果它很小，则执行第一个条件，否则执行第二个条件。

现在你的疑问来了。假设第一个条件正在执行。如果当前节点的左值为none，则代码调用BST(value)，即调用构造函数来启动一个新节点，该新节点又成为当前节点的左孩子。否则，如果已经有一个左孩子，则该孩子成为当前节点，并且一次又一次地迭代 while 循环，直到找到合适的位置。

另外，如果这段代码看起来很复杂。你应该参考这个，以防万一它有帮助。

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

def insert(root,node): 
    if root is None: 
        root = node 
    else: 
        if root.val < node.val: 
            if root.right is None: 
                root.right = node 
            else: 
                insert(root.right, node) 
        else: 
            if root.left is None: 
                root.left = node 
            else: 
                insert(root.left, node) 

#      5 
#    /    \ 
#   3       7
#   / \    / \ 
#  2   4  6   8 
r = Node(5) 
insert(r,Node(3)) 
insert(r,Node(2)) 
insert(r,Node(4)) 
insert(r,Node(7)) 
insert(r,Node(6)) 
insert(r,Node(8))

推荐阅读