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

birdskyws

发布于 2018-09-12 15:03:54

1.3K0

发布于 2018-09-12 15:03:54

文章被收录于专栏：一英里广度一英寸深度的学习

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