Python 实现二叉查找树的示例代码
二叉查找树
- 所有key小于V的都被存储在V的左子树
- 所有key大于V的都存储在V的右子树
BST的节点
classBSTNode(object): def__init__(self,key,value,left=None,right=None): self.key,self.value,self.left,self.right=key,value,left,right
二叉树查找
如何查找一个指定的节点呢，根据定义我们知道每个内部节点左子树的key都比它小，右子树的key都比它大，所以对于带查找的节点search_key，从根节点开始，如果search_key大于当前key，就去右子树查找，否则去左子树查找
NODE_LIST=[
{'key':60,'left':12,'right':90,'is_root':True},
{'key':12,'left':4,'right':41,'is_root':False},
{'key':4,'left':1,'right':None,'is_root':False},
{'key':1,'left':None,'right':None,'is_root':False},
{'key':41,'left':29,'right':None,'is_root':False},
{'key':29,'left':23,'right':37,'is_root':False},
{'key':23,'left':None,'right':None,'is_root':False},
{'key':37,'left':None,'right':None,'is_root':False},
{'key':90,'left':71,'right':100,'is_root':False},
{'key':71,'left':None,'right':84,'is_root':False},
{'key':100,'left':None,'right':None,'is_root':False},
{'key':84,'left':None,'right':None,'is_root':False},
]
classBSTNode(object):
def__init__(self,key,value,left=None,right=None):
self.key,self.value,self.left,self.right=key,value,left,right
classBST(object):
def__init__(self,root=None):
self.root=root
@classmethod
defbuild_from(cls,node_list):
cls.size=0
key_to_node_dict={}
fornode_dictinnode_list:
key=node_dict['key']
key_to_node_dict[key]=BSTNode(key,value=key)#这里值和key一样的
fornode_dictinnode_list:
key=node_dict['key']
node=key_to_node_dict[key]
ifnode_dict['is_root']:
root=node
node.left=key_to_node_dict.get(node_dict['left'])
node.right=key_to_node_dict.get(node_dict['right'])
cls.size+=1
returncls(root)
def_bst_search(self,subtree,key):
"""
subtree.key小于key则去右子树找因为左子树key:
self._bst_search(subtree.left,key)
else:
returnsubtree
defget(self,key,default=None):
"""
查找树
:paramkey:
:paramdefault:
:return:
"""
node=self._bst_search(self.root,key)
ifnodeisNone:
returndefault
else:
returnnode.value
def_bst_min_node(self,subtree):
"""
查找最小值的树
:paramsubtree:
:return:
"""
ifsubtreeisNone:
returnNone
elifsubtree.leftisNone:
#找到左子树的头
returnsubtree
else:
returnself._bst_min_node(subtree.left)
defbst_min(self):
"""
获取最小树的value
:return:
"""
node=self._bst_min_node(self.root)
ifnodeisNone:
returnNone
else:
returnnode.value
def_bst_max_node(self,subtree):
"""
查找最大值的树
:paramsubtree:
:return:
"""
ifsubtreeisNone:
returnNone
elifsubtree.rightisNone:
#找到右子树的头
returnsubtree
else:
returnself._bst_min_node(subtree.right)
defbst_max(self):
"""
获取最大树的value
:return:
"""
node=self._bst_max_node(self.root)
ifnodeisNone:
returnNone
else:
returnnode.value
def_bst_insert(self,subtree,key,value):
"""
二叉查找树插入
:paramsubtree:
:paramkey:
:paramvalue:
:return:
"""
#插入的节点一定是根节点，包括root为空的情况
ifsubtreeisNone:
subtree=BSTNode(key,value)
elifsubtree.key>key:
subtree.left=self._bst_insert(subtree.left,key,value)
elifsubtree.keykey:
subtree.right=self._bst_remove(subtree.right,key)
returnsubtree
elifsubtree.key
以上就是Python实现二叉查找树的示例代码的详细内容，更多关于Python实现二叉查找树的资料请关注毛票票其它相关文章！