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

栏目: 编程语言 · Python · 发布时间: 6年前

内容简介:这篇文章主要介绍了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
>>>

总结


以上就是本文的全部内容,希望本文的内容对大家的学习或者工作能带来一定的帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

神经网络在应用科学和工程中的应用

神经网络在应用科学和工程中的应用

萨马拉辛荷 / 2010-1 / 88.00元

《神经网络在应用科学与工程中的应用:从基本原理到复杂的模式识别》为读者提供了神经网络方面简单但却系统的介绍。 《神经网络在应用科学和工程中的应用从基本原理到复杂的模式识别》以神经网络在科学数据分析中所扮演角色的介绍性讨论作为开始,给出了神经网络的基本概念。《神经网络在应用科学和工程中的应用从基本原理到复杂的模式识别》首先对用于实际数据分析的神经网络结构进行了综合概述,继而对线性网络进行了大量......一起来看看 《神经网络在应用科学和工程中的应用》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

SHA 加密
SHA 加密

SHA 加密工具

Markdown 在线编辑器
Markdown 在线编辑器

Markdown 在线编辑器