# -*- coding: cp936 -*-
#---------------------------------------------
#                                             
# author  chile                                   
# version  1.0                                
# date  2014-02-17                                       
# desc 二叉树                      
#                                             
#                                            
#                                            
#---------------------------------------------
class bintree:
    def __init__(self):
        self.root = None
        
    # 前驱节点
    def treePredecessor(self,entry):
        if entry.left != None:
            return self.maxTree(entry.left)
        preNode = entry.parent
        tempNode = entry
        while preNode != None and preNode.right.value != entry.value:
            tempNode = preNode
            preNode = preNode.parent
        return preNode
        
    
    #后继节点      
    def treeSuccessor(self,entry):
        if entry.right != None:
            return self.minTree(entry.right)
        preNode = entry.parent
        tempNode = entry
        while preNode != None and preNode.left.value != entry.value:
            tempNode = preNode
            preNode = preNode.parent
        return preNode
    
    def add(self,value):
        tempNode = self.root
        parentNode = None
        entry = bintree.entry(value = value)
        while tempNode != None:
            parentNode = tempNode
            if cmp(value,parentNode.value) < 0:
                tempNode = tempNode.left
            else:
                tempNode = tempNode.right
        if parentNode == None:
            self.root = entry
        elif cmp(value,parentNode.value) < 0:
            parentNode.left = entry
            entry.parent = parentNode
        else:
            parentNode.right = entry
            entry.parent = parentNode
    
    #这里删除是全部删除节点（包括所有子节点）
    def remove(self,value):
        root = self.root
        parentNode = None
        if value == root.value:
            root.left = None
            root.right = None
        while root != None:
            parentNode = root.parent
            if value == root.value:
                root.left = None
                root.right = None
                if parentNode.left != None and parentNode.left.value == value:
                    parentNode.left = None
                    break
                else:
                    parentNode.right = None
                    break
            elif cmp(value,root.value) < 0:
                root = root.left
            else:
                root = root.right
    
    #查找节点
    def search(self,value):
        root = self.root
        while root != None and root.value != value:
            if cmp(value,root.value) < 0:
                root = root.left
            else:
                root = root.right
        return root
    
    #最小值的节点，其实就是找左边的叶子节点
    def minTree(self,root):
        entry = root
        while entry.left != None:
            entry = entry.left
        return entry
    
    #最大值的节点
    def maxTree(self,root):
        entry = root
        while entry.right != None:
            entry = entry.right
        return entry
                
    
    #中序遍历
    def iterator(self,root):
        if root != None:
            self.iterator(root.left)
            print root.value
            self.iterator(root.right)
        
    
    class entry:
        def __init__(self, value=None):
            self.left = None
            self.right = None
            self.parent = None
            self.value = value
            
arr = [15,5,3,12,10,13,6,7,16,20,18,23]
tree = bintree()
for val in arr:
    tree.add(val)
 
tree.iterator(tree.root)
node = tree.search(16)
print node.left , node.right , node.parent.value
print tree.maxTree(node).value
print tree.treePredecessor(node).value
print tree.treeSuccessor(node).value
#print tree.maxTree() , tree.minTree()