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

yipeiwu_com5年前Python基础

本文研究的主要是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的Bottle框架写一个简单的服务接口的示例

是不是有这么一个场景,对外提供一堆数据或者是要返回给用户一个结果。但是不想把内部的一些数据和逻辑暴露给对方。。。简单点来说,就是想以服务的方式对外提供一个接口。对于这种有很多处理方式,R...

Python编程scoketServer实现多线程同步实例代码

本文研究的主要是Python编程scoketServer实现多线程同步的相关内容,具体介绍如下。 开发过程中,为了实现不同的客户端同一时刻只能有一个使用共同数据。 虽说用Python编写...

Python+opencv+pyaudio实现带声音屏幕录制

基于个人的爱好和现实的需求,决定用Python做一个屏幕录制的脚本。因为要看一些加密的视频,每次都要登录,特别麻烦,遂决定用自己写的脚本,将加密视频的播放过程全程录制下来,这样以后看自己...

PyQt5 窗口切换与自定义对话框的实例

近日,需要实现一个功能小而全的桌面版软件,所以选中并尝试了PyQt5这个GUI库。在使用中发现,其功能的确完备,但这方面的资料的确不多,有时自己想实现的功能相关资料找不到,有的还不得不阅...

python中必要的名词解释

1.Django框架 Django是一个开放源代码的Web应用框架,由Python写成。它采用 了MVC的框架模式,即模型(M)、视图(V)和控制器(C)。相比 其他Web框架,Djan...