美文网首页数据结构和算法分析
二叉树的插入和搜索--python实现

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

作者: ac619467fef3 | 来源:发表于2018-08-20 13:16 被阅读25次

    本文首先介绍了二分查找法,采用“循环”和“递归”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实现二叉树。

    相关文章

      网友评论

        本文标题:二叉树的插入和搜索--python实现

        本文链接:https://www.haomeiwen.com/subject/pfdkiftx.html