二叉樹的插入和搜尋--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實作二叉樹。