提交网站收录,宣传网页,wordpress插件的开发,网站建设评审1.队列
1.普通队列
queue.Queue 是 Python 标准库 queue 模块中的一个类#xff0c;适用于多线程环境。它实现了线程安全的 FIFO#xff08;先进先出#xff09;队列。
2.双端队列
双端队列#xff08;Deque#xff0c;Double-Ended Queue#xff09;是一种具有队列和…1.队列
1.普通队列
queue.Queue 是 Python 标准库 queue 模块中的一个类适用于多线程环境。它实现了线程安全的 FIFO先进先出队列。
2.双端队列
双端队列DequeDouble-Ended Queue是一种具有队列和栈性质的数据结构它允许我们在两端进行元素的添加push和移除pop操作。在Python中双端队列可以通过collections模块中的deque类来实现。
deque是一个双端队列的实现它提供了在两端快速添加和移除元素的能力。
当结合使用appendleft和popleft时你实际上是在实现一个栈Stack的数据结构因为栈是后进先出LIFO的而这两个操作正好模拟了栈的“压栈”和“弹栈”行为。append和pop结合使用同理。
3.优先队列
优先队列Priority Queue是一种特殊的队列其中的元素按照优先级进行排序。优先级最高的元素总是最先出队。Python 标准库中提供了 queue.PriorityQueue 和 heapq 模块来实现优先队列。
queue.PriorityQueue
queue.PriorityQueue 是 Python 标准库 queue 模块中的一个类适用于多线程环境。它实现了线程安全的优先队列。
heapq
heapq 模块是 Python 标准库中的一个模块提供了基于堆的优先队列实现。heapq 模块不是线程安全的适用于单线程环境。
代码示例
import queue
from collections import deque
import heapqdef pd_queue():# 普通队列 队尾入队 对头出队# put()入队# get() 出队q queue.Queue()q.put(55)q.put(44)q.put(33)print(q.qsize())print(q.get())print(q.get())print(q.get())# deque 双端队列 既可以在队尾进行入队和出队操作# 也可以在队头进行入队和出队操作# append()在队尾入队# appendleft()在队头入队# pop()在队尾出队# popleft()在队头出队# appendleft()和popleft()组合使用时 相当于栈的操作# append()和pop()同理dq deque()dq.append(10)dq.append(20)dq.appendleft(30)dq.appendleft(40)print(dq.popleft())print(dq.popleft())print(dq.popleft())print(dq.popleft())print(----------------------------------------)pq queue.PriorityQueue()pq.put((2,item2))pq.put((1,item1))pq.put((4,item4))pq.put((3,item3))print(pq.get())print(pq.get())print(pq.get())print(pq.get())print(----------------------------------------)# headq 优先队列 基于堆实现的 要预先定义一个数组作为heap堆对象 线程不安全# heappush() 向队中添加元素元组(优先级 元素值) 优先级的数值越小heap []heapq.heappush(heap, (1,hq1))heapq.heappush(heap, (3,hq3))heapq.heappush(heap, (2,hq2))heapq.heappush(heap, (4,hq4))print(heapq.heappop(heap))print(heapq.heappop(heap))print(heapq.heappop(heap))print(heapq.heappop(heap))
if __name__ __main__:pd_queue()
2.树
1.概念
1.术语
在描述树的各个部分的时候有很多术语。 为了让介绍的内容更容易理解, 需要知道一些树的术语. 不过大部分术语都与真实世界的树相关, 或者和家庭关系相关(如父节点和子节点), 所以它们比较容易理解.
我们先来看一下树的结构 2.树的定义 树Tree: nn≥0个结点构成的有限集合。 当n0时称为空树 对于任一棵非空树n 0它具备以下性质 树中有一个称为“根Root”的特殊结点用 root 表示 其余结点可分为m(m0)个互不相交的有限集T1T2... Tm其中每个集合本身又是一棵树称为原来树的“子树SubTree” 注意: 子树之间不可以相交 除了根结点外每个结点有且仅有一个父结点 一棵N个结点的树有N-1条边。
3.树的术语: 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.二叉树
1.概念
二叉树的定义
二叉树可以为空, 也就是没有结点.若不为空则它是由根结点和称为其左子树TL和右子树TR的两个不相交的二叉树组成。
二叉树有五种形态:
注意c和d是不同的二叉树, 因为二叉树是有左右之分的. 2.特性
二叉树有几个比较重要的特性, 在笔试题中比较常见:
一个二叉树第 i 层的最大结点数为2^(i-1), i 1;深度为k的二叉树有最大结点总数为 2^k - 1, k 1;对任何非空二叉树 T若n0表示叶结点的个数、n2是度为2的非叶结点个数那么两者满足关系n0 n2 1。 3.特殊的二叉树
1.满二叉树(Full Binary Tree
在二叉树中, 除了最下一层的叶结点外, 每层节点都有2个子结点, 就构成了满二叉树. 2.完全二叉树(Complete Binary Tree)
除二叉树最后一层外, 其他各层的节点数都达到最大个数.且最后一层从左向右的叶结点连续存在, 只缺右侧若干节点.满二叉树是特殊的完全二叉树.下面不是完全二叉树, 因为D节点还没有右结点, 但是E节点就有了左右节点.
4.二叉树的存储
二叉树的存储常见的方式是链表.
链表存储:
二叉树最常见的方式还是使用链表存储.每个结点封装成一个Node, Node中包含存储的数据, 左结点的引用, 右结点的引用. 5.二叉树遍历
前序遍历Pre-order Traversal、中序遍历In-order Traversal和后序遍历Post-order Traversal是二叉树的三种基本遍历方式。
遍历规则
前序遍历按照以下顺序访问节点根节点、左子树、右子树。中序遍历按照以下顺序访问节点左子树、根节点、右子树。后序遍历按照以下顺序访问节点左子树、右子树、根节点。
3.二叉查找树
二叉查找树Binary Search Tree, BST是一种特殊的二叉树它具有以下性质
每个节点都有一个键值key。对于每个节点其左子树中的所有节点的键值都小于该节点的键值。对于每个节点其右子树中的所有节点的键值都大于该节点的键值。左子树和右子树也分别是二叉查找树。二叉查找树不允许出现键值相等的结点。
二叉查找树的主要操作包括插入、删除和遍历。
1.创建二叉查找树
class TreeNode:def __init__(self, key):self.key keyself.left Noneself.right None 参数说明 key: 节点的键值。 left: 指向左子节点的指针。 right: 指向右子节点的指针。
2.创建二叉查找树
class BinarySearchTree:def __init__(self):self.root None root: 指向二叉搜索树的根节点。初始时为 None。
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): 递归插入方法。根据键值的大小递归地在左子树或右子树中插入新节点。
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)
5.删除节点
删除逻辑
1.递归查找待删除节点 如果待删除节点的键值小于当前节点的键值递归地在左子树中查找并删除。 如果待删除节点的键值大于当前节点的键值递归地在右子树中查找并删除。
2.找到待删除节点
删除操作的步骤可以分为以下几种情况 待删除节点是叶子节点没有子节点直接删除该节点。 待删除节点只有一个子节点用其子节点替换该节点。 待删除节点有两个子节点 找到右子树中的最小节点即后继节点。 用后继节点的键值替换待删除节点的键值。 删除后继节点后继节点要么是叶子节点要么只有一个右子节点。 def _remove(self, node, key):# 如果树为空则返回Noneif node is None:return None# 判断指定的key和当前节点的key的大小 如果指定的key小于当前节点的key 则递归遍历左子树# 如果指定的key大于当前节点的key 则递归遍历右子树if key node.key:node.left self._remove(node.left, key)elif key node.key:node.right self._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.right# 如果右子树为空 则返回左子树elif node.right is None:return node.left# 如果当前节点右两个子树 则查询当前节点右子树的左子树找到最小值节点# 将最小值替换到当前节点 将最小值节点递归删除else:temp self._min_value_node(node.right)node.key temp.key# 以当前节点的右子树节点为根节点 删除最小值节点node.right self._remove(node.right,temp.key)return node# 查找当前节点的最小值 最小值在当前节点的左子树中def _min_value_node(self,node):current nodewhile current.left is not None:current current.leftreturn node6.遍历
遍历规则
前序遍历按照以下顺序访问节点根节点、左子树、右子树。
中序遍历按照以下顺序访问节点左子树、根节点、右子树。
后序遍历按照以下顺序访问节点左子树、右子树、根节点。 # 中序遍历def inorder_search(self):result []self._inorder_search(self.root,result)return resultdef _inorder_search(self,node,result):if node:self._inorder_search(node.left,result)result.append(node.key)self._inorder_search(node.right,result)# 前序遍历def preorder_search(self):result []if self.root is None:return Noneself._preorder_search(self.root,result)return resultdef _preorder_search(self,node,result):if node:result.append(node.key)self._preorder_search(node.left, result)self._preorder_search(node.right, result)# 后序遍历def afterorder_search(self):result []self._afterorder_search(self.root, result)return resultdef _afterorder_search(self, node, result):if node:self._afterorder_search(node.left, result)self._afterorder_search(node.right, result)result.append(node.key)整个代码实现 # 定义二叉查找树节点
class TreeNode:def __init__(self, key):self.key keyself.left Noneself.right Noneclass BST:def __init__(self,):self.root Nonedef 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:# node.left表示当前节点的左子树节点self._insert(node.left,key)# 如果要插入的键值大于当前节点的键值# 则判断当前节点是否有右子树 没有则将新节点赋给当前节点的右子树# 有则继续向当前节点的右子树移动 递归插入else :if node.right is None:node.right TreeNode(key)else:self._insert(node.right, key)# 中序遍历def inorder_search(self):result []self._inorder_search(self.root,result)return resultdef _inorder_search(self,node,result):if node:self._inorder_search(node.left,result)result.append(node.key)self._inorder_search(node.right,result)# 前序遍历def preorder_search(self):result []if self.root is None:return Noneself._preorder_search(self.root,result)return resultdef _preorder_search(self,node,result):if node:result.append(node.key)self._preorder_search(node.left, result)self._preorder_search(node.right, result)# 后序遍历def afterorder_search(self):result []self._afterorder_search(self.root, result)return resultdef _afterorder_search(self, node, result):if node:self._afterorder_search(node.left, result)self._afterorder_search(node.right, result)result.append(node.key)def remove_bst(self, key):self.root self._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.left self._remove(node.left, key)elif key node.key:node.right self._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.right# 如果右子树为空 则返回左子树elif node.right is None:return node.left# 如果当前节点右两个子树 则查询当前节点右子树的左子树找到最小值节点# 将最小值替换到当前节点 将最小值节点递归删除else:temp self._min_value_node(node.right)node.key temp.key# 以当前节点的右子树节点为根节点 删除最小值节点node.right self._remove(node.right,temp.key)return node# 查找当前节点的最小值 最小值在当前节点的左子树中def _min_value_node(self,node):current nodewhile current.left is not None:current current.leftreturn nodeif __name__ __main__:bst BST()bst.insert(3)bst.insert(1)bst.insert(2)bst.insert(5)bst.insert(4)# result bst.inorder_search()# result bst.preorder_search()result bst.afterorder_search()print(result)
