python实现二叉查找树

sharpds77

　　这次用完成的是二叉树，是一种简单的树型结构。同样使用python实现 多的不说了，上代码吧。

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