eightHundreds
1/21/2017 - 6:16 AM

二叉查找树实现

``````class SBTNode():
def __init__(self, value=None, parent=None, left=None, right=None):
self.left = left
self.parent = parent
self.right = right
self.value = value
# 使用魔法方法自定义比较运算符效果
def __gt__(self, other):
return self.value > other.value
def __ge__(self, other):
return self.value >= other.value
def __lt__(self, other):
return self.value < other.value
def __le__(self, other):
return self.value <= other.value
def __eq__(self, other):
# eq影响了==,!=,尤其是!=None被影响了
# eq的目的仅仅是为了与SBTNode比较,所以,当other不是SBTNode时候就照常执行
if type(other) == type(self):
return self.value == other.value
else:
super(SBTNode, self).__eq__(other)

class SBTree():
def __init__(self,traversal=lambda x:print(x)):
"""
:param traversal:遍历时用的,默认输出节点值
"""
self.root = None
self.traversal=traversal
def insert(self, key):
new_node = SBTNode(key)
temp_root = self.root  # type:SBTNode
temp = temp_root  # type:SBTNode

# 找到被插入的节点
while (temp != None):
temp_root = temp
if new_node < temp:
temp = temp.left
elif new_node > temp:
temp = temp.right
else:
raise ValueError('不可用插入重复数据')

new_node.parent = temp_root
if temp_root == None:  # 如果是第一次插入,即根节点为空
self.root = new_node
else:
if new_node > temp_root:
temp_root.right = new_node
else:
temp_root.left = new_node
def remove(self, key):
node=self.search(key)
if not node:
return None
temp1,temp2=None,None
#这一步找到要被删除的节点
if not node.left or not node.right:
temp1=node
else:
#如果左右孩子都不为空,找后继,下面的步骤就是删除这个后继
#最后一步把后继的值赋值给node,就这样用后继来替代node
temp1=self.successor(node)

# 下面是删除temp1

if temp1.left:
temp2=temp1.left
elif temp1.right:
temp2=temp1.right

if temp2:
temp2.parent=temp1.parent

if temp1.parent==None:
self.root=temp2
elif temp1.parent.left==temp1:
temp1.parent.left=temp2
else:
temp1.parent.right=temp2

if temp1!=node:
node.value=temp1.value
pass

def pre_order(self):
"""
前序遍历
:return:
"""
self._pre_order(self.root)
def in_order(self):
"""
中序遍历
:return:
"""
self._in_order(self.root)
def post_order(self):
"""
后序遍历
:return:
"""
self._post_order(self.root)
def successor(self, node: SBTNode):
"""
获得后继
:param node:
:return:
"""
#如果存在右孩子,那么其后继就是右孩子的最小子节点
if node.right:
return self.minimum(node.right)

temp=node.parent

# 如果没有右孩子:
# 该节点是个左孩子,那么他的父节点就是后继
# 该节点是个右孩子,那么向上查找若干次父节点,直到找到这样一个节点x
# node是x的左子树的一部分
while temp and node==temp.right:
node=temp
temp= temp.parent
return temp
def predecessor(self,node:SBTNode):
"""
获得前驱
:param node:
:return:
"""
#如果存在左孩子，则前驱结点为以其左孩子为根的子树的最大结点
if node.left:
return self.maximum(node.left)

temp=node.parent

# 如果没有左孩子:
# 该节点是个右孩子,那么他的父节点就是后继
# 该节点是个左孩子,那么向上查找若干次父节点,直到找到这样一个节点x
# node是x的右子树的一部分
while temp and node==temp.left:
node=temp
temp=temp.parent

return temp
def maximum(self,node:SBTNode):
"""
查找最大节点
:param node:
:return:
"""
if not node:
return None
while node.right:
node=node.right
return node
pass
def minimum(self,node:SBTNode):
"""
查找最小节点
:param node:
:return:
"""
if not node:
return None

while node.left:
node=node.left
return node

def print(self):
"""
打印树
:return:
"""
self._print(self.root, 0)
def iterative_search(self, key):
"""非递归查找"""
temp = self.root
while temp != None:
if key > temp.value:
temp = temp.right
elif key < temp.value:
temp = temp.left
else:
return temp
def destory(self,tree:SBTNode):
if tree==None:
return
if tree.left:
self.destory(tree.left)
if tree.right:
self.destory(tree.right)
tree=None
def clear(self):
self.destory(self.root)
self.root=None
def search(self, key):
if self.root != None:
return self._search(self.root, key)
def _print(self, node: SBTNode, direction):
"""
打印"二叉查找树"
:param node:
:param direction:
direction  0，表示该节点是根节点;
-1，表示该节点是它的父结点的左孩子;
1，表示该节点是它的父结点的右孩子。
:return:
"""
if node != None:
if direction == 0:
print('%s is root' % node.value)
else:
print('%s is %s %s child' % (node.value, node.parent.value, 'right' if direction == 1 else 'left'))
# 递归
self._print(node.left, -1)
self._print(node.right, 1)
def _search(self, node: SBTNode, key):
"""
查找节点对象(递归)
:param value:
:return:
"""
if node == None:
return node

if node.value == key:
return node
elif key > node.value:
return self._search(node.right, key)
else:
return self._search(node.left, key)
def _pre_order(self, node):
if node:
self.traversal(node.value)
self._pre_order(node.left)
self._pre_order(node.right)
pass
def _in_order(self,node):
if node:
self._in_order(node.left)
self.traversal(node.value)
self._in_order(node.right)
def _post_order(self,node):
if node:
self._post_order(node.left)
self._post_order(node.right)
self._post_order(node.right)
``````