在 python 中删除二叉搜索树中的节点？
Deleting nodes in a binary search tree in python?
所以我在计算机科学中遇到了一个问题 class，它要求我扩展我们之前编写的二叉搜索树 class，并添加一种从中删除节点的方法树，如果该节点有 0、1 或 2 个子节点，则必须考虑这一点。查看条件和内容后，我得出结论，我需要找到指定节点的父节点才能执行此操作，因为已删除节点的子节点将分配给父节点。
这就是我卡住的地方，因为我们最近才开始研究节点和链表，我对此还是很陌生，这就是为什么我不知道如何跟踪父节点。
这是 BST 的代码 class:
导入副本
class _BSTNode:
def __init__(self, value):
"""
-------------------------------------------------------
Creates a node containing a copy of value.
Use: node = _BSTNode( value )
-------------------------------------------------------
Preconditions:
value - data for the node (?)
Postconditions:
Initializes a BST node containing value. Child pointers are None, height is 1.
-------------------------------------------------------
"""
self._value = copy.deepcopy(value)
self._left = None
self._right = None
self._height = 1
return
def _update_height(self):
"""
-------------------------------------------------------
Updates the height of the current node.
Use: node._update_height()
-------------------------------------------------------
Postconditions:
_height is 1 plus the maximum of the node's (up to) two children.
-------------------------------------------------------
"""
if self._left is None:
left_height = 0
else:
left_height = self._left._height
if self._right is None:
right_height = 0
else:
right_height = self._right._height
self._height = max(left_height, right_height) + 1
return
def __str__(self):
"""
-------------------------------------------------------
DEBUG: Prints node height and value.
-------------------------------------------------------
"""
return "h: {}, v: {}".format(self._height, self._value)
class BST:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty BST.
Use: bst = BST()
-------------------------------------------------------
Postconditions:
Initializes an empty bst.
-------------------------------------------------------
"""
self._root = None
self._count = 0
return
def is_empty(self):
"""
-------------------------------------------------------
Determines if bst is empty.
Use: b = bst.is_empty()
-------------------------------------------------------
Postconditions:
returns:
True if bst is empty, False otherwise.
-------------------------------------------------------
"""
return self._root is None
def __len__(self):
"""
-------------------------------------------------------
Returns the number of nodes in the BST.
Use: n = len( bst )
-------------------------------------------------------
Postconditions:
returns:
the number of nodes in the BST.
-------------------------------------------------------
"""
return self._count
def insert(self, value):
"""
-------------------------------------------------------
Inserts a copy of value into the bst.
Use: b = bst.insert( value )
-------------------------------------------------------
Preconditions:
value - data to be inserted into the bst (?)
Postconditions:
returns:
inserted - True if value is inserted into the BST,
False otherwise. Values may appear only once in a tree. (bool)
-------------------------------------------------------
"""
self._root, inserted = self._insert_aux(self._root, value)
return inserted
def _insert_aux(self, node, value):
"""
-------------------------------------------------------
Inserts a copy of _value into node.
Private recursive operation called only by insert.
Use: node, inserted = self._insert_aux( node, value )
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
value - data to be inserted into the node (?)
Postconditions:
returns:
node - the current node (_BSTNode)
inserted - True if value is inserted into the BST,
False otherwise. Values may appear only once in a tree. (boolean)
-------------------------------------------------------
"""
if node is None:
# Base case: add a new node containing the value.
node = _BSTNode(value)
self._count += 1
inserted = True
elif value < node._value:
# General case: check the left subtree.
node._left, inserted = self._insert_aux(node._left, value)
elif value > node._value:
# General case: check the right subtree.
node._right, inserted = self._insert_aux(node._right, value)
else:
# Base case: value is already in the BST.
inserted = False
if inserted:
# Update the current node height if any of its children have been changed.
node._update_height()
return node, inserted
def retrieve(self, key):
"""
-------------------------------------------------------
Retrieves a copy of a value matching key in a BST. (Iterative)
Use: v = bst.retrieve( key )
-------------------------------------------------------
Preconditions:
key - data to search for (?)
Postconditions:
returns:
value - value in the node containing key, otherwise None (?)
-------------------------------------------------------
"""
node = self._root
value = None
while node is not None and value is None:
if key < node._value:
node = node._left
elif key > node._value:
node = node._right
else:
value = copy.deepcopy(node._value)
return value
def inorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in inorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed inorder.
-------------------------------------------------------
"""
if self._root is not None:
self._inorder_aux(self._root)
return
def _inorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in inorder
-------------------------------------------------------
"""
if node._left is not None:
self._inorder_aux(node._left)
print(node._value)
if node._right is not None:
self._inorder_aux(node._right)
return
def postorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in postorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed postorder.
-------------------------------------------------------
"""
if self._root is not None:
self._postorder_aux(self._root)
return
def _postorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in postorder
-------------------------------------------------------
"""
if node._left is not None:
self._preorder_aux(node._left)
if node._right is not None:
self._preorder_aux(node._right)
print(node._value)
return
def preorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in preorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed preorder.
-------------------------------------------------------
"""
if self._root is not None:
self._preorder_aux(self._root)
return
def _preorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in preorder
-------------------------------------------------------
"""
print(node._value)
if node._left is not None:
self._postorder_aux(node._left)
if node._right is not None:
self._postorder_aux(node._right)
return
def traverse(self):
"""
---------------------------------------------------------
Returns the contents of bst in an array in sorted order.
---------------------------------------------------------
Postconditions:
returns:
a - an array containing the contents of bst in sorted order.
---------------------------------------------------------
"""
a = []
self._traverse_aux(self._root, a)
return a
def _traverse_aux(self, node, a):
"""
---------------------------------------------------------
Traverse the node's subtree in inorder, adding the contents of
each node to an array
---------------------------------------------------------
Preconditions:
node - the root of a subtree (_BSTNode)
Postconditions:
a - contains the contents of the subtree of node
in sorted order.
---------------------------------------------------------
"""
if node._left is not None:
self._traverse_aux(node._left, a)
a.append(node._value)
if node._right is not None:
self._traverse_aux(node._right, a)
return
def is_identical(self, rhs):
"""
---------------------------------------------------------
Determines whether two BSTs are identical.
Use: b = bst.is_identical( rhs )
-------------------------------------------------------
Preconditions:
rhs - another bst (BST)
Postconditions:
returns:
identical - True if this bst contains the same values
in the same order as rhs, otherwise returns False.
-------------------------------------------------------
"""
identical = self._is_identical_aux(self._root, rhs._root)
return identical
def _is_identical_aux(self, node1, node2):
"""
---------------------------------------------------------
Determines whether two subtrees are identical.
Use: b = bst.is_identical( node1, node2 )
-------------------------------------------------------
Preconditions:
node1 - node of the current BST (_BSTNode)
node2 - node of the rhs BST (_BSTNode)
Postconditions:
returns:
result - True if this stubtree contains the same values as rhs
subtree in the same order, otherwise returns False.
-------------------------------------------------------
"""
result = True
if node1._value != node2._value:
result = False
if node1._left is not None and node2._left is not None and result == True:
result = self._is_identical_aux(node1._left, node2._left)
if node1.right is not None and node2._right is not None and result == True:
result = self._is_identical_aux(node1._right, node2._right)
return result
def leaf_count(self):
"""
---------------------------------------------------------
Returns the number of leaves (nodes with no children) in bst.
Use: n = bst.leaf_count()
(Recursive algorithm)
---------------------------------------------------------
Postconditions:
returns:
n - number of nodes with no children in bst.
---------------------------------------------------------
"""
n = self._leaf_count_aux(self._root)
return n
def _leaf_count_aux(self, node):
"""
---------------------------------------------------------
Returns the number of leaves (nodes with no children) in bst.
Use: n = bst.leaf_count()
(Recursive algorithm)
---------------------------------------------------------
Preconditions:
node - a BST node (_BSTNode)
Postconditions:
returns:
n - number of nodes with no children below node.
---------------------------------------------------------
"""
count = 0
if node._left is None and node._right is None:
count += 1
if node._left is not None and node._right is None:
count += self._leaf_count_aux(node._left)
if node._left is None and node._right is not None:
count += self._leaf_count_aux(node._right)
if node._left is not None and node._right is not None:
count += self._leaf_count_aux(node._left)
count += self._leaf_count_aux(node._right)
return count
def _delete_node(self, node):
"""
-------------------------------------------------------
Removes a node from the bst.
Use: node = self._delete_node(node)
-------------------------------------------------------
Preconditions:
node - the bst node to be deleted (_BSTNode)
Postconditions:
returns:
node - the node that replaces the deleted node. This node is the node
with the maximum value in the current node's left subtree (_BSTNode)
-------------------------------------------------------
"""
# Your code here.
return node
def parent_i(self, key):
"""
---------------------------------------------------------
Returns the value of the parent node of a key node in a bst.
---------------------------------------------------------
Preconditions:
key - a key value (?)
Postconditions:
returns:
value - a copy of the value in a node that is the parent of the
key node, None if the key is not found.
---------------------------------------------------------
"""
# Your code here
return value
BST中的最后两个函数class、parent_i和_delete_node是我想写的，注释是我的老师为这些函数写的条件我们需要写。我想如果我找到一种方法来获取父级，那么删除功能应该很容易做到，但现在我不知道从哪里开始。帮助将不胜感激！此外，中间的几个功能，如 min_i 和 max_i 应该是这样的，可能是为了我们 class 中的未来作业或实验室供我们编写。
提前致谢！
编辑：好的，所以我现在理解了结构，但现在我很困惑如果我尝试删除一个有 2 个子节点的节点，而 2 个子节点中较高的一个也有 2 个子节点，等等上？我应该怎么做才能让它适用于所有大小的所有 bsts？
要确定节点的parent，将变量初始设置为None。现在，当您对节点进行二进制搜索时，将该变量设置为您之前所在的任何节点，一旦您找到该节点
当您尝试删除一个节点时，有您提到的3种情况。前 2 个很容易解决，只需用 1 child 替换删除的节点即可。
棘手的情况是当你有 2 children 时。
有两种方法可以解决这个问题，你可以用它的中序后继节点替换那个节点，即紧随其后的节点（最左边的 child 这个节点的右边 child），或者用它的inorder 前驱，即出现在这个节点之前的节点（该节点左侧 child 的最右侧 child）。
这只是对实际发生情况的快速 运行 了解，但现在您应该很明显不需要明确找到 parent一个节点为了删除该节点，只需在您前往需要删除的节点时跟踪前一个节点就足够了。
有关详细信息，请参阅此example
所以我在计算机科学中遇到了一个问题 class，它要求我扩展我们之前编写的二叉搜索树 class，并添加一种从中删除节点的方法树，如果该节点有 0、1 或 2 个子节点，则必须考虑这一点。查看条件和内容后，我得出结论，我需要找到指定节点的父节点才能执行此操作，因为已删除节点的子节点将分配给父节点。 这就是我卡住的地方，因为我们最近才开始研究节点和链表，我对此还是很陌生，这就是为什么我不知道如何跟踪父节点。
这是 BST 的代码 class:
导入副本
class _BSTNode:
def __init__(self, value):
"""
-------------------------------------------------------
Creates a node containing a copy of value.
Use: node = _BSTNode( value )
-------------------------------------------------------
Preconditions:
value - data for the node (?)
Postconditions:
Initializes a BST node containing value. Child pointers are None, height is 1.
-------------------------------------------------------
"""
self._value = copy.deepcopy(value)
self._left = None
self._right = None
self._height = 1
return
def _update_height(self):
"""
-------------------------------------------------------
Updates the height of the current node.
Use: node._update_height()
-------------------------------------------------------
Postconditions:
_height is 1 plus the maximum of the node's (up to) two children.
-------------------------------------------------------
"""
if self._left is None:
left_height = 0
else:
left_height = self._left._height
if self._right is None:
right_height = 0
else:
right_height = self._right._height
self._height = max(left_height, right_height) + 1
return
def __str__(self):
"""
-------------------------------------------------------
DEBUG: Prints node height and value.
-------------------------------------------------------
"""
return "h: {}, v: {}".format(self._height, self._value)
class BST:
def __init__(self):
"""
-------------------------------------------------------
Initializes an empty BST.
Use: bst = BST()
-------------------------------------------------------
Postconditions:
Initializes an empty bst.
-------------------------------------------------------
"""
self._root = None
self._count = 0
return
def is_empty(self):
"""
-------------------------------------------------------
Determines if bst is empty.
Use: b = bst.is_empty()
-------------------------------------------------------
Postconditions:
returns:
True if bst is empty, False otherwise.
-------------------------------------------------------
"""
return self._root is None
def __len__(self):
"""
-------------------------------------------------------
Returns the number of nodes in the BST.
Use: n = len( bst )
-------------------------------------------------------
Postconditions:
returns:
the number of nodes in the BST.
-------------------------------------------------------
"""
return self._count
def insert(self, value):
"""
-------------------------------------------------------
Inserts a copy of value into the bst.
Use: b = bst.insert( value )
-------------------------------------------------------
Preconditions:
value - data to be inserted into the bst (?)
Postconditions:
returns:
inserted - True if value is inserted into the BST,
False otherwise. Values may appear only once in a tree. (bool)
-------------------------------------------------------
"""
self._root, inserted = self._insert_aux(self._root, value)
return inserted
def _insert_aux(self, node, value):
"""
-------------------------------------------------------
Inserts a copy of _value into node.
Private recursive operation called only by insert.
Use: node, inserted = self._insert_aux( node, value )
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
value - data to be inserted into the node (?)
Postconditions:
returns:
node - the current node (_BSTNode)
inserted - True if value is inserted into the BST,
False otherwise. Values may appear only once in a tree. (boolean)
-------------------------------------------------------
"""
if node is None:
# Base case: add a new node containing the value.
node = _BSTNode(value)
self._count += 1
inserted = True
elif value < node._value:
# General case: check the left subtree.
node._left, inserted = self._insert_aux(node._left, value)
elif value > node._value:
# General case: check the right subtree.
node._right, inserted = self._insert_aux(node._right, value)
else:
# Base case: value is already in the BST.
inserted = False
if inserted:
# Update the current node height if any of its children have been changed.
node._update_height()
return node, inserted
def retrieve(self, key):
"""
-------------------------------------------------------
Retrieves a copy of a value matching key in a BST. (Iterative)
Use: v = bst.retrieve( key )
-------------------------------------------------------
Preconditions:
key - data to search for (?)
Postconditions:
returns:
value - value in the node containing key, otherwise None (?)
-------------------------------------------------------
"""
node = self._root
value = None
while node is not None and value is None:
if key < node._value:
node = node._left
elif key > node._value:
node = node._right
else:
value = copy.deepcopy(node._value)
return value
def inorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in inorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed inorder.
-------------------------------------------------------
"""
if self._root is not None:
self._inorder_aux(self._root)
return
def _inorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in inorder
-------------------------------------------------------
"""
if node._left is not None:
self._inorder_aux(node._left)
print(node._value)
if node._right is not None:
self._inorder_aux(node._right)
return
def postorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in postorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed postorder.
-------------------------------------------------------
"""
if self._root is not None:
self._postorder_aux(self._root)
return
def _postorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in postorder
-------------------------------------------------------
"""
if node._left is not None:
self._preorder_aux(node._left)
if node._right is not None:
self._preorder_aux(node._right)
print(node._value)
return
def preorder(self):
"""
-------------------------------------------------------
Prints the contents of the tree in preorder order.
-------------------------------------------------------
Postconditions:
The contents of the tree are printed preorder.
-------------------------------------------------------
"""
if self._root is not None:
self._preorder_aux(self._root)
return
def _preorder_aux(self, node):
"""
-------------------------------------------------------
Prints the contents of the subtree at node.
-------------------------------------------------------
Preconditions:
node - a bst node (_BSTNode)
Postconditions:
prints:
the values at the subtree of node in preorder
-------------------------------------------------------
"""
print(node._value)
if node._left is not None:
self._postorder_aux(node._left)
if node._right is not None:
self._postorder_aux(node._right)
return
def traverse(self):
"""
---------------------------------------------------------
Returns the contents of bst in an array in sorted order.
---------------------------------------------------------
Postconditions:
returns:
a - an array containing the contents of bst in sorted order.
---------------------------------------------------------
"""
a = []
self._traverse_aux(self._root, a)
return a
def _traverse_aux(self, node, a):
"""
---------------------------------------------------------
Traverse the node's subtree in inorder, adding the contents of
each node to an array
---------------------------------------------------------
Preconditions:
node - the root of a subtree (_BSTNode)
Postconditions:
a - contains the contents of the subtree of node
in sorted order.
---------------------------------------------------------
"""
if node._left is not None:
self._traverse_aux(node._left, a)
a.append(node._value)
if node._right is not None:
self._traverse_aux(node._right, a)
return
def is_identical(self, rhs):
"""
---------------------------------------------------------
Determines whether two BSTs are identical.
Use: b = bst.is_identical( rhs )
-------------------------------------------------------
Preconditions:
rhs - another bst (BST)
Postconditions:
returns:
identical - True if this bst contains the same values
in the same order as rhs, otherwise returns False.
-------------------------------------------------------
"""
identical = self._is_identical_aux(self._root, rhs._root)
return identical
def _is_identical_aux(self, node1, node2):
"""
---------------------------------------------------------
Determines whether two subtrees are identical.
Use: b = bst.is_identical( node1, node2 )
-------------------------------------------------------
Preconditions:
node1 - node of the current BST (_BSTNode)
node2 - node of the rhs BST (_BSTNode)
Postconditions:
returns:
result - True if this stubtree contains the same values as rhs
subtree in the same order, otherwise returns False.
-------------------------------------------------------
"""
result = True
if node1._value != node2._value:
result = False
if node1._left is not None and node2._left is not None and result == True:
result = self._is_identical_aux(node1._left, node2._left)
if node1.right is not None and node2._right is not None and result == True:
result = self._is_identical_aux(node1._right, node2._right)
return result
def leaf_count(self):
"""
---------------------------------------------------------
Returns the number of leaves (nodes with no children) in bst.
Use: n = bst.leaf_count()
(Recursive algorithm)
---------------------------------------------------------
Postconditions:
returns:
n - number of nodes with no children in bst.
---------------------------------------------------------
"""
n = self._leaf_count_aux(self._root)
return n
def _leaf_count_aux(self, node):
"""
---------------------------------------------------------
Returns the number of leaves (nodes with no children) in bst.
Use: n = bst.leaf_count()
(Recursive algorithm)
---------------------------------------------------------
Preconditions:
node - a BST node (_BSTNode)
Postconditions:
returns:
n - number of nodes with no children below node.
---------------------------------------------------------
"""
count = 0
if node._left is None and node._right is None:
count += 1
if node._left is not None and node._right is None:
count += self._leaf_count_aux(node._left)
if node._left is None and node._right is not None:
count += self._leaf_count_aux(node._right)
if node._left is not None and node._right is not None:
count += self._leaf_count_aux(node._left)
count += self._leaf_count_aux(node._right)
return count
def _delete_node(self, node):
"""
-------------------------------------------------------
Removes a node from the bst.
Use: node = self._delete_node(node)
-------------------------------------------------------
Preconditions:
node - the bst node to be deleted (_BSTNode)
Postconditions:
returns:
node - the node that replaces the deleted node. This node is the node
with the maximum value in the current node's left subtree (_BSTNode)
-------------------------------------------------------
"""
# Your code here.
return node
def parent_i(self, key):
"""
---------------------------------------------------------
Returns the value of the parent node of a key node in a bst.
---------------------------------------------------------
Preconditions:
key - a key value (?)
Postconditions:
returns:
value - a copy of the value in a node that is the parent of the
key node, None if the key is not found.
---------------------------------------------------------
"""
# Your code here
return value
BST中的最后两个函数class、parent_i和_delete_node是我想写的，注释是我的老师为这些函数写的条件我们需要写。我想如果我找到一种方法来获取父级，那么删除功能应该很容易做到，但现在我不知道从哪里开始。帮助将不胜感激！此外，中间的几个功能，如 min_i 和 max_i 应该是这样的，可能是为了我们 class 中的未来作业或实验室供我们编写。
提前致谢！
编辑：好的，所以我现在理解了结构，但现在我很困惑如果我尝试删除一个有 2 个子节点的节点，而 2 个子节点中较高的一个也有 2 个子节点，等等上？我应该怎么做才能让它适用于所有大小的所有 bsts？
要确定节点的parent，将变量初始设置为
None。现在，当您对节点进行二进制搜索时，将该变量设置为您之前所在的任何节点，一旦您找到该节点 ，该变量就会给您 parent
当您尝试删除一个节点时，有您提到的3种情况。前 2 个很容易解决，只需用 1 child 替换删除的节点即可。 棘手的情况是当你有 2 children 时。 有两种方法可以解决这个问题，你可以用它的中序后继节点替换那个节点，即紧随其后的节点（最左边的 child 这个节点的右边 child），或者用它的inorder 前驱，即出现在这个节点之前的节点（该节点左侧 child 的最右侧 child）。
这只是对实际发生情况的快速 运行 了解，但现在您应该很明显不需要明确找到 parent一个节点为了删除该节点，只需在您前往需要删除的节点时跟踪前一个节点就足够了。
有关详细信息，请参阅此example