" name="sm-site-verification"/>
侧边栏壁纸
博主头像
PySuper博主等级

千里之行,始于足下

  • 累计撰写 203 篇文章
  • 累计创建 14 个标签
  • 累计收到 1 条评论

目 录CONTENT

文章目录

二叉树、二分法

PySuper
2020-03-20 / 0 评论 / 0 点赞 / 16 阅读 / 6668 字
温馨提示:
所有牛逼的人都有一段苦逼的岁月。 但是你只要像SB一样去坚持,终将牛逼!!! ✊✊✊

二叉树

树是一种数据结构,它是由n(n>=1)个有限节点组成一个具有层次关系的集合。

  • 树的特点:
    • 每个节点有零个或多个子节点
    • 没有父节点的节点称为根节点
    • 每一个非根节点有且只有一个父节点
    • 除了根节点外,每个子节点可以分为多个不相交的子树
  • 树的术语:
    • 结点的度:结点拥有的子树的数目。
    • 叶子:度为零的结点。
    • 分支结点:度不为零的结点。
    • 树的度:树中结点的最大的度。
    • 层次:根结点的层次为1,其余结点的层次等于该结点的双亲结点的层次加1。
    • 树的高度:树中结点的最大层次。
    • 无序树:如果树中结点的各子树之间的次序是不重要的,可以交换位置。
    • 有序树:如果树中结点的各子树之间的次序是重要的, 不可以交换位置。
    • 森林:0个或多个不相交的树组成。对森林加上一个根,森林即成为树;删去根,树即成为森林。

二叉树

每个节点最多有两个子树的树结构

  • 五种基本形态:
    • 跟和左右子树
    • 二叉树可以是空集
    • 根可以有空的左子树
    • 根可以有空的右子树
    • 左、右子树皆为空

<img src=“http://qny.zhengxingtao.com/media/images/BST_2.jpg”/ style=“max-width: 93%;”>

  • 二叉树有以下几个性质:
    • 二叉树第i层上的结点数目最多为 2{i-1} (i≥1)。
    • 深度为k的二叉树至多有2{k}-1个结点(k≥1)。
    • 包含n个结点的二叉树的高度至少为log2 (n+1)。
    • 在任意一棵二叉树中,若终端结点的个数为n0,度为2的结点数为n2,则n0=n2+1

案例

给定一个二叉树,判断其是否是一个有效的二叉搜索树

  • 一个二叉搜索树具有如下特征:
    • 节点的左子树只包含小于当前节点的数
    • 节点的右子树只包含大于当前节点的数
    • 所有左子树和右子树自身必须也是二叉搜索树
 class Solution(object):
    """
    从上往下比较的,将每个节点往左就是最大,往右就是最小值
    在传输过程中原函数不能够传递最大最小值,又重新定义了一个函数调用
    """
     def validBST(self, root, min, max):
         if root == None:
             return True
         if root.val <= min or root.val >= max:
             return False
         return self.validBST(root.left, min, root.val) and self.validBST(root.right, root.val, max)

     def isValidBST(self, root):
         """
         :type root: TreeNode
         :rtype: bool
         """
         return self.validBST(root, -21474836480, 21474836470)

递归

之前我对于需要重复使用的一个方法,总是使用回调的方式处理,而算法有种类似的处理方式–递归

递归就是在函数内部调用自己的函数被称之为递归

个人感觉递归就像是套娃

  • 递归的特点
    • 必须有一个明确的结束条件
    • 每次进入更深一层递归时,问题规模(计算量)相比上次递归都应有所减少
    • 递归效率不高,递归层次过多会导致栈溢出

在计算机中,函数调用是通过栈(stack)这种数据结构实现的,每当进入一个函数调用,栈就会加一层栈帧,每当函数返回,栈就会减一层栈帧。由于栈的大小不是无限的,所以,递归调用的次数过多,会导致栈溢出


def recursion(n):
    """将 10不断除以2,直至商为0,输出这个过程中每次得到的商的值"""

     # 每次求商,输出商的值
    v = n//2
    print(v)

    if v==0:
        return 'Done'    # 当商为0时,停止,返回Done
    
    # 递归调用,函数内自己调用自己
    v = recursion(v)

recursion(10) # 函数调用

递归与非递归的对比

# 非递归实现阶乘
def factorial(n):
    res = 1
    for i in range(2, n+1):
        res *= i
    return res 

print(factorial(4))

# 递归实现阶乘
def factorial(n):
    if n == 0 or n == 1: 
        return 1
    else: 
        return (n * factorial(n - 1))

print(factorial(5))

二分法

给定一个有序列表,获取其索引

index()

直接使用index获取,如果 i比较靠前,那么遍历列表的次数还可以接受

但是如果列表很长,同时 i 也在最后,这时的遍历就很费事了(时间复杂度)

def index_search(items, i):
    """使用内置方法,获取索引"""
    for num in items:
        if num == i:
            return items.index(num)

可变类型

列表是可变类型

我们遍历列表的同时队列表进行操作,第二次遍历的时候,列表会变成我们操作后的列表

def change_search(items, i):
    """未做是否在列表中的判断"""
    # 队列表删除后,列表中少一个值,通过计数获取在原列表中的index
    x = 0
    for num in items:
        if i > num:
            items.remove(num)
        elif i < num:
            # 每次删除一个,间隔一个,所以出现比 i 小的,那么 i 就一定在前一个
            return items.index(num) - 1 + x
        else:  # i = num
            return items.index(num) + x
        x += 1

二分法

二分法可以减少很多的比较次数

def binary_search(items, left, right, i):
    """二分查找: 对列表进行切片,每次比较确定 i 在左边还是右边"""

    # 判断是否在列表中
    if right >= left:
        mid = int(left + (right - left) / 2)
        
        # 刚好取到 i
        if items[mid] == i:
            return mid
        
        # i 小于中间位置的元素,只需要再比较左边的元素
        elif items[mid] > i:
            return binary_search(items, left, mid - 1, i)
        
        # i 大于中间位置的元素,只需要再比较右边的元素
        else:
            return binary_search(items, mid + 1, right, i)
    else:
        # 不存在
        return " {} 不在列表中!".format(i)


i = 7
items = [1, 2, 3, 4, 5, 6, 7, 8, 9]

result = binary_search(items, 0, len(items) - 1, i)
print(result)
0
  1. 支付宝打赏

    qrcode alipay
  2. 微信打赏

    qrcode weixin

评论区