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