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实现二叉查找树实例代码的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！

赞 (0)

相关推荐

  • python实现画一颗树和一片森林

    python实现画一颗树和一片森林

    本文实例为大家分享了python画一颗树和一片森林的具体代码,供大家参考,具体内容如下 实现效果 代码在这里 from turtle import Turtle def tree(plist, l, a, f): """ :param plist:画笔列表,指数型增加 :param l: 画笔的长度,同时也是递归终止条件,注意下面的引用中是字母l,不是数字1 :param a: 分开的两个树杈之间夹角的一半,固定值65° :param f: 子树与父树的比值 :return:

  • python使用turtle库绘制树

    本文实例为大家分享了python使用turtle库绘制树的具体代码,供大家参考,具体内容如下 # -*- coding: utf-8 -*- """ Spyder Editor This is a temporary script file. """ import turtle, datetime def drawGap(): #绘制数码管间隔 turtle.penup() turtle.fd(5) def drawLine(draw): #绘制

  • python递归函数绘制分形树的方法

    python递归函数绘制分形树的方法

    分形几何学的基本思想:客观事物具有自相似性的层次结构,局部和整体在形态,功能,信息,时间,空间等方面具有统计意义上的相似性,称为自相似性,自相似性是指局部是整体成比例缩小的性质. 我们先看一下我们最终要绘制的图形: 案例分析: 代码: ## 绘制分型树,末梢的树枝的颜色不同 import turtle def draw_brach(brach_length): if brach_length > 5: if brach_length < 40: turtle.color('green') el

  • Python+Turtle动态绘制一棵树实例分享

    Python+Turtle动态绘制一棵树实例分享

    本文实例主要是对turtle的使用,实现Python+turtle动态绘制一棵树的实例,具体代码: # drawtree.py from turtle import Turtle, mainloop def tree(plist, l, a, f): """ plist is list of pens l is length of branch a is half of the angle between 2 branches f is factor by which bra

  • python使用turtle绘制分形树

    python使用turtle绘制分形树

    由于分形树具有对称性,自相似性,所以我们可以用递归来完成绘制.只要确定开始树枝长.每层树枝的减短长度和树枝分叉的角度,我们就可以把分形树画出来啦!! 代码如下: # -*- coding: utf-8 -*- ''' 绘制分形树 ''' import turtle as tl def draw_smalltree(tree_length,tree_angle): ''' 绘制分形树函数 ''' if tree_length >= 3: tl.forward(tree_length) #往前画 t

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

    本文研究的主要是python实现二叉查找树的相关内容,具体介绍及实现如下. 1. 二叉查找树的定义: 左子树不为空的时候,左子树的结点值小于根节点,右子树不为空时,右子树的结点值大于根节点,左右子树分别为二叉查找树 2. 二叉查找树的最左边的结点即为最小值,要查找最小值,只需遍历左子树的结点直到为空为止,同理,最右边的结点结尾最大值,要查找最大值,只需遍历右子树的结点直到为空为止.二叉查找树的插入查找和删除都是通过递归的方式来实现的,删除一个结点的时候,先找到这个结点S,如果这个结点左右孩子都不

  • Python 实现链表实例代码

    Python 实现链表实例代码 前言 算法和数据结构是一个亘古不变的话题,作为一个程序员,掌握常用的数据结构实现是非常非常的有必要的. 实现清单 实现链表,本质上和语言是无关的.但是灵活度却和实现它的语言密切相关.今天用Python来实现一下,包含如下操作: ['addNode(self, data)'] ['append(self, value)'] ['prepend(self, value)'] ['insert(self, index, value)'] ['delNode(self,

  • java 二叉查找树实例代码

    java 二叉查找树实例代码 1.左边<中间<右边 2.前序遍历 左中右 3.中序遍历 中左右 4.后序遍历 左右中 public class BinaryTree { // 二叉树的根节点 public TreeNode rootNode ; // 记录搜索深度 public int count; /** * 利用传入一个数组来建立二叉树 */ public BinaryTree(int[] data) { for (int i = 0; i < data. length; i++)

  • python matplotlib画图实例代码分享

    python matplotlib画图实例代码分享

    python的matplotlib包支持我们画图,有点非常多,现学习如下. 首先要导入包,在以后的示例中默认已经导入这两个包 import matplotlib.pyplot as plt import numpy as np 然后画一个最基本的图 t = np.arange(0.0, 2.0, 0.01)#x轴上的点,0到2之间以0.01为间隔 s = np.sin(2*np.pi*t)#y轴为正弦 plt.plot(t, s)#画图 plt.xlabel('time (s)')#x轴标签 p

  • python验证码识别实例代码

    本文研究的主要是Python验证码识别的相关代码,具体如下. Talk is cheap, show you the Code! import numpy as np import matplotlib.pyplot as plt from sklearn.cluster import KMeans from PIL import Image #打开图像 im=np.array(Image.open('yzm.png')) #得到图像3个维度 h,w,san=im.shape X=[(h-x,y

  • Python操作Mysql实例代码教程在线版(查询手册)

    Python操作Mysql实例代码教程在线版(查询手册)

    实例1.取得MYSQL的版本在windows环境下安装mysql模块用于python开发 MySQL-python Windows下EXE安装文件下载 复制代码 代码如下: # -*- coding: UTF-8 -*- #安装MYSQL DB for pythonimport MySQLdb as mdb con = None try:    #连接mysql的方法:connect('ip','user','password','dbname')    con = mdb.connect('l

  • Python 流程控制实例代码

    首先,介绍if-else条件语句.if语句是用来根据表达式的真假来有选择的执行特定的程序块,控制程序的流程.用法同java等语言.对于else if,有一个elif的简写方式. 例如: 复制代码 代码如下: if x > 3: print("greater") elif x == 3: print("eq") else: print("small") 接下来介绍while语句.while语句的作用是在条件表达式为真时,重复执行特定的程序块.

  • Python图片裁剪实例代码(如头像裁剪)

    Python图片裁剪实例代码(如头像裁剪)

    今天就来说个常用的功能,图片裁剪,可用于头像裁剪啊之类的.用的还是我们之前用的哪个模块pillow 1. 安装pillow 用pip安装 pip install pillow 2. 图片裁剪 2.1 准备一张图片 2.2 我们使用的是Image中的crop(box)功能,它需要一个参数box,元组 类型,元组包括4个元素,如: (距离图片左边界距离x, 距离图片上边界距离y,距离图片左边界距离+裁剪框宽度x+w,距离图片上边界距离+裁剪框高度y+h) 如图:(x, y, x+w, y+h), x

  • python双向链表实现实例代码

    python双向链表实现实例代码

    示意图: python双向链表实现代码: 复制代码 代码如下: #!/usr/bin/python# -*- coding: utf-8 -*- class Node(object):    def __init__(self,val,p=0):        self.data = val        self.next = p        self.prev = p class LinkList(object):    def __init__(self):        self.he

  • python学习数据结构实例代码

    在学习python的过程中,用来练习代码,并且复习数据结构的 #coding:utf-8 #author:Elvis class Stack(object): def __init__(self, size=8): self.stack = [] self.size = size self.top = -1 def is_empty(self): if self.top == -1: return True else: return False def is_full(self): if sel

随机推荐