专栏首页一英里广度一英寸深度的学习二叉树的插入和搜索--python实现

二叉树的插入和搜索--python实现

本文首先介绍了二分查找法,采用“循环”和“递归”2种方法实现。采用递归算法实现了二叉树的插入和搜索算法。

一、二分查找法

查找算法的计算复杂度为O(n)、O(logN)、O(1)。

  • 无序列表,顺序查找法时间复杂度为O(n)。
  • 排好序的结构,O(logN)
  • hash表,O(1)

二、二分查找法代码

循环方式

a = [x for x in range(100)]
target = 51

l=0 
r=100
while(l<=r):
    mid = (l+r)//2
    if(a[mid]>target):
        // 下一次循环[l,mid)
        r=mid
    elif(a[mid]<target):
        // [mid,r)
        l=mid+1
   //此时命中 
    else:
        print("target position:%d" % mid)
        break

递归实现

def binarySearch(l,r,target):
    mid = (l+r)//2
    if(a[mid]>target):
        r=mid
        return binarySearch(l,r,target)
    elif(a[mid]<target):
        l = mid+1
        return binarySearch(l,r,target)
    else:
        return mid
postion2 = binarySearch(0,100,50)
print(postion2) //50
postion3 = binarySearch(0,100,51)
print(postion3) //51

三、二叉树的搜索算法

在二分查找基于数组,在插入删除时需要移动较多节点,采用二叉树的数据结构,更好的实现插入、删除操作。

class BinarySearchTree2:
    #在此处定义的静态变量    
    def __init__(self):
        self.count=0
        self.root = None
        
    def count():
        return self.count
    
    def insert(self,key,value):
        if(self.count == 0):
            self.root = Node(key,value)
            self.count = self.count+1
            return
        else:
            node = self.root
            while True:
                if(node.key>key):
                    if(node.lnode == None):
                        node.lnode = Node(key,value)
                        return
                    else:
                        node = node.lnode
                elif(node.key<key):
                    if(node.rnode == None):
                        node.rnode = Node(key,value)
                        return
                    else:
                        node = node.rnode
    
    def contains(self,key):
        return self._contain(self.root,key)
    
    def _contain(self,node,key):
        if(node == None):
            return False
        if(node.key > key):
            return self._contain(node.lnode,key)
        elif(node.key < key):
            return self._contain(node.rnode,key)
        else:
            return True        

四、总结

查找算法是计算机中的基本问题,无论面试还是在日常工作中,都会经常遇到查找问题。本文,根据二分搜索算法用Python实现二叉树。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 线性排序算法-堆排序 (2)

    在学数据结构的时候,链表、堆栈、树三种数据结构印象最深刻。当时理解有误区,堆栈被当成一种结构,可能因为堆栈有同样的特性——只关心堆顶或栈顶的元素。

    birdskyws
  • Python 传值还是传引用

    如果 node =None,相当于node指向一个不可变对象,在调用insert函数时,仅传值。

    birdskyws
  • 二叉树添加删除节点Python

    采用递归调用实现二叉树添加、删除节点。文章采用Python对象引用方式实现指针结构的创建。

    birdskyws
  • 关键词爬虫,Python花瓣画板关键词采集存储数据库

    想要寻找图片的小伙伴们应该不会错过这个网站,对,没错,就是花瓣网,各种图片应有尽有,而花瓣网的推荐画板里面的词还是非常不错的,可惜被和谐了不少,想要采集花瓣画板...

    二爷
  • 用python做ppt服务用于导入图片

    项目需要做WINFORM程序与powerpoint交互,把winform生成的图片自动拷贝到ppt中。目前使用python做了一个简单的服务解决。由于要求是32...

    py3study
  • Python PyQt5整理介绍

    PyQt5 是Digia的一套Qt5应用框架与python的结合,同时支持2.x和3.x,官方网站:www.riverbankcomputing.co.uk/n...

    砸漏
  • python代码实现将列表中重复元素之间的内容全部滤除

    因为在学习遗传算法路径规划的内容,其中遗传算法中涉及到了种群的初始化,而在路径规划的种群初始化中,种群初始化就是先找到一条条从起点到终点的路径,也因此需要将路径...

    砸漏
  • 前端渲染引擎doT.js解析

    背景 前端渲染有很多框架,而且形式和内容在不断发生变化。这些演变的背后是设计模式的变化,而归根到底是功能划分逻辑的演变:MVC—>MVP—>MVVM(忽略最早混...

    美团技术团队
  • 智能网联汽车已经上路,ICT中国高层论坛搭建新赛道

    VRPinea
  • 多线程爪巴虫下载进击的巨人

    孤独的明月

扫码关注云+社区

领取腾讯云代金券