[硕.Love Python] BinarySearchTree(二叉搜索树)

cike0415

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