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[0] == 'i': bst.insert(int(cmd[1])) PRint bst.root elif cmd[0] == 'd': bst.delete(int(cmd[1])) print bst.root |
新闻热点
疑难解答
