BST Operations

写一个二叉树的各种operations。delete实在太难写了！我选择放弃！

class TreeNode(object):
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

    def __repr__(self):
        return repr(self.val) + ' ' + repr(self.left) + ' ' + repr(self.right)


class BST():
    def __init__(self, root=None):
        self.root = root

    def insert(self, val):
        node = TreeNode(val)
        if not self.root:
            self.root = node
            return

        self.find_n_insert(node, self.root)

    def find_n_insert(self, node, cur):
        if  node.val < cur.val:
            if not cur.left:
                cur.left = node
                return
            else:
                return self.find_n_insert(node, cur.left)

        if cur.val < node.val:
            if not cur.right:
                cur.right = node
                return
            else:
                return self.find_n_insert(node, cur.right)


    def search(self, val):
        cur = self.root
        while cur:
            if val == cur.val:
                return cur
            elif val < cur.val:
                cur = cur.left
            else:
                cur = cur.right
        return None


    def successor(self, val):
        cur = self.root
        successor = None
        while cur:
            if val < cur.val:
                successor = cur.val
                cur = cur.left
            else:
                cur = cur.right
        return successor


    def predecessor(self, val):
        cur = self.root
        predecessor = None
        while cur:
            if val > cur.val:
                predecessor = cur.val
                cur = cur.right
            else:
                cur = cur.left
        return predecessor


    def delete(self, val):
        # this is too hard, I gave up!
        root = self.search(val)
        if not root:
            return False

        # if node only has one child
        left, right = root.left, root.right
        if left and not right:
            root.val = left.val
            root.left = left.left
            root.right = left.right
        if right and not left:
            root.val = right.val
            root.left = right.left
            root.right = right.right

        # if node have two children
        rightMost = root.left
        pre = rightMost
        while rightMost and rightMost.right:
            pre = rightMost
            rightMost = rightMost.right
        root.val = rightMost.val

        # delete rightMost node
        left = rightMost.left
        if left:
            rightMost.val = left.val
            rightMost.left = left.left
            rightMost.right = left.right
        return True


tree = BST()
tree.insert(2);tree.insert(1);tree.insert(3);
print tree.root
print tree.search(3)
print tree.successor(2)
print tree.predecessor(2)
print tree.delete(1)