我是相当新的在Python编程,我想作一个二叉搜索树的一些实施。我想添加的最后一个实现是,当用户选择我的'删除'功能时,无论他们想要删除什么项目,我的功能都会用最好的数字代替它。无论是继承人还是前任,为了使我的树平衡。 二叉搜索树,确定要使用前置或后续使树平衡
所以在这个例子中,用户希望'30'被删除。那么你会用什么替换它?我希望我的程序用'24'替换它,以使列表更加平衡,因为节点'24'的数量与另一侧的'52'相比。但是,它会随机选择一个,这会使45个超过30个我不想要的。
这里是我的树节点类:
class TreeNode(object):
def __init__(self, data = None, left=None, right=None):
self.item = data
self.left = left
self.right = right
def __str__(self):
return str(self.item)
这是我的主要功能,我修剪大部分除了我的删除功能和我的计算功能这可能使过程更容易,我觉得。
from TreeNode import TreeNode
class BST(object):
#------------------------------------------------------------
def __init__(self):
"""create empty binary search tree
post: empty tree created"""
self.root = None
self.size = 0
def delete(self, item):
"""remove item from binary search tree
post: item is removed from the tree"""
self.root = self._subtreeDelete(self.root, item)
#------------------------------------------------------------
def _subtreeDelete(self, root, item):
if root is None: # Empty tree, nothing to do
return None
if item < root.item: # modify left
root.left = self._subtreeDelete(root.left, item)
elif item > root.item: # modify right
root.right = self._subtreeDelete(root.right, item)
else: # delete root
if root.left is None: # promote right subtree
root = root.right
elif root.right is None: # promote left subtree
root = root.left
else:
# root node can't be deleted, overwrite it with max of
# left subtree and delete max node from the subtree
root.item, root.left = self._subtreeDelMax(root.left)
return root
def _subtreeDelMax(self, root):
if root.right is None: # root is the max
return root.item, root.left # return max and promote left subtree
else:
# max is in right subtree, recursively find and delete it
maxVal, root.right = self._subtreeDelMax(root.right)
return maxVal, root
def treeSize(self, root, size = 0):
if root is None:
return -1
if root is not None:
self.size += 1
if root.left is not None:
self.treeSize(root.left, size)
if root.right is not None:
self.treeSize(root.right, size)
return self.size
如果有人可以帮助我如何更改我的删除功能,以使其搜索正确的节点进行删除。谢谢!
编辑:我不知道这是否有助于但这里是我的测试代码也:
from BinarySearchTree import BST
from TreeNode import TreeNode
tree = TreeNode(4, TreeNode(2, TreeNode(1), TreeNode(3)), TreeNode (7, TreeNode(6),TreeNode(9, TreeNode(8), TreeNode(10))))
a = BST()
print("PRE-ORDER TRANSVERSE:")
print(a.preOrder(tree))
print("IN-ORDER TRANSVERSE:")
print(a.inOrder(tree))
print("POST-ORDER TRANSVERSE:")
print(a.postOrder(tree))
print("There are,", a.treeSize(tree),"nodes in this tree.")
所以基本上我的测试,它需要用“24”来代替“30”。