开锁公司做网站,怎么填写网站icp备案,cname域名解析,制作网页的2.3 队列
队列(Queue)#xff0c;它是一种运算受限的线性表,先进先出(FIFO First In First Out) 队列是一种受限的线性结构 受限之处在于它只允许在表的前端#xff08;front#xff09;进行删除操作#xff0c;而在表的后端#xff08;rear#xff09;进行插入操作 P…2.3 队列
队列(Queue)它是一种运算受限的线性表,先进先出(FIFO First In First Out) 队列是一种受限的线性结构 受限之处在于它只允许在表的前端front进行删除操作而在表的后端rear进行插入操作 Python标准库中的queue模块提供了多种队列实现包括普通队列、双端队列、优先队列等。
当两个程序效率不一样时可以用队列作为缓冲池提高系统性能把同步操作变成异步操作。生产者-消费者模式。
redis可以存数组
2.3.1 普通队列
queue.Queue 是 Python 标准库 queue 模块中的一个类适用于多线程环境。它实现了线程安全的 FIFO先进先出队列。
案例
import queue
q queue.Queue()
q.put(1)
q.put(3)
q.put(2)
print(q.qsize())
print(q.get())
print(q.get())
print(q.get())
2.3.2 双端队列
双端队列DequeDouble-Ended Queue是一种具有队列和栈性质的数据结构它允许我们在两端进行元素的添加push和移除pop操作。在Python中双端队列可以通过collections模块中的deque类来实现。
deque是一个双端队列的实现它提供了在两端快速添加和移除元素的能力。
案例
from collections import deque
q deque()
q.append(1)
q.append(2)
q.appendleft(3)
q.appendleft(4)
print(q.pop())
print(q.popleft())
当结合使用appendleft和popleft时你实际上是在实现一个栈Stack的数据结构因为栈是后进先出LIFO的而这两个操作正好模拟了栈的“压栈”和“弹栈”行为。append和pop结合使用同理。
2.3.3 优先队列
优先队列Priority Queue是一种特殊的队列其中的元素按照优先级进行排序。优先级最高的元素总是最先出队。Python 标准库中提供了 queue.PriorityQueue 和 heapq 模块来实现优先队列。
queue.PriorityQueue
queue.PriorityQueue 是 Python 标准库 queue 模块中的一个类适用于多线程环境。它实现了线程安全的优先队列。
案例
import queue
q queue.PriorityQueue()
# 向队列中添加元素元素是一个元组 (priority, item)其中 priority 是优先级item 是实际的数据
q.put((1,item1))
q.put((3,item3))
q.put((2,item2))
print(q.get())
print(q.get())
print(q.get())
heapq
heapq 模块是 Python 标准库中的一个模块提供了基于堆的优先队列实现。heapq 模块不是线程安全的适用于单线程环境。
案例
import heapq
# 创建一个列表作为堆
heap []
# 向堆中添加元素元素是一个元组 (priority, item)
heapq.heappush(heap, (3, Task 3))
heapq.heappush(heap, (1, Task 1))
heapq.heappush(heap, (2, Task 2))
# 从堆中取出元素
print(heapq.heappop(heap)) # 输出: (1, Task 1)
print(heapq.heappop(heap)) # 输出: (2, Task 2)
print(heapq.heappop(heap)) # 输出: (3, Task 3)
import queue
from collections import deque
import heapq
def pd_queue():#Queue:普通队列从队尾入队从队头出队#put():入队#get():出队qqueue.Queue()q.put(1)q.put(2)q.put(3)
print(q.get())print(q.get())print(q.get())
#deque:双端队列既可以在队尾进行入队和出队操作也可以在队头进行入队和出队操作
#append():在队尾入队
#appendleft():在队头入队
#pop():在队尾出队
#popleft():在队头出队
#appendleft和popleft组合使用时相当于栈的操作
#appned和pop组合使用同理dqdeque()dq.append(1)dq.append(2)dq.appendleft(3)dq.appendleft(4)
print(dq.popleft())print(dq.popleft())print(dq.popleft())print(dq.popleft())
#PriorityQueue:优先队列参数元组优先级元素优先级的数值越小优先级越高pqqueue.PriorityQueue()pq.put((1,item1))pq.put((3, item2))pq.put((3, item3))
print(--------------)print(pq.get())print(pq.get())print(pq.get())
#heapq:优先队列基于堆实现的预先定义一个数组作为heap对象线程不安全#heappush参数1heap是预先定义的堆参数2向队中添加优先级的元素元祖优先级元素值优先级的数值越小优先级越高#heappopheap参数heap是预先定义的堆heap[ ]heapq.heappush(heap,(1,hq1))heapq.heappush(heap,(3,hq2))heapq.heappush(heap,(2,hq3))
print(-----------)print(heapq.heappop(heap))print(heapq.heappop(heap))print(heapq.heappop(heap))
if __name____main__:pd_queue
2.4 树
2.4.1 概念和术语
模拟树结构 将组织架构里的数据移除, 抽象出来结构, 那么就是我们要学习的树结构 术语
树的结构 树的定义: 树Tree: nn≥0个结点构成的有限集合。 当n0时称为空树 对于任一棵非空树n 0它具备以下性质 树中有一个称为“根Root”的特殊结点用 root 表示 其余结点可分为m(m0)个互不相交的有限集T1T2... Tm其中每个集合本身又是一棵树称为原来树的“子树SubTree” 注意: 子树之间不可以相交 除了根结点外每个结点有且仅有一个父结点 一棵N个结点的树有N-1条边。
树的术语: 1.结点的度Degree该结点的拥有的子节点数量。 2.树的度树的所有结点中最大的度数. (树的度通常为结点的个数N-1) 3.叶子结点Leaf度为0的结点. (也称为叶子结点) 4.父结点Parent有子树的结点是其子树的根结点的父结点 5.子结点Child若A结点是B结点的父结点则称B结点是A结点的子结点子结点也称孩子结点。 6.兄弟结点Sibling具有同一父结点的各结点彼此是兄弟结点。 7.路径和路径长度从结点n1到nk的路径为一个结点序列n1 , n2,… , nk, ni是 ni1的父结点。路径所包含边的个数为路径的长度。 8.结点的层次Level规定根结点在1层其它任一结点的层数是其父结点的层数加1。 9.树的深度Depth树中所有结点中的最大层次是这棵树的深度。
2.4.2 二叉树
2.4.2.1 概念
二叉树的定义 二叉树可以为空, 也就是没有结点. 若不为空则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树有五种形态: 注意c和d是不同的二叉树, 因为二叉树是有左右之分的.
2.4.2.2 特性 二叉树有几个比较重要的特性, 在笔试题中比较常见: 一个二叉树第 i 层的最大结点数为2^(i-1), i 1; 深度为k的二叉树有最大结点总数为 2^k - 1, k 1; 对任何非空二叉树 T若n0表示叶结点的个数、n2是度为2的非叶结点个数那么两者满足关系n0 n2 1。
2.4.2.3 特殊的二叉树
满二叉树(Full Binary Tree 在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树. 完全二叉树(Complete Binary Tree) 除二叉树最后一层外, 其他各层的节点数都达到最大个数. 且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点. 满二叉树是特殊的完全二叉树. 下面不是完全二叉树, 因为D节点还没有右结点, 但是E节点就有了左右节点.
2.4.2.4 二叉树的存储
二叉树的存储常见的方式是链表.
链表存储: 二叉树最常见的方式还是使用链表存储. 每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用. 2.4.2.5 二叉树遍历
前序遍历Pre-order Traversal、中序遍历In-order Traversal和后序遍历Post-order Traversal是二叉树的三种基本遍历方式。
遍历规则
前序遍历按照以下顺序访问节点根节点、左子树、右子树。
中序遍历按照以下顺序访问节点左子树、根节点、右子树。
后序遍历按照以下顺序访问节点左子树、右子树、根节点。
2.4.3 二叉查找树
二叉查找树Binary Search Tree, BST是一种特殊的二叉树它具有以下性质 每个节点都有一个键值key。 对于每个节点其左子树中的所有节点的键值都小于该节点的键值。 对于每个节点其右子树中的所有节点的键值都大于该节点的键值。 左子树和右子树也分别是二叉查找树。 二叉查找树不允许出现键值相等的结点。 二叉查找树的主要操作包括插入、删除和遍历。代码实现如下
2.4.3.1 创建二叉查找树节点
class TreeNode:def __init__(self, key):self.key keyself.left Noneself.right None key: 节点的键值。 left: 指向左子节点的指针。 right: 指向右子节点的指针。
2.4.3.2 创建二叉查找树类
class BinarySearchTree:def __init__(self):self.root None root: 指向二叉搜索树的根节点。初始时为 None。
2.4.3.3 插入节点
插入操作的步骤 如果树为空直接将新节点作为根节点。 如果树不为空 从根节点开始根据新节点的键值与当前节点的键值的比较结果决定向左子树还是右子树移动。 如果新节点的键值小于当前节点的键值如果当前节点没有左子树则将新节点插入到当前节点的左子树否则向左子树移动。 如果新节点的键值大于当前节点的键值如果当前节点没有右子树则将新节点插入到当前节点的右子树否则向右子树移动。 重复上述步骤直到找到一个空位置将新节点插入到该位置。
def insert(self, key):if self.root is None:self.root TreeNode(key)else:self._insert(self.root, key)
def _insert(self, node, key):if key node.key:if node.left is None:node.left TreeNode(key)else:self._insert(node.left, key)elif key node.key:if node.right is None:node.right TreeNode(key)else:self._insert(node.right, key) insert(key): 公开的插入方法。如果树为空则创建一个新节点作为根节点否则调用 _insert 方法进行递归插入。 _insert(node, key): 递归插入方法。根据键值的大小递归地在左子树或右子树中插入新节点。
2.4.3.4 查找节点
def search(self, key):return self._search(self.root, key)
def _search(self, node, key):if node is None or node.key key:return nodeif key node.key:return self._search(node.left, key)return self._search(node.right, key)
2.4.3.5 删除节点
删除逻辑
1.递归查找待删除节点 如果待删除节点的键值小于当前节点的键值递归地在左子树中查找并删除。 如果待删除节点的键值大于当前节点的键值递归地在右子树中查找并删除。
2.找到待删除节点
删除操作的步骤可以分为以下几种情况 待删除节点是叶子节点没有子节点直接删除该节点。 待删除节点只有一个子节点用其子节点替换该节点。 待删除节点有两个子节点 找到右子树中的最小节点即后继节点。 用后继节点的键值替换待删除节点的键值。 删除后继节点后继节点要么是叶子节点要么只有一个右子节点。
假设我们有以下二叉搜索树 50/ \30 70/ \ / \20 40 60 80
删除节点 20 找到键值为 20 的节点。 该节点是叶子节点直接删除。
删除后的树 50/ \30 70\ / \40 60 80
删除节点 30 找到键值为 30 的节点。 该节点有一个右子节点 40用 40 替换 30。
删除后的树 50/ \40 70/ \60 80
删除节点 50 找到键值为 50 的节点。 该节点有两个子节点找到右子树中的最小节点 60即后继节点。 用 60 替换 50。 删除右子树中的 60。
删除后的树 60/ \40 70\80
def delete(self, key):self.root self._delete(self.root, key)
def _delete(self, node, key):if node is None:return node
if key node.key:node.left self._delete(node.left, key)elif key node.key:node.right self._delete(node.right, key)else:# 找到要删除的节点# 情况 1: 节点是叶子节点if node.left is None and node.right is None:return None# 情况 2: 节点只有一个子节点elif node.left is None:return node.rightelif node.right is None:return node.left# 情况 3: 节点有两个子节点temp self._min_value_node(node.right)node.key temp.keynode.right self._delete(node.right, temp.key)
return node
def _min_value_node(self, node):current nodewhile current.left is not None:current current.leftreturn current
2.4.3.6 中序遍历
先遍历左子树然后访问当前节点最后遍历右子树。
def inorder_traversal(self):result []self._inorder_traversal(self.root, result)return result
def _inorder_traversal(self, node, result):if node:self._inorder_traversal(node.left, result)result.append(node.key)self._inorder_traversal(node.right, result)
2.4.3.7 前序遍历
先访问根节点、然后遍历左子树、最后遍历右子树。
def preorder_search(self):result []if self.root is None:return Noneself._preorder_search(self.root, result)return result
def _preorder_search(self,node,result):if node is None:return Noneresult.append(node.key)self._preorder_search(node.left,result)self._preorder_search(node.right,result)# 后序遍历按照以下顺序访问节点左子树、右子树、根节点。def _behind_search(self, node, result):if node:self._behind_search(node.left, result)self._behind_search(node.right, result)result.append(node.key)
def remove(self,key):if self.root is None:return Noneself.rootself._remove(self.root,key)
class TreeNode:def __init__(self,key):self.keykeyself.leftNoneself.rightNone
class BST:def __init__(self):self.rootNone
def insert(self,key):#判断树是否为空是则将新节点赋给根节点if self.root is None:self.rootTreeNode(key)else:self._insert(self.root,key)
def _insert(self,node,key):#如果要插入的键值小于当前节点的键值则判断当前节点是否有左子树没有则将新节点赋给当前节点的左子树#有则继续向当前节点的左子树移动递归插入if keynode.key:if node.left is None:node.leftTreeNode(key)else:#node.left当前节点的左子树节点self._insert(node.left,key)#如果要插入的键值大于当前节点的键值则判断当前节点是否有右子树没有则将新节点插入到当前节点的右子树#有则继续向当前节点的右子树移动递归插入else:if node.right is None:node.rightTreeNode(key)else:self._insert(node.right,key)
def inorder_search(self):result[ ]self._inorder_search(self.root,result)return result#中序遍历左子树、根、右子树def _inorder_search(self,node,result):if node:self._inorder_search(node.left,result)result.append(node.key)self._inorder_search(node.right,result)
def frontorder_search(self):result[ ]if self.root is None:return Noneself._front_search(self.root,result)return result
# 前序遍历按照以下顺序访问节点根节点、左子树、右子树。def _front_search(self, node, result):if node is None:return Noneelse:result.append(node.key)self._front_search(node.left, result)self._front_search(node.right, result)
def behindorder_search(self):result[ ]self._behind_search(self.root,result)return result
# 后序遍历按照以下顺序访问节点左子树、右子树、根节点。def _behind_search(self, node, result):if node:self._behind_search(node.left, result)self._behind_search(node.right, result)result.append(node.key)
def remove(self,key):if self.root is None:return Noneself.rootself._remove(self.root,key)
def _remove(self,node,key):#如果树为空则返回Noneif node is None:return None#判断指定的key和当前节点的key的大小如果指定key小于当前节点的key则递归遍历左子树#如果指定key大于当前节点的key则递归遍历右子树if key node.key:node.leftself._remove(node.left,key)elif key node.key:node.rightself._remove(node.right,key)#指定key等于当前节点的key#1.当前节点没有子节点则直接删除返回None#2.当前节点有一个子节点1.有右子节点则用右子节点替换当前节点2.有左子结点则用左子结点替换当前节点#3.当前节点有两个子节点查找当前节点右子树的左子树找到最小值用最小值节点替换当前节点删除最小值节点else:#如果当前节点左右子树都为空则返回Noneif node.left is None and node.right is None:return None#如果当前节点只有一个子树如果左子树为空则返回右子树节点如果右子树节点为空则返回左子树节点elif node.left is None:return node.rightelif node.right is None:return node.left#如果当前节点有两个子树则查询当前节点右子树的左子树找到最小值节点#将最小值替换到当前节点#将最小值节点递归删除else:tempself._min_value_node(node.right)node.keytemp.key#以当前节点的右子树节点为根节点删除最小值节点node.rightself._remove(node.right,temp.key)
return node#查找当前节点的最小值最小值在当前节点的左子树中def _min_value_node(self,node):while node.left is not None:nodenode.leftreturn node
if __name____main__:bstBST()bst.insert(5)bst.insert(8)bst.insert(3)bst.insert(2)bst.insert(7)bst.insert(4)
resultbst.inorder_search()print(result)result1 bst.frontorder_search()print(result1)result2 bst.behindorder_search()print(result2)
# bst.remove(4)# resultbst.inorder_search()# print(result)
