BST 插入函数给出问题

Question

我正在努力练习 python 但我被困在这里。我的二叉搜索树可以正常工作，因为它与搜索功能相关，但我的插入功能存在一些问题。我不断收到错误 TypeError: insert() missing 1 required positional argument: 'key' 我似乎看不到我遗漏了什么：

class Node:

def __init__(self, key, parent = None):
    self.key = key
    self.parent = parent
    self.left = None 
    self.right = None
    # Make sure that the parent's left/right pointer
    # will point to the newly created node.
    if parent != None:
        if key < parent.key:
            assert(parent.left == None),
            parent.left = self
        else:
            assert key > parent.key, 
            assert(parent.right == None ), 
            parent.right = self

# Utility function that keeps traversing left until it finds
# the leftmost descendant
def get_leftmost_descendant(self):
    if self.left != None:
        return self.left.get_leftmost_descendant()
    else:
        return self

def search(self, key):
    if self.key == key:
        return (True, self)
    else:
        if key > self.key and self.right != None:
            return self.right.search(key)
        if key < self.key and self.left != None:
            return self.left.search(key) 
        else:
            return (False, self)

def insert(self, parent, key):
    if parent is None:
        parent = Node(key)
        return parent
    else:
        if parent.data <= key:
            parent.right = self.insert(parent.right, key)
        else:
            parent.left = self.insert(parent.left, key)
        return parent

这些是它测试的条件。它似乎毫无问题地通过了搜索，但我不完全确定插入错误的原因。

print('-- Testing search -- ')
(b, found_node) = t1.search(18)
assert b and found_node.key == 18, 'test 8 failed'
(b, found_node) = t1.search(25)
assert b and found_node.key == 25, 
(b, found_node) = t1.search(26)
assert(not b), 'test 10 failed'
assert(found_node.key == 40),

print('-- Testing insert -- ')
ins_node = t1.insert(26)
assert ins_node.key == 26, ' test 12 failed '
assert ins_node.parent == t4, ' test 13 failed '
assert t4.left == ins_node, ' test 14 failed '
ins_node2 = t1.insert(33)
assert ins_node2.key == 33, 'test 15 failed'
assert ins_node2.parent == ins_node, 'test 16 failed'
assert ins_node.right == ins_node2, 'test 17 failed'

Answer 1

那是因为Node中定义的insert签名是

def insert(self: Node, parent: Optional[Node], key: int):

并且在你的测试中你正在调用

ins_node = t1.insert(26)

有签名

def insert(self: Node, key: int):

由于签名不匹配，出现错误。你可以重构为这样的东西：

def insert(self, key):
    if self.parent is None:
        self.parent = Node(key)
        return parent
    
    if self.parent.data <= key:
        self.parent.right = self.parent.right.insert(key)
    else:
        self.parent.left = self.parent.left.insert(key)
    return self.parent

BST 插入函数给出问题

BST Insert function giving issues

python

binary-search-tree