从栈、队列到二叉树遍历：5种数据结构在Python 3.12中的实现与复杂度分析

从栈、队列到二叉树遍历5种数据结构在Python 3.12中的实现与复杂度分析1. 数据结构基础与Python实现概览数据结构是计算机科学中组织和存储数据的系统化方式它直接影响程序的效率和性能。Python作为一门高级语言提供了丰富的内置数据类型但理解底层数据结构实现原理对开发者至关重要。在Python 3.12中我们可以用更简洁的语法实现经典数据结构。比如类型提示的增强让代码更具可读性class Stack[T]: def __init__(self) - None: self._items: list[T] []这种泛型写法明确表示了栈可以存储任何类型T的元素。我们将从最简单的线性结构开始逐步深入到非线性结构每种实现都包含核心操作的方法实现边界条件处理时间复杂度分析实际应用场景示例2. 栈(Stack)的实现与应用2.1 栈的基本实现栈遵循LIFO(后进先出)原则核心操作是push和pop。Python中可用列表模拟栈但为教学目的我们实现完整ADTclass Stack[T]: def __init__(self) - None: self._items: list[T] [] def push(self, item: T) - None: O(1)时间复杂度 self._items.append(item) def pop(self) - T: O(1)时间复杂度 if self.is_empty(): raise IndexError(pop from empty stack) return self._items.pop() def peek(self) - T: return self._items[-1] def is_empty(self) - bool: return len(self._items) 0 def size(self) - int: return len(self._items)注意实际使用中Python的list已经可以很好实现栈功能这里实现主要为了教学目的。2.2 栈的复杂度分析操作时间复杂度空间复杂度pushO(1)O(1)popO(1)O(1)peekO(1)O(1)2.3 栈的实际应用案例栈在计算机科学中应用广泛函数调用栈括号匹配检查浏览器前进后退功能表达式求值(逆波兰表示法)def is_balanced(expr: str) - bool: 检查括号是否匹配 stack Stack[str]() pairs {): (, ]: [, }: {} for char in expr: if char in pairs.values(): stack.push(char) elif char in pairs: if stack.is_empty() or stack.pop() ! pairs[char]: return False return stack.is_empty()3. 队列(Queue)的实现与变种3.1 基本队列实现队列遵循FIFO(先进先出)原则Python中可用collections.deque但我们实现基础版本class Queue[T]: def __init__(self) - None: self._items: list[T] [] def enqueue(self, item: T) - None: O(1)平均时间复杂度 self._items.append(item) def dequeue(self) - T: O(n)时间复杂度因为要移动元素 if self.is_empty(): raise IndexError(dequeue from empty queue) return self._items.pop(0) def is_empty(self) - bool: return len(self._items) 0 def size(self) - int: return len(self._items)3.2 循环队列优化为改善出队性能可使用循环队列class CircularQueue[T]: def __init__(self, capacity: int) - None: self._items: list[T | None] [None] * capacity self._front 0 self._rear -1 self._size 0 def enqueue(self, item: T) - None: if self.is_full(): raise OverflowError(Queue is full) self._rear (self._rear 1) % len(self._items) self._items[self._rear] item self._size 1 def dequeue(self) - T: if self.is_empty(): raise IndexError(dequeue from empty queue) item self._items[self._front] self._front (self._front 1) % len(self._items) self._size - 1 return item def is_empty(self) - bool: return self._size 0 def is_full(self) - bool: return self._size len(self._items)3.3 队列复杂度对比实现方式enqueuedequeue空间利用率普通队列O(1)O(n)低循环队列O(1)O(1)高Python dequeO(1)O(1)高4. 链表(Linked List)的实现4.1 单链表实现class Node[T]: def __init__(self, data: T): self.data: T data self.next: Node[T] | None None class LinkedList[T]: def __init__(self): self.head: Node[T] | None None def append(self, data: T) - None: O(n)时间复杂度 new_node Node(data) if not self.head: self.head new_node return last self.head while last.next: last last.next last.next new_node def prepend(self, data: T) - None: O(1)时间复杂度 new_node Node(data) new_node.next self.head self.head new_node def delete(self, key: T) - None: O(n)时间复杂度 current self.head if current and current.data key: self.head current.next return prev None while current and current.data ! key: prev current current current.next if current is None: return prev.next current.next4.2 链表与数组对比特性数组链表访问元素O(1)随机访问O(n)顺序访问插入/删除O(n)O(1)已知位置空间利用率高(连续内存)低(额外指针)缓存友好性好差5. 二叉树与遍历算法5.1 二叉树节点定义class TreeNode[T]: def __init__(self, value: T): self.value value self.left: TreeNode[T] | None None self.right: TreeNode[T] | None None5.2 三种深度优先遍历def preorder(root: TreeNode | None) - None: 前序遍历: 根-左-右 if root: print(root.value, end ) preorder(root.left) preorder(root.right) def inorder(root: TreeNode | None) - None: 中序遍历: 左-根-右 if root: inorder(root.left) print(root.value, end ) inorder(root.right) def postorder(root: TreeNode | None) - None: 后序遍历: 左-右-根 if root: postorder(root.left) postorder(root.right) print(root.value, end )5.3 广度优先遍历(层次遍历)from collections import deque def level_order(root: TreeNode | None) - None: 使用队列实现层次遍历 if not root: return queue deque([root]) while queue: node queue.popleft() print(node.value, end ) if node.left: queue.append(node.left) if node.right: queue.append(node.right)5.4 二叉树遍历复杂度所有遍历方式的时间复杂度都是O(n)因为每个节点访问一次。空间复杂度深度优先O(h)h为树高广度优先O(w)w为树的最大宽度6. 数据结构综合比较与应用选择6.1 时间复杂度汇总表数据结构插入删除查找访问栈(数组)O(1)O(1)O(n)O(1)顶部队列(循环)O(1)O(1)O(n)O(1)头部单链表O(1)头插O(1)头删O(n)O(n)二叉树(BST)O(h)O(h)O(h)O(h)6.2 实际应用场景建议栈适合需要撤销操作的场景如文本编辑、浏览器历史队列任务调度、消息传递等先进先出场景链表频繁插入删除的场景如实现队列、邻接表二叉树快速搜索(BST)、表达式树、文件系统结构# 示例用栈实现表达式求值 def evaluate_postfix(expr: str) - float: stack Stack[float]() for token in expr.split(): if token.replace(., ).isdigit(): stack.push(float(token)) else: b stack.pop() a stack.pop() if token : stack.push(a b) elif token -: stack.push(a - b) elif token *: stack.push(a * b) elif token /: stack.push(a / b) return stack.pop()