python

超轻量级php框架startmvc

python实现二叉查找树实例代码

更新时间:2020-05-21 18:54:01 作者:startmvc
本文研究的主要是python实现二叉查找树的相关内容,具体介绍及实现如下。1.二叉查找树的

本文研究的主要是python实现二叉查找树的相关内容,具体介绍及实现如下。

1. 二叉查找树的定义:

左子树不为空的时候,左子树的结点值小于根节点,右子树不为空时,右子树的结点值大于根节点,左右子树分别为二叉查找树

2. 二叉查找树的最左边的结点即为最小值,要查找最小值,只需遍历左子树的结点直到为空为止,同理,最右边的结点结尾最大值,要查找最大值,只需遍历右子树的结点直到为空为止。二叉查找树的插入查找和删除都是通过递归的方式来实现的,删除一个结点的时候,先找到这个结点S,如果这个结点左右孩子都不为空,这时并不是真正的删除这个结点S,而是在其右子树找到后继结点,将后继结点的值付给S,然后删除这个后继结点即可。如果结点S的左孩子或者右孩子为空,可以直接删除这个结点S。

3. 二叉查找树的python实现:


class TreeNode: 
 def __init__(self,val): 
 self.val=val; 
 self.left=None; 
 self.right=None; 
def insert(root,val): 
 if root is None: 
 root=TreeNode(val); 
 else: 
 if val<root.val: 
 root.left=insert(root.left,val); #递归地插入元素 
 elif val>root.val: 
 root.right=insert(root.right,val); 
 return root; 
 
def query(root,val): 
 if root is None: 
 return ; 
 if root.val is val: 
 return 1; 
 if root.val <val: 
 return query(root.right,val); #递归地查询 
 else: 
 return query(root.left,val); 
def findmin(root): 
 if root.left: 
 return findmin(root.left); 
 else: 
 return root; 
 
def delnum(root,val): 
 if root is None: 
 return ; 
 if val<root.val: 
 return delnum(root.left,val); 
 elif val>root.val: 
 return delnum(root.right,val); 
 else: # 删除要区分左右孩子是否为空的情况 
 if(root.left and root.right): 
 
 tmp=finmin(root.right); #找到后继结点 
 root.val=tmp.val; 
 root.right=delnum(root.right,val); #实际删除的是这个后继结点 
 
 else: 
 if root.left is None: 
 root=root.right; 
 elif root.right is None: 
 root=root.left; 
 return root; 
 
 
#测试代码 
root=TreeNode(3); 
root=insert(root,2); 
root=insert(root,1); 
root=insert(root,4); 
 
#print query(root,3); 
print query(root,1); 
root=delnum(root,1); 
print query(root,1); 

结果:

1 None >>>

总结

以上就是本文关于python实现二叉查找树实例代码的全部内容,希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

python实现二叉树代码 python 二叉树查找 python查找二叉树删除 python实例代码 python 词二叉树查找