弄了一个很长的delete功能
def delete(self, key):
有什么办法弄滴短一点吗(见后面)?
而且很奇怪的是:
>>> newTree.printTree()
15
13
12
11
14
18
16
19
>>> newTree.delete(11)
>>> newTree.printTree()
# 11 根本没有被去掉,奇怪啊~~
15
13
12
11
14
18
16
19


class BinaryTree:

 def __init__(self, key, left=None, right=None, parent=None):
     self.key = key
     self.left = left
     self.right = right
     self.parent = parent
def delete(self, key):
        """Delete a node  from the tree.


        """
        node=self.getNode(key)
        if node:
            if node.right and node.left:
                # find left most node in right subtree
                """
                newleft = self.getMinNode(node.key)
                newleft.parent.left = None
                newleft.parent.right = newleft.right
                newleft.left = node.left
                newleft.right = node.right
                node.key = newleft.key
                """
                subNode = self.getMinNode(node.key)
                subNode.left = node.left
                # find maximum in subnode
                subMax = subNode.getMaxNode()
                # set its right child to right child of node that will be
                # deleted
                subMax.right = node.right
                node.right.left = None
                node.key = subNode.key
                node.right.parent = subMax
                node.right = subNode.right


            elif node.right:
                # replace node with child tree/
                node.key = node.right.key
                try:
                    node.left = node.right.left
                except:
                    node.left=None
                try:
                    node.right = node.right.right
                except:
                    node.right=None


            elif node.left:
                subNode= node.left
                if node.parent:
                    if node.parent.left:
                        if node.parent.left == node:
                            node.parent.left = subNode
                    if node.parent.right:
                        if node.parent.right == node:
                            node.parent.right = subNode
                else:
                    # at root
                    node.key = subNode.key
                    if subNode.left:
                        node.left=subNode.left
                    else:
                        node.left=None
                    if subNode.right:
                        node.right=subNode.right
                    else:
                        node.right=None


            elif node.right:
                subNode= node.right
                if node.parent:
                    if node.parent.left:
                        if node.parent.left == node:
                            node.parent.left = subNode
                    if node.parent.right:
                        if node.parent.right == node:
                            node.parent.right = subNode
                else:
                    node.key=subNode.key
                    if subNode.left:
                        node.left=subNode.left
                    else:
                        node.left=None
                    if subNode.right:
                        node.right=subNode.right
                    else:
                        node.right=None

            else:
                if node.parent:
                    if node.parent.left:
                        if node.parent.left == node:
                            node.parent.left=None
                    if node.parent.right:
                        if node.parent.right == node:
                            node.parent.right=None
        else:
            print 'no'

 def addNode(self,key):
     """Add a node in the proper location."""
     if key < self.key:
         if self.left:
             self.left.addNode(key)
         else:
             self.left = BinaryTree(key, parent=self)
     elif key > self.key:
         if self.right:
             self.right.addNode(key)
         else:
             self.right = BinaryTree(key, parent=self)

   def printTree(self):
       print self.key
       if self.left:
           self.left.printTree()
       if self.right:
           self.right.printTree()

    def getNode(self, key):
        """Get the node/subtree from the tree.

        Returns
            Node if node exisits
            None if not
        """
        if self.key == key:
            return self
        elif key < self.key:
            if self.left:
                return self.left.getNode(key)
            else:
                return
        elif key > self.key:
            if self.right:
                return self.right.getNode(key)
            else:
                return

    def getMaxNode(self):
        """return the maximum value node in the subtree"""
        if self.right:
            return self.right.getMaxNode()
        else:
            return self

    def getMinNode(self,root=None):
        """return the minimum valued node in the subtree.

        If root, then look for next largest value in the tree
        """
        if root:
            root = self.getNode(root)
            tree = root.right
            return tree.left.getMinNode()
        if self.left:
            return self.left.getMinNode()
        else:
            return self