二叉树、二分法-PySuper

二叉树

树

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

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

二叉树

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

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

二叉树有以下几个性质：
- 二叉树第 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)

目录 CONTENT

二叉树、二分法

二叉树

树

二叉树

案例

递归

递归与非递归的对比

二分法

index()

可变类型

二分法

评论区