在线视频网站开发方案php,wordpress自动封ip,装修网站建设优缺点,高端网络非线性结构(树状结构) 特点: 每个节点都可以有n个子节点(后继节点) 和 n个父节点(前驱节点) 代表: 树, 图...... 概述
属于数据结构之 非线性结构的一种, 父节点可以有多个子节点(后续节点)
特点 有且只有1个根节点 每个节点都可以有1个父节点及任意个子节点, 前提: 根节点除…非线性结构(树状结构) 特点: 每个节点都可以有n个子节点(后继节点) 和 n个父节点(前驱节点) 代表: 树, 图...... 概述
属于数据结构之 非线性结构的一种, 父节点可以有多个子节点(后续节点)
特点 有且只有1个根节点 每个节点都可以有1个父节点及任意个子节点, 前提: 根节点除外(没有父节点) 没有子节点的节点称之为: 叶子节点
二叉树概念和性质 每个节点最多只能有2个子节点 二叉树分类: 完全二叉树: 除了最后1层, 其他层的节点都是满的 满二叉树: 包括最后1层, 所有层的节点都是满的 不完全二叉树: 某层(不仅仅是最后1层)的节点数量不满
常用二叉树: 平衡二叉树: 防止树退化成链表, 指的是: 任意节点的两颗子树的高度差不超过1 排序二叉树: 主要是对元素排序的
存储方式
更推荐使用 链表的方式来存储, 每个节点有三部分组成, 分别是: 元素域(数值域), 左子树(地址域), 右子树(地址域)
针对于, 多叉树的情况, 可以将其转成二叉树, 然后再来存储
性质 在二叉树的第i层上至多有2i-1 个结点i0eg第3层最多结点个数2^((3-1)) 深度为k的二叉树至多有2k - 1个结点k0eg:层次2^((3))-1 7 对于任意一棵二叉树如果其叶结点数为N0而度数为2的结点总数为N2则N0 N21 最多有n个结点的完全二叉树的深度必为log2(n1) 对完全二叉树若从上至下、从左至右编号则编号为i的结点其左孩子编号必为2i其右孩子编号必为2i1,其父节点的编号必为i//2i1时为根,除外
二叉树的广度优先 广度优先可以找到最短路径 相当于层次遍历先把第层给遍历完看有没有终点再把第层遍历完看有没有重点 插入节点 初始操作 初始化队列、将根节点入队、准备加入到二叉树的新结点 重复执行 获得并弹出队头元素 1、若当前结点的左右子结点不为空则将其左右子节点入队列 2、若当前结点的左右子节点为空则将新结点挂到为空的左子结点、或者右子节点
图示 二叉树的深度优先 深度优先往往可以很快找到搜索路径 比如先找一个结点看看是不是终点若不是继续往深层去找直到找到终点。、中序先序后序属于深度优先算法 示例
层次(广度)遍历: 0123456789
先序遍历: 0137849256 根 左 右
中序遍历: 7381940526 左 根 右
后序遍历: 7839415620 左 右 根
图示 二叉树代码演示
# 创建节点类
class Node(object):# 初始化属性def __init__(self, item):self.item item # 数值域self.lchild None # 左子树(地址域)self.rchild None # 左子树(地址域)
# 创建二叉树类
class BinaryTree(object):def __init__(self, root: Node None):self.root root # 根节点
# 添加元素函数(完全二叉树)def add(self, item):# 判断根节点是否为空if self.root is None:self.root Node(item)return# 根节点不为空, 找到缺失节点# 创建队列, 用于记录已存在的节点queue []# 把根节点添加到队列queue.append(self.root)# 循环遍历队列, 直至 把新元素添加到合适的位置while True:# 获取队列中的第一个元素node queue.pop(0)# 左子树为空if node.lchild is None:node.lchild Node(item)return # 结束添加动作else:# 左子树存在, 就将其添加到队列中queue.append(node.lchild)# 右子树为空if node.rchild is None:node.rchild Node(item)return # 结束添加动作else:# 右子树存在, 就将其添加到队列中queue.append(node.rchild)
# 广度优先def breadth_travel(self):# 判断根节点是否为空if self.root is None:return # 为空直接结束# 创建队列, 记录所有节点queue []# 将根节点, 添加到队列中queue.append(self.root)# 只要队列长度大于0, 就说明还有节点, 循环遍历while len(queue) 0:# 获取队列中的第一元素node queue.pop(0)# 输出当前节点print(node.item, end\t)# 判断当前节点的左子树是否为空if node.lchild is not None:# 不为空, 则将左子树入队queue.append(node.lchild)# 判断当前节点的右子树是否为空if node.rchild is not None:# 不为空, 则将左子树入队queue.append(node.rchild)
# 深度优先: 先序(根左右)def preorder_travel(self, root):# 判断根节点是否不为空if root is not None:# 中序先输出根节点print(root.item, end\t)# 递归左子树self.preorder_travel(root.lchild)# 递归右子树self.preorder_travel(root.rchild)
# 深度优先: 中序(左根右)def mid_travel(self, root):if root is not None:self.mid_travel(root.lchild)print(root.item, end\t)self.mid_travel(root.rchild)
# 深度优先: 后序(左右根)def poster_travel(self, root):if root is not None:self.poster_travel(root.lchild)self.poster_travel(root.rchild)print(root.item, end\t)
三. 算法 排序类相关 稳定性: 排序前后的相对位置(相同的元素位置)是否发生变化 稳定排序: 冒泡排序、插入排序、归并排序和基数排序 不稳定排序: 选择排序、快速排序、希尔排序、堆排序 冒泡排序
原理
相邻元素两辆比较, 大的往后走, 这样第一轮比较完毕后, 最大值就在最大索引处
核心 比较的总轮数 列表长度 - 1 每轮比较的总次数 列表长度 - 1 - 轮数(从0 开始) 谁和谁比较(交换) j 和 j 1 比较
图解 代码
def buble_sort(my_list):# 定义变量n存储列表长度n len(my_list)# 比较的轮数for i in range(n - 1): # i: 0, 1, 2, 3# 记录交换的次数count 0# 每轮比较的次数for j in range(n - 1 - i): # j: 4, 3, 2, 1if my_list[j] my_list[j 1]:# 交换时计数器加一count 1my_list[j], my_list[j 1] my_list[j 1], my_list[j]print(f第 {i} 轮交换了 {count} 次)# 如果当前轮次交换了0次, 则跳出外循环if count 0:break
if __name__ __main__:list1 [2, 1, 4, 5, 3]buble_sort(list1)print(list1, list1)print(- * 21)
list2 [5, 3, 4, 7, 2]buble_sort(list2)print(list2, list2)
冒泡总结
时间复杂度: 最优O(n), 最差O(n²)
遍历一遍发现没有任何元素发生了位置交换,终止排序
算法稳定性:稳定算法 选择排序
原理
第一轮: 假设索引为0的元素时最小值, 依次和后续的元素比较, 只要比该值小, 就纪录住真正最小值的那个索引, 第一轮比较完毕后, 把最小值放到索引为0的位置即可
第二轮: 假设索引为1的元素时最小值, 依次和后续的元素比较, 只要比该值小, 就纪录住真正最小值的那个索引, 第一轮比较完毕后, 把最小值放到索引为1的位置即可
......
解释:
选择排序就是把符合要求的数据选择出来进行排序
核心 比较的总轮数 列表长度 - 1 每轮比较的总次数 i 1 ~ 列表的最后1个元素 谁和谁比较(交换) j 和 min_index 位置的元素比较
比较过程
具体的比较过程, 假设共 5 个元素 比较的轮数 每轮比较的总次数 谁和谁比较 第0轮 4 0和1, 0和2, 0和3, 0和4 第1轮 3 1和2, 1和3, 1和4 第2轮 2 2和3, 2和4 第3轮 1 3和4
代码
def select_sort(my_list):# 定义变量n存储列表长度n len(my_list)# 比较的轮数for i in range(n - 1): # i: 0, 1, 2, 3# 记录最小值索引min_idx i# 每轮比较的次数for j in range(i 1, n): # j: 4, 3, 2, 1# 判断min_idx后的元素是否比min_idx小if my_list[j] my_list[min_idx]:# 将最小值索引设为jmin_idx j# 如果最小值索引等于i说明i的位置是正确的,不交换if min_idx ! i:# 交换my_list[i], my_list[min_idx] my_list[min_idx], my_list[i]
if __name__ __main__:list1 [2, 1, 4, 5, 3]select_sort(list1)print(list1, list1)print(- * 21)
list2 [5, 3, 4, 7, 2]select_sort(list2)print(list2, list2)
选择总结
算法稳定性: 不稳定算法
时间复杂度: 最优: O(n²), 最差: O(n²) 插入排序
原理
把要排序的列表分成两部分, 第一部分是有序的(拍好序的), 第二部分是无序的(待排序的), 然后从待排序的列表中, 依次取出每个值, 插入到 排好序的列表的 合适位置 .
核心 比较的总轮数 列表长度 - 1 for i in range(1, n) 每轮比较的总次数 i ~ 0(逆向遍历) for i in range(i, 0, -1) 谁和谁比较(交换) i 和 j 的每个值 比较
比较过程
具体的比较过程, 假设共 5 个元素 比较的轮数 每轮比较的总次数 谁和谁比较 第1轮 4 1和0 第2轮 3 2和1, 2和0 第3轮 2 3和2, 3和1, 3和0 第4轮 1 4和3, 4和2, 4和1, 4和0
代码
def insert_sort(my_list):# 定义变量n存储列表长度n len(my_list)# 比较的轮数for i in range(1, n): # i: 1, 2, 3, 4# 每轮比较的次数for j in range(i, 0, -1): # j: 1 2,1 3,2,1 4,3,2,1# 判断当前元素(待排序)是否比前面的元素(排好序的)小if my_list[j] my_list[j - 1]:# 交换当前元素和当前元素的前一个元素my_list[j], my_list[j - 1] my_list[j - 1], my_list[j]else:break
if __name__ __main__:list1 [2, 1, 4, 5, 3]insert_sort(list1)print(list1, list1)print(- * 21)
list2 [5, 3, 4, 7, 2]insert_sort(list2)print(list2, list2)
插入总结
算法稳定性: 稳定算法
时间复杂度: 最优: O(n) 最坏: O(n²) 查找类相关(二分查找) 此处只记录二分查找, 并非查找只有二分查找这一种 介绍 概述: 他是一种高效的查找类算法, 也叫: 折半查找 细节: 要被查找的列表必须是有序的 原理: 获取列表的中间位置的元素, 然后和要查找的元素进行比较 如果相等, 直接返回结果即可 如果比中间值小, 去 中间前 范围查找 如果比中间值大, 去 中间后 范围查找 递归版
def binary_search(my_list, item):n len(my_list)if n 0:return Falsemid n // 2if item my_list[mid]:return Trueelif item my_list[mid]:return binary_search(my_list[:mid], item)else:return binary_search(my_list[mid 1:], item) 非递归版
def binary_search(my_list, item):# 计算列表长度n len(my_list)# 定义初始起始位置为0start 0# 定义初始终止位置为列表长度减1end n - 1# 当起始位置大于终止位置时结束循环while start end:# 定义中间位置为起始位置加终止位置除2mid (start end) // 2# 判断中间索引位置的元素是否为要查找的元素if my_list[mid] item:return True# 判断中间索引位置的元素比要查找的位置小elif my_list[mid] item:# 设置起始位置索引为中间位置加1start mid 1# 判断中间索引位置的元素比要查找的位置大else:# 设置终止位置索引为中间位置减1end mid - 1return False
if __name__ __main__:list1 [1, 2, 3, 4, 5, 6, 7]print(binary_search(list1, 4))
总结 必须采用顺序存储结构 必须按关键字大小有序排列 时间复杂度: 最优: O(1) 最坏: O(logn)
