使用python实现二叉搜索树

 class Node(object):
'''Tree's nodes factory'''
def __init__(self, value):
self.value = value
self.father = None

self.left = None
self.right = None
class Tree(object):
'''A search tree which has two children nodes'''
def __init__(self, nodes_list):
self.root = None
for node in nodes_list:
self.insert(node)def ergodic_middle(self):
def middle(node):
if node != None:
middle(node.left)
print node.value,
middle(node.right)
middle(self.root)

def search(self, value):
def _search(node, value):
current = node
while current != None and current.value != value:
if current.value > value:
current = current.left
else:
current = current.right
return current
return _search(self.root, value)

def _min(self, node):
current = node
while current.left != None:
current = current.left
return current

def min(self):
return self._min(self.root)

def _max(self, node):
current = node
while current.right != None:
current = current.right
return current

def max(self):
return self._max(self.root)

def next(self, node):
current = node
if current.right != None:
return self._min(current.right)
father = current.father
while father != Node and current == father.right:
current = father
father = father.father
return father

def pre(self, node):
current = node
if current.left != None:
return self._max(current.left)
father = current.father
while father != None and current == father.left:
current = father
father = father.father
return father

def insert(self, node):
father = None
current = self.root

while current != None:
if current.value == node.value:
raise ValueError('node.value is already in the search tree')
father = current
if node.value < current.value:
current = current.left
else:
current = current.right

node.father = father
if father == None:
self.root = node
elif node.value < father.value:
father.left = node
else:
father.right = node

def delete(self, node):
def _delete(tree, node):
if node.left == None and node.right == None:
_nochild(tree, node)
elif node.left == None and node.right != None:
_onechild(tree, node)
elif node.left != None and node.right == None:
_onechild(tree, node)
else:
_twochildren(tree, node)

def _nochild(tree, node):
if tree.root == node:
tree.root = None
else:
if node.value < node.father.value:
node.father.left = None
else:
node.father.right = None

def _onechild(tree, node):
if tree.root == node:
if node.right != None:
tree.root = node.right
else:
tree.root = node.left
else:
if node.right != None:
if node.value < node.father.value:
node.father.left = node.right
else:
node.father.right = node.right
node.right.father = node.father
else:
if node.value < node.father.value:
node.father.left = node.left
else:
node.father.right = node.left
node.left.father = node.father

def _twochildren(tree, node):
if tree.root == node:
next = self.next(node)
_delete(tree,next)
tree.root = next
next.left = node.left
next.right = node.right
node.left.father = next
node.right.father = next
else:
next = self.next(node)
_delete(tree,next)
if node.value < node.father.value:
node.father.left = next
else:
node.father.right = next
next.left = node.left
next.right = node.right
node.left.father = next
node.right.father = next

node_in_tree = self.search(node.value)
if node_in_tree and node_in_tree.left == node.left \
and node_in_tree.right == node.right \
and node_in_tree.father == node.father:
_delete(self, node)
else:
raise ValueError('No such Node')

weinxin
我的微信
有问题微信找我
DannyWu

发表评论

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

Protected with IP Blacklist CloudIP Blacklist Cloud