[硕.Love Python] BinarySearchTree(二叉搜索树)
class Node(object):__slots__ = ['left', 'right', 'data']
def __init__(self, data, left=None, right=None):
self.data = data
self.left = left
self.right = right
def __str__(self):
sl = '%s <-' % self.left if self.left else ''
sr = '-> %s' % self.right if self.right else ''
return '[%s Node(%s) %s]' % (sl, self.data, sr)
class BinarySearchTree(object):
def __init__(self):
self.root = None
def insert(self, data):
node, parent = self.search(data, True)
if node:
raise ValueError('"%s" has been in tree.' % data)
node = Node(data)
if parent is None:
self.root = node
elif data < parent.data:
parent.left = node
else:
parent.right = node
def search(self, data, retParent=False):
parent = None
node = self.root
while node and node.data != data:
parent = node
if data < node.data:
node = node.left
else:
node = node.right
return (node, parent) if retParent else node
def delete(self, data):
self._deleteNode(*self.search(data, True))
def _findBiggest(self, node):
parent = None
while node.right:
parent = node
node = node.right
return node, parent
def _deleteNode(self, node, parent):
if node is None:
return
if node.left and node.right:
tmp, tmpParent = self._findBiggest(node.left)
if tmpParent is not None:
tmpParent.right = tmp.left
tmp.left = node.left
tmp.right = node.right
else:
tmp = node.left or node.right
if parent is None:
self.root = tmp
elif parent.left is node:
parent.left = tmp
else:
parent.right = tmp
if __name__ == '__main__':
bst = BinarySearchTree()
while True:
cmd = (raw_input('$ ')).strip().split()
if cmd == 'i':
bst.insert(int(cmd))
print bst.root
elif cmd == 'd':
bst.delete(int(cmd))
print bst.root
页:
[1]