从二叉搜索树中删除节点

Question

我正在从整数列表生成二叉搜索树，一切正常，但是当我实现删除节点的功能时 (deleteNode)。我得到一个错误
AttributeError: 'int' 对象没有属性 'value'

我知道这个错误意味着我正在尝试访问整数上不存在的属性。但我不知道如何让它发挥作用。到目前为止，这是我的全部代码。


numbers = [8, 10, 14, 3, 1, 6, 4, 7]
print(f"My numbers: {numbers}")

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

def insert_node(node, value):
    if node == None:
        return Node(value)
    if value < node.value:
        node.left = insert_node(node.left, value)
    else:
        node.right = insert_node(node.right, value)

    return node

def inorder(root):
    if root is not None:
        inorder(root.left)
        print(str(root.value) + "->", end=' ')
        inorder(root.right)


def min_value(node):
    current = node
    while(current.left is not None):
        current = current.left
    return current.value


def deleteNode(root, value):
    if root is None:
        return root

    if value < root.value:
        root.left = deleteNode(root.left, value)
    elif(value > root.value):
        root.right = deleteNode(root.right, value)
    else:
        if root.left is None:
            temp = root.right
            root = None
            return temp

        elif root.right is None:
            temp = root.left
            root = None
            return temp

        temp = min_value(root.right)
        root.value = temp.value
        root.right = deleteNode(root.right, temp.value)

    return root

root = None
for i in range(len(numbers)):
    root = insert_node(root, numbers[i])

print(f"\nInorder traversal: ")
inorder(root)


print("\nDelete 3")
root = deleteNode(root, 3)
print("Inorder traversal: ", end=' ')
inorder(root)

Answer 1

每 temp.value 改为 temp。因为 temp 本身是一个整数并且 temp.value 给出错误，因为 int 没有名为 value.

的属性

需要修改的代码：

temp = min_value(root.right)
root.value = temp
root.right = deleteNode(root.right, temp)

输出：

My numbers: [8, 10, 14, 3, 1, 6, 4, 7]

Inorder traversal:
1-> 3-> 4-> 6-> 7-> 8-> 10-> 14->
Delete 3
Inorder traversal:  1-> 4-> 6-> 7-> 8-> 10-> 14->

从二叉搜索树中删除节点

Deleting node from Binary Search Tree

python

nodes

binary-search-tree