# -*- 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()