一.堆
堆的建立可以通过导入heapq库来实现
在Python中建立的是最小堆 即heap[k]<=heap[2*k+1]and heap[k]<=heap[2*k+2]
下面是一些 堆使用的方法
heapq.heappush([],加入的元素) heapq.heappop(heap)弹出最小的元素 heapq.nlargest(3,heap)返回最大的三个元素 heapq.nsmallest(3,heap)返回最小的三个元素 heapq.heapify(my) #自动将列表装换成堆
例子:
import heapq ,random
data=list(range(10))
random.shuffle(data)
print(data)
#建堆
heap=[]
for i in data:
heapq.heappush(heap,i)
heapq.heappush(heap,99)#添加元素99
print(heap)
print(heapq.heappop(heap)) #弹出最小的元素
heapq.heapreplace(heap,3)#替换堆中最小的元素值,并自动重新建堆
print(heapq.nlargest(3,heap)) #返回最大的三个元素
print(heapq.nsmallest(3,heap)) #返回最小的三个元素
my=[2,0,4,3,12,15,5]
heapq.heapify(my) #自动将列表装换成堆
print(my)二.队列
通过导入queue模块实现
下面是一些 队列使用的方法
q=queue.Queue(6) #实例化队列 q.put(1) #元素入队 q.get()出队 q.empty()判断队列是否为空 q.full()判断队列是否为满
import queue
q=queue.Queue(6) #实例化队列
q.put(1) #元素入队
q.put(3)
q.put(10)
print(q.full())
print(q.get())
3.链表
可以通过列表来模拟.不过多讲解
4.二叉树
自己实现
class TreeNode:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
class BinaryTree:
def __init__(self):
self.root = None
def insert(self, key):
if self.root is None:
self.root = TreeNode(key)
else:
self._insert_recursive(self.root, key)
def _insert_recursive(self, current_node, key):
if key < current_node.key:
if current_node.left is None:
current_node.left = TreeNode(key)
else:
self._insert_recursive(current_node.left, key)
else:
if current_node.right is None:
current_node.right = TreeNode(key)
else:
self._insert_recursive(current_node.right, key)
def search(self, key):
return self._search_recursive(self.root, key)
def _search_recursive(self, current_node, key):
if current_node is None or current_node.key == key:
return current_node
elif key < current_node.key:
return self._search_recursive(current_node.left, key)
else:
return self._search_recursive(current_node.right, key)
def inorder_traversal(self):
return self._inorder_recursive(self.root)
def _inorder_recursive(self, current_node):
result = []
if current_node:
result.extend(self._inorder_recursive(current_node.left))
result.append(current_node.key)
result.extend(self._inorder_recursive(current_node.right))
return result
# 使用示例
tree = BinaryTree()
tree.insert(5)
tree.insert(3)
tree.insert(7)
tree.insert(2)
tree.insert(4)
tree.insert(6)
tree.insert(8)
print(tree.inorder_traversal()) # 输出：[2, 3, 4, 5, 6, 7, 8]
# 搜索示例
result = tree.search(4)
if result:
print(f"Key 4 found: {result.key}")
else:
print("Key 4 not found")
实现说明：
-
TreeNode类：
- 表示二叉树中的每个节点，具有一个
key属性存储节点的值，以及left和right属性分别指向左子节点和右子节点。
- 表示二叉树中的每个节点，具有一个
-
BinaryTree类：
- 使用
root属性表示树的根节点。 insert(key)方法用于插入新的节点到二叉树中。_insert_recursive(current_node, key)是递归插入方法，根据节点值大小决定向左子树或右子树插入新节点。search(key)方法用于搜索特定值的节点。_search_recursive(current_node, key)是递归搜索方法，根据节点值大小在左子树或右子树中搜索目标节点。inorder_traversal()方法实现中序遍历，返回一个按升序排列的节点值列表。_inorder_recursive(current_node)是递归实现的中序遍历方法。
- 使用
-
使用示例：
- 创建一个二叉搜索树（BST），插入一些节点并进行搜索和遍历操作。
- 输出示例展示了中序遍历的结果，以及如何搜索特定的节点。
这是一个基本的二叉树实现，可以根据需要扩展添加其他操作如删除节点、前序遍历、后序遍历等。
当我们对一个简单的二叉搜索树进行中序遍历时，可以通过以下步骤演示 _inorder_recursive() 方法的执行过程
初始调用
首先，我们从根节点 5 开始调用 _inorder_recursive() 方法：
-
调用
_inorder_recursive(5)current_node是5。result初始化为空列表[]。
-
处理左子树
_inorder_recursive(3)current_node是3。- 调用
_inorder_recursive(3)。
-
处理左子树
_inorder_recursive(2)current_node是2。- 调用
_inorder_recursive(2)。
-
返回空列表
[2]到_inorder_recursive(3)- 现在
result是[2]。 - 添加
3，返回[2, 3]到_inorder_recursive(5)。
- 现在
-
处理根节点
5- 现在
result是[2, 3]。 - 添加
5，成为[2, 3, 5]。
- 现在
-
处理右子树
_inorder_recursive(7)current_node是7。- 调用
_inorder_recursive(7)。
-
处理左子树
_inorder_recursive(6)current_node是6。- 调用
_inorder_recursive(6)。
-
返回空列表
[6]到_inorder_recursive(7)- 现在
result是[6]。 - 添加
7，返回[6, 7]到_inorder_recursive(5)。
- 现在
-
处理根节点
5- 现在
result是[2, 3, 5, 6, 7]。
- 现在
-
处理右子树
8current_node是8。- 调用
_inorder_recursive(8)。
-
返回空列表
[8]到_inorder_recursive(7)- 现在
result是[6, 7, 8]。 - 返回
[2, 3, 5, 6, 7, 8]到_inorder_recursive(5)。
- 现在
-
最终结果
- 最终返回
[2, 3, 4, 5, 6, 7, 8]，这是二叉搜索树中序遍历的结果。
- 最终返回
5.有向图
from collections import defaultdict
class WeightedGraph:
def __init__(self):
self.graph = defaultdict(list)
def add_edge(self, u, v, weight):
self.graph[u].append((v, weight))
# Uncomment below for undirected graph
# self.graph[v].append((u, weight))
def print_graph(self):
for node in self.graph:
print(f"{node} -> {self.graph[node]}")
# 创建一个新的带权图实例
graph = WeightedGraph()
# 添加带权边
graph.add_edge(0, 1, 4)
graph.add_edge(0, 2, 2)
graph.add_edge(1, 3, 1)
graph.add_edge(2, 3, 3)
# 打印邻接表表示的带权图
graph.print_graph()
