1. 二叉树基础与遍历实战第一次接触二叉树时我被它的递归定义惊艳到了——每个节点最多有两个孩子左右子树又是一棵二叉树。这种自我相似的特性让二叉树成为解决分层数据的利器。记得刚学遍历算法时我总混淆前序、中序、后序的区别直到用下面这个例子才彻底明白假设我们要遍历这样一棵二叉树A / \ B C / \ \ D E F前序遍历根左右就像初次拜访节点A→B→D→E→C→F中序遍历左根右像把树压扁后从左到右读D→B→E→A→C→F后序遍历左右根则像离开时的告别D→E→B→F→C→A用Python实现递归遍历特别简洁class Node: def __init__(self, value): self.left None self.right None self.value value def preorder(root): if root: print(root.value, end ) preorder(root.left) preorder(root.right) # 中序和后序只需调整print语句位置但递归在深度大的树上可能栈溢出这时非递归版本就更安全。我常用栈模拟递归过程比如非递归中序遍历def inorder_stack(root): stack [] while stack or root: while root: stack.append(root) root root.left root stack.pop() print(root.value, end ) root root.right2. 从遍历序列重建二叉树工作中遇到过这样的需求已知某二叉树的中序和前序遍历序列要求重建原树结构。这就像玩拼图需要找准分割点给定前序 [A,B,D,E,C,F]中序 [D,B,E,A,C,F]重建步骤前序首元素A是根节点在中序中找到A左侧[D,B,E]是左子树右侧[C,F]是右子树递归处理左右子树代码实现时需要注意边界条件def build_tree(preorder, inorder): if not preorder: return None root_val preorder[0] root Node(root_val) idx inorder.index(root_val) root.left build_tree(preorder[1:idx1], inorder[:idx]) root.right build_tree(preorder[idx1:], inorder[idx1:]) return root3. 哈夫曼树的构建奥秘哈夫曼树在文件压缩中大显身手。我曾用它优化过日志存储系统压缩率能达到30%。它的核心思想是让高频字符用短编码低频字符用长编码。构建过程就像搭积木将各节点视为单节点树按权值放入最小堆每次取出权值最小的两棵树合并新树权值为两者之和重复直到只剩一棵树手动模拟这个过程很有趣。比如给定权重[5,9,12,13,16,45]第一次合并5和9新节点14第二次取12和13合并得25接着合并14和16得到30然后合并25和30得到55最后合并45和55完成构建用优先队列实现的Python代码import heapq class HuffmanNode: def __init__(self, weight, charNone): self.left None self.right None self.weight weight self.char char def __lt__(self, other): return self.weight other.weight def build_huffman(freq): heap [HuffmanNode(w, c) for c, w in freq.items()] heapq.heapify(heap) while len(heap) 1: left heapq.heappop(heap) right heapq.heappop(heap) merged HuffmanNode(left.weight right.weight) merged.left, merged.right left, right heapq.heappush(heap, merged) return heap[0]4. 哈夫曼编码实战应用生成哈夫曼编码就像走迷宫往左走记0往右走记1。以前文最后的树为例45的路径是0 → 编码05的路径是1→1→0→0 → 编码1100编码实现采用深度优先遍历def encode_huffman(root, path, code{}): if root.char is not None: code[root.char] path else: encode_huffman(root.left, path0, code) encode_huffman(root.right, path1, code) return code在数据压缩时实测发现哈夫曼编码有这些特点前缀无歧义没有编码是另一个编码的前缀高频字符编码长度 ≤ 低频字符平均编码长度接近信息熵我曾用哈夫曼编码压缩英文文本对比发现字母e的编码最短通常1-2位字母z的编码较长4-5位整体压缩率取决于字符频率分布解码时需要逐位匹配def decode_huffman(root, encoded): res [] node root for bit in encoded: node node.left if bit 0 else node.right if node.char: res.append(node.char) node root return .join(res)